5
$\begingroup$

Let $S=\{1,2,\dots,n\}$ and $P(S)$ the family of the $2^n$ subsets of $S$. Prove that the number of sequences $(S_1,S_2, \dots, S_k )$ formed by the subsets of $S$ that verify that $S_i \cap S_j = \varnothing$ for $i\neq j$ is $(k+1)^n$.

I have done research about this problem and everything leads to be a partition of a set of $n$ elements into $k$ classes, but in no way the result is $(k+1)^n$. So I think the problem is that I do not understand the question (so it is not such partition).

$\endgroup$
0

4 Answers 4

2
$\begingroup$

For each $a \in \{1,2,\ldots,n\}$, there are $k+1$ possibilities: $a$ can be element of $S_1$, of $S_2$, ..., of $S_n$ or of none of the $S_i$. It is not possible that $a$ is an element of more than one of the $S_i$, since that would contradict the condition $S_i \cap S_j$ for $i \neq j$. Multiplying these $k+1$ possibilities for all $a \in \{1,2,\ldots,n\}$ yields the answer of $(k+1)^n$ possibilities.

$\endgroup$
0
$\begingroup$

Fix $k$, and do an induction on $n$.

We deal with the induction step. A sequence for $\{1,2,\dots,n,n+1\}$ can be obtained in $k+1$ ways from a sequence for $\{1,2,\dots,n\}$: (i) add $n+1$ to $S_i$ for some $i$, or (ii) do not change any $S_i$. There are $k(k+1)^n$ sequences of Type (i), and $(k+1)^n$ sequences of Type (ii). Add.

$\endgroup$
0
$\begingroup$

For every element in $S$ there are $k+1$ options, it can belong to none of the $k$ sets or to exactly one. This decision must be taken $n$ times.

$\endgroup$
0
$\begingroup$

Supposing that the empty set may form part of a sequence we get the combinatorial species $$\mathfrak{S}_{=k}(\mathfrak{P}(\mathcal{Z})) \times\mathfrak{P}(\mathcal{Z})$$ which represents a sequence of $k$ sets coupled with a choice about the elements that are not used.

This gives the generating function $$\left(\exp(z)\right)^k\times \exp(z) = \exp((k+1)z).$$

Clearly $$n![z^n]\exp((k+1)z) = n!\times\frac{(k+1)^n}{n!} =(k+1)^n,$$ proving the claim.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .