ghijk3
Lv 4
ghijk3 asked in Science & MathematicsMathematics · 1 decade ago

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

Update:

To the first answerer:

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.

3 Answers

Relevance
  • 1 decade ago
    Best Answer

    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=20080627172...

    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:

    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..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. :)

    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

  • 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 )

  • 3 years ago

    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

Still have questions? Get your answers by asking now.