## Task A-4.4.

Let $n$ and $k$ be natural numbers and $S=\{1,2, \ldots, n\}$.

a) Determine the number of all ordered $k$-tuples $\left(A_{1}, A_{2}, \ldots, A_{k}\right)$ where $A_{i}, i=1, \ldots, k$ are pairwise disjoint subsets of $S$ such that $\bigcup_{i=1}^{k} A_{i}=S$.

b) Determine the number of all ordered $k$-tuples $\left(A_{1}, A_{2}, \ldots, A_{k}\right)$ where $A_{i}, i=1, \ldots, k$ are subsets (not necessarily disjoint) of $S$ such that $\bigcup_{i=1}^{k} A_{i}=S$.
Solution. a) part of the task is worth 3 points, and b) part is worth 7 points.

a) Each of the elements of the set $S$ is in one and only one of the sets $A_{i}$, $i=1, \ldots, k$.

(1 point)

Thus, the subset in which a particular element will be located can be chosen in $k$ ways.

(1 point)

Since the set $S$ has $n$ elements, the desired number is $k^{n}$.

b) 1st method

Assign a binary sequence of length $n$ to each set $A_{i}$ which has 1 at position $l$ if $l \in A_{i}$ or 0 if $l \notin A_{i}$.

(2 points)

Form a $k \times n$ matrix whose rows are the binary sequences assigned to the sets $A_{1}, A_{2}, \ldots, A_{k}$.

(1 point)

Due to the condition $\bigcup_{i=1}^{k} A_{i}=S$, in each column of this matrix there is at least one one.

(1 point)

Conversely, every binary matrix $k \times n$ in which there is at least one one in each column determines one $k$-tuple of subsets that satisfies the given condition.

(1 point)

There are $\left(2^{k}-1\right)^{n}$ such matrices, since each column can be chosen in $2^{k}-1$ ways (all except $000 \ldots 0$).

(2 points)

b) 2nd method

Define the sets $T_{1}, \ldots, T_{n}$ such that $T_{i}$ contains all ordered $k$-tuples $\left(A_{1}, A_{2}, \ldots, A_{k}\right)$ of subsets of $S \backslash\{i\}$ (with no other conditions on the union).

The desired number is the number of elements of the set $T_{1}^{c} \cap T_{2}^{c} \cap \cdots \cap T_{n}^{c}$. We will calculate it using the inclusion-exclusion principle

$$
\left|T_{1}^{c} \cap T_{2}^{c} \cap \ldots \cap T_{n}^{c}\right|=|T|-\sum_{i=1}^{n}\left|T_{i}\right|+\sum_{1 \leqslant i<j \leqslant n}\left|T_{i} \cap T_{j}\right|-\ldots+(-1)^{n}\left|T_{1} \cap \ldots \cap T_{n}\right|
$$

where $T$ is the set of all ordered $k$-tuples $\left(A_{1}, A_{2}, \ldots, A_{k}\right)$ of subsets of $S$, with no additional conditions.

(1 point)

Clearly, $|T|=\left(2^{n}\right)^{k}$ since we are choosing $k$ subsets of an $n$-element set.

The set $S \backslash\{i\}$ contains $n-1$ elements, so $\left|T_{i}\right|=\left(2^{n-1}\right)^{k}$ for each $i=1, \ldots, n$.

The set $S \backslash\{i, j\}$ contains $n-2$ elements, so $\left|T_{i} \cap T_{j}\right|=\left(2^{n-2}\right)^{k}$, etc.

(3 points)

If we substitute all of this into the formula, using the binomial theorem, we get that the desired number is

$$
\begin{aligned}
\left|T_{1}^{c} \cap T_{2}^{c} \cap \ldots \cap T_{n}^{c}\right| & =2^{k n}-\sum_{i=1}^{n} 2^{k(n-1)}+\sum_{1 \leqslant i<j \leqslant n} 2^{k(n-2)}-\ldots+(-1)^{n} 2^{0} \\
& =2^{k n}-n \cdot 2^{k(n-1)}+\binom{n}{2} 2^{k(n-2)}-\ldots+(-1)^{n} 2^{0} \\
& =\sum_{r=0}^{n}\binom{n}{r}(-1)^{n-r}\left(2^{k}\right)^{r}=\left(2^{k}-1\right)^{n}
\end{aligned}
$$