Yahoo Answers: Answers and Comments for Serious math: find a formula for the number of surjective function from a set with n elemente to a set with m? [Mathematics]
Copyright © Yahoo! Inc. All rights reserved.
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
From ghijk3
enUS
Thu, 03 Jul 2008 03:01:14 +0000
3
Yahoo Answers: Answers and Comments for Serious math: find a formula for the number of surjective function from a set with n elemente to a set with m? [Mathematics]
292
38
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
https://s.yimg.com/zz/combo?images/emaillogous.png

From bothwell: What thou loookest for thou will possibly no l...
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
Sat, 08 Oct 2016 11:02:05 +0000
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

From MathMan TG: This is very much like another problem I saw r...
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
Thu, 03 Jul 2008 11:09:34 +0000
This is very much like another problem I saw recently here,
but without all the fancy terms like "surjective" and "codomain".
http://answers.yahoo.com/question/?qid=20080627172925AAH38qC
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..k1) [ 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/CouponCollectorProblem/
Example:
4 balls, 3 baskets:
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..k1) [ 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. :)
Addendum:
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

From antidisestablishmentarianist: in a surjective function, the range is the who...
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
https://answers.yahoo.com/question/index?qid=20080703030114AAzN8mf
Thu, 03 Jul 2008 03:15:56 +0000
in a surjective function, the range is the whole of the codomain
ie. each element of the codomain set must have a preimage 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 preimages 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 preimage 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 preimage
thus the total number of surjective functions is :
n*n*n*n*n*n...(m times)
= ( n ^ m )