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?

1,102

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.

Share:
1,102

Related videos on Youtube

Uni696
Author by

Uni696

Updated on August 01, 2022

Comments

  • Uni696
    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
      Sujaan Kunalan almost 10 years
      What are your thoughts on the problem? Is there anything in particular that is giving you difficulties? What have you tried?
  • juantheron
    juantheron almost 10 years
    Nice solution André Nicolas....