Matematyka.pl

Mam zbiór \(\displaystyle{ B = \left\{ \left( A, B\right) \in P\left( \left\{ 1, 2, ..., n\right\} \right)^2: A \subseteq B \right\}}\)
Chcę policzyć \(\displaystyle{ \left| B \right|}\)
Zacząłem tak: dla każdego możliwego \(\displaystyle{ B}\) ( przy liczeniu konkretnego \(\displaystyle{ B}\), \(\displaystyle{ |B| = k}\) ) liczę możliwe A (|A| < k).
Odrzucam \(\displaystyle{ k=0}\) ,bo wtedy nie znajde A będącego podzbiorem B.

\(\displaystyle{ \sum_{k=1}^{n} {n \choose k} \left( \sum_{i=0}^{k} {k \choose i} \right)}\)

czyli mnożę dla ustalonego \(\displaystyle{ B}\) sposoby dobrania \(\displaystyle{ A}\) i sumuje to dla mocy \(\displaystyle{ B}\) od \(\displaystyle{ k=1}\) do \(\displaystyle{ k=n}\)

tylko dalej mi nie idzie
- co robię źle?
- jak wyznaczyć moc tego zbioru

Nie odrzucaj \(\displaystyle{ k=0}\) bo zbiór pusty zawiera się w każdym zbiorze, więc go ominiesz.
Rozwiąż to zadanie używając wzoru dwumianowego Newtona:
\(\displaystyle{ \sum_{k=0}^{n}\binom{n}{k}\left( \sum_{i=0}^{k}\binom{k}{i} \right)=\sum_{k=0}^{n}\binom{n}{k} 2^{k} =\left( 2+1\right)^n=3^n}\)