Question: $F$ is the set of all functions from a $n$-set to $B=\{a,b,c\}$. In a random experiment of selection of functions from $f$ assume that every $f\in F$ is equally likely. What is the probability that such a function has $a$ in its image?

I know the problem can be easily tackled by calculating the probability of selecting a function not having $a$ in its image ($=2^n/3^n$), and finding the desired probability by subtracting it from $1 (=\frac{3^n-2^n}{3^n})$. However I wanted to see if I could solve it using the Inclusion-Exclusion Principle too:

The total number of functions $f: \{a_1,a_2,a_3...a_n\} \to \{a,b,c\}$ would be $3^n$. Let $P_i$ be the property "$a_i$ doesnt map to $a$". Hence,

$$\sum_{1\leq i\leq n}|P_i| = \sum 2 \cdot 3^{n-1} = n\cdot2\cdot 3^{n-1}$$ (Choose from $\{b,c\}$ for $a_i$, $\{a,b,c\}$ for the rest)

$$\sum_{1\leq i \leq j \leq n}|P_i \cap P_j| = \sum 2^2 \cdot3^{n-2}n={n \choose 2}2^2\cdot3^{n-2}$$ (Choose from $\{b,c\}$ for ${n \choose 2}$ pairs of $(a_i, a_j)$)

Hence, $$\sum\left|\bigcap_{i=1}^{r} P_i\right|={n \choose r}2^r\cdot3^{n-r}$$ (Choose from $\{b,c\}$ for ${n\choose r}$ selections of $(a_i,a_j...a_{i+r})$)

By IEP, Number of functions which map having $a$ in its image= $$\left|\bigcap_{i=1}^n\overline{P_i}\right|=\left|\overline{\bigcup_{i=1}^n P_i}\right|=3^n -\left|\bigcup_{i=1}^n P_i\right|=3^n-2\cdot3^{n-1}n+{n \choose 2}2^2\cdot3^{n-2}\cdots+(-1)^n2^n = (3-2)^n=1$$ The number of functions which have $a$ in their image definitely isn't $1$. Is there something wrong with this approach?


A good careful calculation, unfortunately of the wrong thing.

The Inclusion/Exclusion argument in the OP shows, in a correct but lengthy way, that there is exactly one function that maps all the $a_i$ to $a$.

For the union of the $P_i$ is the set of all functions that miss $a$ somewhere. Subtracting the cardinality of the union from $3^n$ counts the functions that miss $a$ nowhere. There is only one such function.

  • $\begingroup$ So, is it possible to find the number of functions using IEP (maybe by not subtracting the union from $3^n$)? $\endgroup$ – Vibhav Pant Jan 3 '15 at 5:05
  • 1
    $\begingroup$ An Inclusion/Exclusion argument very similar to yours will work, though as you know it is not optimal. We count the functions that map $1$ to $a$, $2$ to $a$ and so on and add up. From these we must subtract the functions that send both $1$ and $2$ to $a$, and so on for all pairs. And add back $\dots$. When we divide by $3^n$ we get $1$ minus the binomial expansion of $\left(1-\frac{1}{3}\right)^n$. $\endgroup$ – André Nicolas Jan 3 '15 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.