2
$\begingroup$

I wish to count the number of onto functions from a $[k]$ set to $[4]$ through considering the complement. Here is what I have in mind, subtract the total number of functions from $[k]$ to $[4],$ $4^k$ with the number of functions that fail to map to all of the $4$ elements in $[4],$ i.e. $4^k - [4 + 6(2^k - 2) + 4(3^k - 10)]$ corresponds to the total - [functions mapping to a single element + $2$ elements of $4$ + $3$ elements of $4$] only would be the number of onto functions from $[k]$ to $[4].$

Is this reasoning and formula correct? As of now I am unsure if the $3$ element missed formula is correct, $4(3^k - 10).$ Any thoughts or hints would be appreciated.

$\endgroup$
1
  • $\begingroup$ This answer could help you. $\endgroup$ Oct 29, 2016 at 9:39

1 Answer 1

2
$\begingroup$

To see that your answer $4^k-[4+6(2^k-2)+4(3^k-10)]$ is wrong, just try plugging in some small values of $k;$ for $k=1,2,3,4$ you should get $0,0,0,24$ if your formula is correct.

The in-and-out formula is designed for problems like this. For four sets $A_1,A_2,A_3,A_4\subseteq E$ the formula is $$|E\setminus(A_1\cup A_2\cup A_3\cup A_4)|=$$ $$|E|$$ $$-(|A_1|+|A_2|+|A_3|+|A_4|)$$ $$+(|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|)$$ $$-(|A_1\cap A_2\cap A_3|+|A_1\cap A_2\cap A_4|+|A_1\cap A_3\cap A_4|+|A_2\cap A_3\cap A_4|)$$ $$+|A_1\cap A_2\cap A_3\cap A_4|.$$ If $E$ is the set of all functions from $[k]=\{1,\dots,k\}$ to $[4]=\{1,2,3,4\},$ and $A_i$ is the set of all functions $f\in E$ such that $i$ is not in the range of $f,$ then $$|E|=4^k,$$ $$|A_1|=|A_2|=|A_3|=|A_4|=3^k,$$ $$|A_1\cap A_2|=|A_1\cap A_3|=|A_1\cap A_4|=|A_2\cap A_3|=|A_2\cap A_4|=|A_3\cap A_4|=2^k,$$ $$|A_1\cap A_2\cap A_3|=|A_1\cap A_2\cap A_4|=|A_1\cap A_3\cap A_4|=|A_2\cap A_3\cap A_4|=1^k=1,$$ $$|A_1\cap A_2\cap A_3\cap A_4|=0^k=\begin{cases} 0\text{ if }k\gt0,\\ 1\text{ if }k=0. \end{cases}$$

Thus, For $k\ge1,$ the number of "onto" functions from $[k]$ to $[4]$ is $$|E\setminus(A_1\cup a|2\cup A_3\cup A_4)|=4^k-\binom413^k+\binom422^k-\binom431^k+\binom440^k=\boxed{4^k-4\cdot3^k+6\cdot2^k-4}\ .$$

Likewise, the number of "onto" functions from $[k]$ to $[3]$ is $$3^k-\binom312^k+\binom321^k+\binom330^k=3^k=\boxed{3^k-3\cdot2^k+3}\ne3^k-10.$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .