Let A = {1, 2, 3, . . . , 10}, and B = {1, 2, 3, . . . , 7}. How many functions f : A→B satisfy |f (A)| = 4? How many have |f (A)| ≤ 4?
We do $|f(A)|=4$. There are $\binom{7}{4}$ ways to choose $4$ numbers from $B$.
For each such choice $Y$, for example $Y=\{1,3,5,7\}$, we count the onto functions to $Y$.
There are $4^{10}$ functions from $A$ to $Y$. However, some are not onto. There are $3^{10}$ functions that miss $1$, and the same number that miss $3,5,7$. However, if we adjust by subtracting $\binom{4}{1}3^{10}$, we will have subtracted too much, for we will have subtracted twice the functions that, for example, miss $1$ and $3$, and similarly for all pairs. So we must add back $\binom{4}{2}2^{10}$. However, this adds back too much, since we have added back one too much for the $\binom{4}{3}1^{10}$ functions that have a $1$-element range. Our count is therefore $$\binom{7}{4}\left(4^{10}-\binom{4}{1}3^{10}+\binom{4}{2}2^{10}-\binom{4}{3}1^{10}\right).$$
Inclusion/Exclusion cn also be used for the second problem, which we leave to you.
Related videos on Youtube
Uni696
Updated on August 01, 2022Comments
-
Uni696 over 1 year
Let $A=\{1, 2, 3, . . . , 10\}$ and $B=\{1, 2, 3, . . . , 7\}$.
a) How many functions $f: A \rightarrow B$ satisfy $|f(A)| = 4$?
b) How many have $|f (A)|\leq 4$?
-
Sujaan Kunalan almost 10 yearsWhat are your thoughts on the problem? Is there anything in particular that is giving you difficulties? What have you tried?
-
-
juantheron almost 10 yearsNice solution André Nicolas....