Collecties van deelverzamelingen
Opgave - PUMA 2010 vraag 3
Zij $S$ een verzameling met $n$ elementen, en kies een vast getal $k \in \mathbb{N}\backslash\left\{0\right\}$. Hoeveel $k$-tallen $(T_1,\ldots,T_k)$ van deelverzamelingen $T_i\subseteq S$ zijn er zodat $T_1 \subseteq T_2 \subseteq \ldots \subseteq T_k$?
Om triviale herformuleringen van de opgave te vermijden mag in het antwoord enkel gebruik gemaakt worden van optelling, aftrekking, vermenigvulding, deling, machtsverheffing, worteltrekking, combinaties, faculteiten en gevalstudies. Uiteraard mogen (en moeten) deze uitdrukkingen $k$ en $n$ bevatten. Recursieve antwoorden of herformuleringen van de opgave worden niet goedgekeurd.
- login om te reageren
Oplossing
Oplossing 1. Voor elk element van $S$ zijn er $k+1$ mogelijke gevallen: in $T_1$, niet in $T_1$ maar wel in $T_2$, niet in $T_2$ maar wel in $T_3$, ..., niet in $T_{k-1}$ maar wel in $T_k$, niet in $T_k$. Dit zijn $k+1$ gevallen, die per element onafhankelijk zijn, het totale aantal is dus $(k+1)^n$.
Oplossing 2. Stellen we $T_{k+1} = \left\{1,2,\ldots,n\right\}$. We definiëren de afbeelding $f T_{k+1} \rightarrow \left\{1,2,\ldots,k,k+1\right\}$, die elk element $i$ uit haar definitieverzameling afbeeldt op het element $j$ van haar domein zodat $i \in T_j$ en $i \not\in T_{j'}$ voor $j' < j$. Deze afbeelding geeft duidelijk een bijectie tussen de collecties deelverzamelingen met de gewenste inclusies en de woorden van lengte $n$ met $k+1$ letters. Op elke van de $n$ posities zijn er $k+1$ keuzes, dus het gezochte aantal is $(k+1)^n$.