Given 3 sets $|A|=6, |B|=4, |C|=3$ and $C \subseteq B$. Calculate the size of the set: $\{f\in A\to B$ $| C\subseteq Imf\}$

Question

Given 3 sets $|A|=6, |B|=4, |C|=3$ and $C \subseteq B$. Calculate the size of the set:

$\{f\in A\to B$ $| C\subseteq Imf\}$

Please let me know if you have any idea on how to solve this. Thank you

Answer 1

Without loss of generality, let $A=\{1,2,3,4,5,6\}$, let $B=\{1,2,3,4\}$ and let $C=\{1,2,3\}$.

The total number of functions from $A$ to $B$ can be calculated via rule of product by the following steps:

• Choose the value of $f(1)$: there are four options
• Choose the value of $f(2)$: there are again four options
• Choose the value of $f(3)$: there are again four options
• $\vdots$
• Choose the value of $f(6)$: there are again four options

giving a total of $4\cdot 4\cdot 4\cdot 4\cdot 4\cdot 4=4^6=4096$ possible functions from $A$ to $B$.

(The same argument can be generalized to show that there are $|Y|^{|X|}$ functions from $X$ to $Y$ in general. It is for this reason that the set of functions from $X$ to $Y$ is sometimes notated as $Y^X$ yielding the nice identity $|Y^X|=|Y|^{|X|}$)

We are interested in a special subset of the functions from $A$ to $B$ with the property that $C$ is a subset of the image, i.e. every element of $C$ is contained in the image at least once. To calculate this, let us instead remove from our count the number of "bad" functions, namely those functions which are missing at least one of the elements of $C$ from the image.

Let $X_1$ be the set of functions from $A$ to $B$ which does not have $1$ in the image. Similarly define $X_2$ and $X_3$ to be the sets of functions missing $2$ and $3$ from their images respectively. The set of "bad" functions then is $X_1\cup X_2\cup X_3$.

The total number of good functions then is the total number of functions minus the number of bad functions, i.e. $$4^6 - |X_1\cup X_2\cup X_3|$$

Expanding via inclusion-exclusion

$$4^6-|X_1|-|X_2|-|X_3|+|X_1\cap X_2|+|X_1\cap X_3|+|X_2\cap X_3|-|X_1\cap X_2\cap X_3|$$

Calculating each of these terms can be done again by the rule of product using the generalization mentioned above. For example $|X_1\cap X_2|$ is the number of functions from $A$ to $B$ which does not contain $1$ or $2$ in the image, i.e. the number of functions from $\{1,2,3,4,5,6\}$ to $\{3,4\}$.

As found in the comments above, this then simplifies as:

$$4^6-3^6-3^6-3^6+2^6+2^6+2^6-1^6=2100$$