# Serious math: find a formula for the number of surjective function from a set with n elemente to a set with m?

Update:

you cannot assign one element of the domain to two different elements of the codomain,

therefore your choises are not always n.

Update 2:

The second choice depends on the first one.

Update 3:

The solution is quite difficult.

Relevance

This is very much like another problem I saw recently here,

but without all the fancy terms like "surjective" and "codomain".

If you throw n balls at m baskets, and every ball lands in a basket, what is the probability of having at least one ball in every basket ?

Disregarding the probability aspects, I came up with this formula:

cover(n,k) = k^n - SUM(i = 1..k-1) [ C(k,i) cover(n, i) ]

(Where C(k,i) is combinations of (k) things (i) at a time.)

Where "cover(n,k)" is the number of ways of mapping the n balls onto the k baskets with every basket represented at least once.

From the k^n universe of functions,

we eliminate those with missing baskets.

That is we pick "i" baskets to have balls in them (in C(k,i) ways), (i < k)

and then throw balls at only those baskets (in cover(n,i) ways).

We then eliminate those cases.

This is related (if not the same as) the "Coupon Collector Problem", described at

http://demonstrations.wolfram.com/CouponCollectorP...

Example:

call the baskets A, B, and C.

Then when we throw the balls we can get 3^4 possible outcomes:

AAAA

AAAB

AAAC

AABA

AABB

AABC

AACA

AACB

AACC

....etc.

Formula gives:

cover(n,k) = k^n - SUM(i = 1..k-1) [ C(k,i) cover(n, i) ]

3^4 -

( C(3,1) * cover(4,1) +

C(3,2) * cover(4,2) )

cover(4,1) = 1 (all balls in the lone basket)

cover(4,2) =

2^4 - C(2,1) * cover(3,1) = 16 - 2 = 14

So we get 81 - 3 - 42 = 36.

Looking at the example above, and extending to all the

cases where A is the first one:

AAAA

AAAB

AAAC

AABA

AABB

AABC <---

AACA

AACB <---

AACC

ABAA

ABAB

ABAC <----

ABBA

ABBB

ABBC <----

ABCA <----

ABCB <----

ABCC <----

In the first group, the first 2 throws were the same

and there were 2 successful cases.

There are 2 more groups like this: total 6 successes.

In the second group, the first 2 throws were different,

and there were 5 successful cases.

There are 5 more groups like that, total 30 successes.

Total of 36 successes, as the formula gave.

Now all we need is something in closed form. :)

If n = m, then it's easy: n!

Here are some numbers for various n, with m = 3:

4 3: 36

5 3: 150

6 3: 540

7 3: 1806

8 3: 5796

9 3: 18150

10 3: 55980

11 3: 171006

12 3: 519156

13 3: 1569750

14 3: 4733820

15 3: 14250606

16 3: 42850116

17 3: 128746950

18 3: 386634060

19 3: 1160688606

20 3: 3483638676

21 3: 10454061750

22 3: 31368476700

23 3: 94118013006

24 3: 282379204836

25 3: 847187946150

and m = 4:

5 4: 240

6 4: 1560

7 4: 8400

8 4: 40824

9 4: 186480

10 4: 818520

11 4: 3498000

12 4: 14676024

13 4: 60780720

14 4: 249401880

15 4: 1016542800

and m = 10:

11 10: 199584000

12 10: 6187104000

13 10: 142702560000

14 10: 2731586457600

15 10: 45950224320000

16 10: 703098107712000

• Login to reply the answers
• in a surjective function, the range is the whole of the codomain

ie. each element of the codomain set must have a pre-image in the domain

in our case, all 'm' elements of the second set, must be the function values of the 'n' arguments in the first set

thus we need to assign pre-images to these 'n' elements, and count the number of ways in which this task can be done

of the 'm' elements, the first element can be assigned a pre-image in 'n' ways, (ie. any one of the 'n' elements can have the first element of the codomain as its function value --> image)

similarly, for each of the 'm' elements, we can have 'n' ways of assigning a pre-image

thus the total number of surjective functions is :

n*n*n*n*n*n...(m times)

= ( n ^ m )

• Login to reply the answers
• What thou loookest for thou will possibly no longer discover (and please warms those palms first in case you do no longer techniques) My advice - take decrease lunch while "going bush" this could take an prolonged whilst so relax your tush it is not a stable circulate in scheme of romance yet I see out of your face you could take of venture score me out of 10 once you get the time it may motivate me to place in writing you a rhyme

• Login to reply the answers