- #1

mr_coffee

- 1,629

- 1

Hello everyone i was wondering if someone could check to see if this looks correct or not. The question is:

If X is a set with n elements and Y is a set with m elements, express the number of onto functions from X and Y using Stirling numbers of the second kind. Justify your answer.

for more info on stirling numbers of a second kind look here:

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

Well the back of the book gave the following hint:

The number of onto functions from X = {x_1,x_2,x_3,x_4} to Y = {y_1,y_2,y_3} is [tex]S_{4,3}x3![/tex] because the construction of an onto function can be thought of as a 2-step processs where

step 1: is to choose a partion of X into 3 subsets and

step 2: is to choose, for each subset of the partition, an element of Y for the elements of the subset to be sent to.

Well in the question X has n elements in the hint 4 elements.

Y has m elements in the question and in the hint it has 3 elements.

So it looks like the answer would be:

[tex]S_{n,m} x m![/tex]

does that look right to you? thanks!

If X is a set with n elements and Y is a set with m elements, express the number of onto functions from X and Y using Stirling numbers of the second kind. Justify your answer.

**note: the x in the latex generated graphics means multiply not the variable 'x'.**for more info on stirling numbers of a second kind look here:

http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

Well the back of the book gave the following hint:

The number of onto functions from X = {x_1,x_2,x_3,x_4} to Y = {y_1,y_2,y_3} is [tex]S_{4,3}x3![/tex] because the construction of an onto function can be thought of as a 2-step processs where

step 1: is to choose a partion of X into 3 subsets and

step 2: is to choose, for each subset of the partition, an element of Y for the elements of the subset to be sent to.

Well in the question X has n elements in the hint 4 elements.

Y has m elements in the question and in the hint it has 3 elements.

So it looks like the answer would be:

[tex]S_{n,m} x m![/tex]

does that look right to you? thanks!

Last edited: