Úloha 2.u2: Čtveřice množin (3 b)

Zadáno v čísle 24.2.

Řešeno v čísle 24.4.

Zadání

Kolik existuje čtveřic množin $(A, B, C, D)$ takových, že1

\[ A \subseteq B \subseteq C \subseteq D \subseteq \{ 1, 2, \ldots , n\} \]

pro dané přirozené $n$?


1) zápis $A\subseteq B$ znamená „$A$ je podmnožina $B$“.

Řešení

Nejlepší je podívat se na problém z pohledu jednotlivých čísel. Pro každé číslo $k$ z množiny $\{ 1, 2, \dots , n\} $ platí jedna z následujících pěti možností:

  1. $k \notin A, k \notin B, k \notin C, k \notin D$

  2. $k \notin A, k \notin B, k \notin C, k \in D$

  3. $k \notin A, k \notin B, k \in C, k \in D$

  4. $k \notin A, k \in B, k \in C, k \in D$

  5. $k \in A, k \in B, k \in C, k \in D$

Volby umístění jednotlivých čísel do množin jsou na sobě navzájem nezávislé. Máme $n$ pozic, na kterých si vybíráme z 5 možností. Celkový počet čtveřic množin $(A, B, C, D)$ je proto $5^ n$.