How many onto functions are there from a set with n elements to a set with three elements?

Could somebody explain how to do this, perhaps substituting 5 in for n?

Printable View

- Dec 13th 2009, 03:49 AMjmedsy[SOLVED] number of onto functions
How many onto functions are there from a set with n elements to a set with three elements?

Could somebody explain how to do this, perhaps substituting 5 in for n? - Dec 13th 2009, 04:22 AMShanks
You can solve it by recusive definition: suppose $\displaystyle n\geq 3$

Let $\displaystyle A_n$ be the number of onto function from a set with n elements to a set with three elements, $\displaystyle B_n$ be the number of onto function from a set with n elements to a set with two elements.

then what is the recusive relation between $\displaystyle A_{n+1}$,$\displaystyle A_n$ and $\displaystyle B_n$?

$\displaystyle A_{n+1}=3A_n+3B_n$

while it is easy to see that $\displaystyle A_3=6,B_n=2^n-2$.