telprobleem

Opgave - IrMO 1992 dag 1 vraag 3

$A$ heeft $n$ elementen. Hoeveel $(B,C)$ zijn er zodat $\emptyset\neq B\subseteq C\subseteq A$?

Oplossing

Als $|C|=k$ zijn er voor $B$ precies $2^k-1$ mogelijkheden, dus uiteindelijk zoeken we $\sum^n_{i=1} (2^k-1)\binom{n}{k} = \sum^n_{i=1} 2^k\binom{n}{k} - \sum^n_{i=1} \binom{n}{k}$.

Daarin herkennen we de binomiaaluitwerking van $(2+1)^k-2^k$, dus is het gevraagde aantal $3^k-2^k$.