I know the standard formula for finding the number of onto functions (for a function $f: [n] \to [m],$ where $[n] = \{1, …, n\}$ and $n \ge m$) is the one that involves inclusion/exclusion, but I'm not fully sure why using the multiplication rule would be wrong here.
In particular, I did $${n\choose m} \cdot m! \cdot m^{n-m}$$
My reason is as follows:
${n\choose m} \cdot m!$ (Part 1): When I first did this part, I was just attempting to ensure that there are a set of elements in the domain that map to all the elements in the codomain, hence ensuring it's onto. However, I think a better way to justify my reasoning (that I just thought of while writing this question) is the intuition that for any onto function there must be a partial function that's bijective (not sure how to formally prove it though), hence this is what this part of my formula attempts to do.
$m^{n – m}$ (Part 2): This is just mapping the remaining domain elements to any of the elements in the codomain since we've already ensured the function is onto but still need these elements to map to exactly 1 element in the codomain to still be a function
I can see that there's at least one example where this overcounts:
f: [8] -> [4]
- Part 1: choose the domain elements 1, 2, 3, 4 and map them to 1, 2,
3, 4 (respectively) - Part 2: map the remaining domain elements 5, 6,
7, 8 to 1, 2, 3, 4 (also respectively)
or
- Part 1: choose the domain elements 5, 6, 7, 8 and map them to 1, 2,
3, 4 (respectively) - Part 2: map the remaining domain elements 1, 2,
3, 4 to 1, 2, 3, 4 (also respectively)
Both lead to the same function.
I think this hits home at a fundamental issue I often struggle with when using the multiplication rule, that is I don't know when to properly use it such that I avoid overcounting. What are the exact conditions in which you're allowed to use the product rule, since textbooks I feel don't give a rigorous enough definition and it leads to such errors for many people. Maybe I'm personally missing something here. Kindly please do help here.
Also, is there a way to modify my formula so that it can work?
Best Answer
The product rule says that if $A_1,A_2,\dots,A_n$ are sets, then the number of tuples $(a_1,a_2,\dots,a_n)$ with $a_i\in A_i$ is equal to the product of the numher of elements in each $A_i.$ In short:
$$|A_1\times\cdots\times A_n|=|A_1|\cdot\cdots\cdot |A_n|$$
In reality, we often call something the product rule when we are counting a set $S$ and find a function $f:A_1\times\cdots\times A_n\to S$ which is a bijection, and then $|S|=|A_1\times\cdot\times A_n|=|A_1|\cdots |A_n|.$
Such is the case in your example, and it is really a combination of two rules, the product rule and, for lack of memory, what I'll the bijection rule:
When in doubt, always try to think of such a count of $S$ this way, and try to make sure you know what the $A_i,S,$ and $f$ are, and whether you know $f$ is a bijection.
In your argument, $A$ is the set of subsets $\{a_1<a_2<\cdots<a_m\}$ of $[n]$ of size $m,$ $B$ is the set of permutations on $[m],$ and $C$ is the set of functions $[n-m]\to [m].$
Now, $|A|=\binom nm, |B|=m!, |C|=m^{n-m},$ and your formula correctly counts $A\times B\times C.$
But your function $f$ is not a bijection.
Here, $S$ is the set of all onto functions $h:[n]\to [m].$
Your function takes a tuple $x=(M,\pi,g)$ where $M=\{a_1<\cdots<a_m\}\subseteq [n],$ $\pi$ is a permutation of $[m],$ and $g:[n-m]\to [m].$
You define a map $f_x:[n]\to[m]$ as follows.
This creates a map $A\times B\times C\to S$ sending $x\mapsto f_x.$
This map is onto, but it is not one-to-one. It is not a bijection,
So all we can really say is $|A||B||C|\geq |S|.$
It is worth noting what your function does count.
For example, we can say your function counts all pairs $$S_2=\{(M,h)\mid M\in B, h:[n]\to [m],h(M)=[m]\}.$$ The bijection is $x\mapsto (M,f_x),$ and we get $|S_2|=|A||B||C|.$ But, when $n>m$ and $h\in S,$ there will always be two or more $M$ with $(h,M)\in S_2.$ So $|S_2|\geq 2|S|.$