0

Guest

Courses New

number of surjections formula

number of surjections formula

Grade:12

2 Answers

Charchit Tailong
askIITians Faculty 147 Points
7 years ago
It is quite easy to calculate the total number of functions from a setXwithmelements to a setYwithnelements (nm), and also the total number of injective functions (nm−−, denoting the falling factorial). But I am thinking about how to calculate the total number of surjective functionsf:X↠Y.

The way I thought of doing this is as follows: firstly, since allnelements of the codomainYneed to be mapped to, you choose anynelements from themelements of the setXto be mapped one-to-one with thenelements ofY. This results inn!possible pairings. But the number of ways of choosingnelements frommelements ism!(m−n)!n!, so the total number of ways of matchingnelements inXto be one-to-one with thenelements ofYism!(m−n)!n!×n!=m!(m−n)!.

Now we have 'covered' the codomainYwithnelements fromX, the remaining unpairedm−nelements fromXcan be mapped to any of the elements ofY, so there arenm−nways of doing this. Therefore I think that the total number of surjective functions should bem!(m−n)!nm−n.
Ashutosh Sharma
askIITians Faculty 181 Points
7 years ago
one can get a formula for the number of surjections using inclusion-exclusion, applied to the setsX1,...,Xm, where for eachithe setXiis defined to be the set of functions that never take the valuei. This gives rise to the following expression:mn−(m1)(m−1)n+(m2)(m−2)n−(m3)(m−3)n+….

Think You Can Provide A Better Answer ?

Other Related Questions on Magical Mathematics[Interesting Approach]

View all Questions »

View courses by askIITians

Design classes One-on-One in your own way with Top IITians/Medical Professionals

Click Here Know More

Complete Self Study Package designed by Industry Leading Experts

Click Here Know More

Live 1-1 coding classes to unleash the Creator in your Child

Click Here Know More

a Complete All-in-One Study package Fully Loaded inside a Tablet!

Click Here Know More