Matematyka dyskretna 1/Ćwiczenia 6: Permutacje i podziały: Różnice pomiędzy wersjami

← poprzednia edycja

WizualnieWikikod

Aktualna wersja na dzień 21:37, 11 wrz 2023

Permutacje i Podziały

Ćwiczenie 1

Policz średnią liczbę cykli w permutacji $n$ zbioru elementowego.

Wskazówka

Rozwiązanie

Ponieważ

\sum_{i = 0}^{n} i [\begin{array}{c} n \\ i \end{array}] = n! H_{n}

a suma po lewej stronie to sumaryczna liczba cykli we wszystkich permutacjach zbioru $n$ -elementowego, więc średnia liczba cykli równa jest wartości tej sumy podzielonej przez liczbę wszystkich permutacji zbioru $n$ -elementowego, czyli $n!$ :

\frac{\sum_{i = 0}^{n} i [\begin{array}{c} n \\ i \end{array}]}{n!} = H_{n}

Ćwiczenie 2

Oblicz postać zwartą symbolu ${\begin{array}{c} n \\ 4 \end{array}}$ .

Wskazówka

Skorzystaj z przestawienia ${\begin{array}{c} n \\ k \end{array}}$ w postaci sumy iloczynów współczynników dwumianowych.

Rozwiązanie

\begin{aligned} {\begin{array}{c} n \\ 4 \end{array}} & = \frac{1}{4!} \sum_{0 < i_{0} < i_{1} < i_{2} < n} (\binom{n}{i_{2}}) (\binom{i_{2}}{i_{1}}) (\binom{i_{1}}{i_{0}}) \\ = \frac{1}{24} \sum_{0 < i_{1} < i_{2} < n} (\binom{n}{i_{2}}) (\binom{i_{2}}{i_{1}}) \sum_{0 < i_{0} < i_{1}} (\binom{i_{1}}{i_{0}}) \\ = \frac{1}{24} \sum_{0 < i_{1} < i_{2} < n} (\binom{n}{i_{2}}) (\binom{i_{2}}{i_{1}}) (2^{i_{1}} - 2) \\ = \frac{1}{24} \sum_{0 < i_{2} < n} (\binom{n}{i_{2}}) (\sum_{0 < i_{1} < i_{2}} (\binom{i_{2}}{i_{1}}) 2^{i_{1}} - 2 \sum_{0 < i_{1} < i_{2}} (\binom{i_{2}}{i_{1}})) \\ = \frac{1}{24} \sum_{0 < i_{2} < n} (\binom{n}{i_{2}}) ((3^{i_{2}} - 1 - 2^{i_{2}}) - 2 (2^{i_{2}} - 2)) \\ = \frac{1}{24} \sum_{0 < i_{2} < n} (\binom{n}{i_{2}}) (3^{i_{2}} - 3 \cdot 2^{i_{2}} + 3) \\ = \frac{1}{24} ((4^{n} - 1 - 3^{n}) - 3 (3^{n} - 1 - 2^{n}) + 3 \cdot (2^{n} - 2)) \\ = \frac{1}{24} (4^{n} - 4 \cdot 3^{n} + 6 \cdot 2^{n} - 4) \end{aligned}

Ćwiczenie 3

Udowodnij wzór na odwracanie liczb Stirlinga, czyli że dla dowolnych funkcji $f, g$ określonych na $ℕ$ zachodzi:

f (n) = \sum_{i} {\begin{array}{c} n \\ i \end{array}} (- 1)^{i} g (i)

wtedy i tylko wtedy, gdy

g (n) = \sum_{i} [\begin{array}{c} n \\ i \end{array}] (- 1)^{i} f (i)

Wskazówka

Skorzystaj z zależności inwersyjnych między liczbami Stirlinga dla cykli i dla podziałów:

\sum_{i} [\begin{array}{c} m \\ i \end{array}] {\begin{array}{c} i \\ n \end{array}} (- 1)^{m - i} = {\begin{cases} 0, & dla m \neq n, \\ 1, & dla m = n \end{cases}

Rozwiązanie

Pokażemy jedynie implikację w dół (drugą można udowodnić analogicznie). Załóżmy zatem, iż $f (n) = \sum_{i} {\begin{array}{c} n \\ i \end{array}} (- 1)^{i} g (i)$ . Przekształcając sumę z prawej części tezy otrzymujemy:

\begin{aligned} \sum_{i} [\begin{array}{c} n \\ i \end{array}] (- 1)^{i} f (i) & = \sum_{i} [\begin{array}{c} n \\ i \end{array}] (- 1)^{i} \sum_{j} {\begin{array}{c} n \\ j \end{array}} (- 1)^{j} g (j) \\ = \sum_{j} \sum_{i} [\begin{array}{c} n \\ i \end{array}] {\begin{array}{c} i \\ j \end{array}} (- 1)^{i + j} g (j) \\ = \sum_{j} (- 1)^{n + j} g (j) \sum_{i} [\begin{array}{c} n \\ i \end{array}] {\begin{array}{c} i \\ j \end{array}} (- 1)^{n - i} \end{aligned}

Ale

\sum_{i} [\begin{array}{c} n \\ i \end{array}] {\begin{array}{c} i \\ j \end{array}} (- 1)^{n - i} = {\begin{cases} 0, & dla n \neq j, \\ 1, & dla n = j, \end{cases}

więc wszystkie składniki, poza $j = n$ , zewnętrznej sumy zerują się, więc:

\begin{aligned} \sum_{i} [\begin{array}{c} n \\ i \end{array}] (- 1)^{i} f (i) & = \sum_{j} (- 1)^{n + j} g (j) \sum_{i} [\begin{array}{c} n \\ i \end{array}] {\begin{array}{c} i \\ j \end{array}} (- 1)^{n - i} \\ = (- 1)^{n + n} g (n) \cdot 1 \\ = g (n) \end{aligned}

Ćwiczenie 4

Posługując się interpretacją kombinatoryczną pokaż, że

{\begin{array}{c} n + 1 \\ m + 1 \end{array}} = \sum_{k} (\binom{n}{k}) {\begin{array}{c} k \\ m \end{array}}

Wskazówka

Wyraź liczbę podziałów zbioru $(n + 1)$ -elementowego na $m + 1$ bloków poprzez wyróżnienie jednego z elementów, rozważenie w jak licznym bloku może się on znajdować i na ile sposobów można podzielić resztę elementów spoza tego bloku na $m$ bloków.

Rozwiązanie

Rozważmy podziały zbioru $(n + 1)$ -elementowego na $m + 1$ bloków. Dla ustalenia uwagi, rozważamy zbiór ${1, \dots, n + 1}$ . Zauważmy, że w dowolnym podziale naszego zbioru na $m + 1$ bloków, liczba elementów nie będących w bloku elementu $n + 1$ może przybrać wartość $k \in {m, \dots, n}$ . Elementy te możemy wybrać ze zbioru ${1, \dots, n}$ na $(\binom{n}{k})$ sposobów i potem podzielić na $m$ bloków na ${\begin{array}{c} k \\ m \end{array}}$ sposobów. Sumując po wszystkich, możliwych wartościach $k$ wnioskujemy, iż liczba podziałów zbioru ${1, \dots, n + 1}$ na $m + 1$ bloków wynosi

\sum_{k = m}^{n} (\binom{n}{k}) {\begin{array}{c} k \\ m \end{array}} = \sum_{k} (\binom{n}{k}) {\begin{array}{c} k \\ m \end{array}}

Ćwiczenie 5

Posługując się interpretacją kombinatoryczną pokaż, że

[\begin{array}{c} n + 1 \\ m + 1 \end{array}] = n! \sum_{k = 0}^{n} \frac{1}{k!} [\begin{array}{c} k \\ m \end{array}]

Wskazówka

Wyraź liczbę permutacji zbioru $(n + 1)$ -elementowego o $m + 1$ cyklach poprzez wyróżnienie jednego z elementów, rozważenie w jak licznym cyklu może się on znajdować i na ile sposobów można zbudować ten cykl przy ustalonej liczbie elementów oraz na ile sposobów można podzielić resztę zbioru na $m$ cykli.

Rozwiązanie

Policzmy permutacje zbioru ${1, \dots, n + 1}$ o $m + 1$ cyklach. W dowolnej, takiej permutacji liczba elementów nie będących w cyklu z elementem $n + 1$ wynosi $k \in {m, \dots, n}$ . Elementy te możemy wybrać ze zbioru ${1, \dots, n}$ na $(\binom{n}{k})$ sposobów i podzielić na $m$ cykli na $[\begin{array}{c} k \\ m \end{array}]$ sposobów. Do tego jeszcze $n - k$ elementów będących w cyklu z elementem $n + 1$ może stworzyć ten cykl na $(n - k)!$ sposobów. Podsumowując mamy

\sum_{k = m}^{n} (\binom{n}{k}) [\begin{array}{c} k \\ m \end{array}] (n - k)! = \sum_{k = m}^{n} \frac{n!}{k!} [\begin{array}{c} k \\ m \end{array}] = n! \sum_{k = 0}^{n} \frac{1}{k!} [\begin{array}{c} k \\ m \end{array}]

permutacji zbioru ${1, \dots, n + 1}$ o $m + 1$ cyklach.

Ćwiczenie 6

Posługując się interpretacją kombinatoryczną pokaż, że

{\begin{array}{c} m + n + 1 \\ m \end{array}} = \sum_{i = 0}^{m} i {\begin{array}{c} n + i \\ i \end{array}}

Wskazówka

Rozwiń ${\begin{array}{c} n + m + 1 \\ m \end{array}}$ używając wielokrotnie podstawowej zależności rekurencyjnej dla podziałowych liczb Stirlinga.

Rozwiązanie

Wystarczy pokazać, iż prawa strona równości zlicza podziały zbioru $(n + m + 1)$ -elementowego na $m$ bloków. W dowolnym podziale zbioru ${1, \dots, n, n + 1, \dots, n + m, n + m + 1}$ na $m$ bloków:

albo element $n + m + 1$ nie jest sam w swoim bloku.

Taki podział jest wyznaczony jednoznacznie przez podział zbioru ${1, \dots, n + m}$ na $m$ bloków i dołożenie elementu $n + m + 1$ do jednego z $m$ bloków.

Zatem takich podziałów jest $m {\begin{array}{c} n + m \\ m \end{array}}$ .

albo element $n + m + 1$ jest sam w swoim bloku.

Wtedy pozostałe $n + m$ elementy są podzielone na $m - 1$ bloków. Znów w dowolnym takim podziale:

- albo element $n + m$ nie jest sam w swoim bloku. Analogiczne rozumowanie do wcześniejszego wskazuje, że takich podziałów jest $(m - 1) {\begin{array}{c} n + m - 1 \\ m - 1 \end{array}}$ .
- albo element $n + m$ stanowi jednoelementowy blok, itd.

Po $m$ krokach powyższego wywodu otrzymujemy, że jest

n {\begin{array}{c} n + m \\ m \end{array}} + (n - 1) {\begin{array}{c} n + m - 1 \\ m - 1 \end{array}} + \dots + 1 {\begin{array}{c} n + 1 \\ 1 \end{array}}

podziałów zbioru ${1, \dots, n + m + 1}$ na $m$ bloków.

Ćwiczenie 7

Posługując się interpretacją kombinatoryczną pokaż, że

[\begin{array}{c} m + n + 1 \\ m \end{array}] = \sum_{i = 0}^{m} (n + i) [\begin{array}{c} n + i \\ i \end{array}]

Wskazówka

Rozwiń $[\begin{array}{c} n + m + 1 \\ m \end{array}]$ wielokrotnie używając podstawowej zależności rekurencyjnej dla cyklowych liczb Stirlinga.

Rozwiązanie

Analogicznie jak w Ćwiczeniu 6 wystarczy wykazać, iż prawa strona tożsamości zlicza permutacje zbioru $(n + m + 1)$ -elementowego o $m$ cyklach. W dowolnej permutacji zbioru ${1, \dots, n, n + 1, \dots, n + m, n + m + 1}$ o $m$ cyklach:

albo element $n + m + 1$ nie jest sam w swoim cyklu.

Dowolną taką permutację jednoznacznie wyznaczamy poprzez permutację zbioru ${1, \dots, n + m}$ o $m$ cyklach z dołożonym elementem $n + m + 1$ na jednej z $n + m$ możliwych pozycji. Zatem takich permutacji jest dokładnie $(n + m) [\begin{array}{c} n + m \\ m \end{array}]$ .

albo element $n + m + 1$ stanowi jednoelementowy cykl.

Wtedy elementy $1, \dots, n + m$ są rozłożone w $m - 1$ cyklach. Znów w dowolnej takiej permutacji:

- albo element $n + m$ nie jest sam w swoim cyklu.

Wtedy rozumując analogicznie jak wcześniej wiemy, iż takich permutacji jest $(n + m - 1) [\begin{array}{c} n + m - 1 \\ m - 1 \end{array}]$ .

- albo element $n + m$ stanowi jednoelementowy cykl, itd.

Po $m$ krokach powyższy wywód daje

(n + m) [\begin{array}{c} n + m \\ m \end{array}] + (n + m - 1) [\begin{array}{c} n + m - 1 \\ m - 1 \end{array}] + \dots + n [\begin{array}{c} n \\ 0 \end{array}]

permutacji zbioru ${1, \dots, n + m + 1}$ o $m$ cyklach.

Ćwiczenie 8

Posługując się interpretacją kombinatoryczną pokaż, że

{\begin{array}{c} n \\ l + m \end{array}} (\binom{l + m}{l}) = \sum_{k} (\binom{n}{k}) {\begin{array}{c} k \\ l \end{array}} {\begin{array}{c} n - k \\ m \end{array}}

Wskazówka

Zauważ, że obie strony równości to liczba podziałów zbioru $n$ -elementowego na $l + m$ bloków, przy czym $l$ bloków jest wyróżnionych (pomalowanych na czerwono).

Rozwiązanie

Lewą stronę tożsamości możemy interpretować jako liczbę podziałów zbioru $n$ -elementowego na $l + m$ bloków, w których $l$ bloków jest wyróżnionych (pomalowanych na czerwono).

Policzmy te specjalne podziały inną metodą. Wybierzmy najpierw $k$ -elementowy podzbiór zbioru $n$ -elementowego (na jeden z $(\binom{n}{k})$ sposobów), którego elementy będą stanowić wyróżnione bloki. Wybrany $k$ -elementowy podzbiór możemy podzielić na docelowe $l$ wyróżnionych bloków na ${\begin{array}{c} k \\ l \end{array}}$ sposobów. Pozostałe, zaś $n - k$ elementów możemy podzielić na $m$ , (nie czerwonych) bloków na ${\begin{array}{c} n - k \\ m \end{array}}$ sposobów.

Zatem dla ustalonego $k$ mamy $(\binom{n}{k}) {\begin{array}{c} k \\ l \end{array}} {\begin{array}{c} n - k \\ m \end{array}}$ podziałów zbioru $n$ -elementowego na $l + m$ bloków, przy czym wyróżnione $l$ bloków ma w sumie $k$ elementów. Sumując teraz po wszystkich możliwych wartościach $k$ możemy zakończyć dowód.

Ćwiczenie 9

Podział liczby $n$ na sumę jest symetryczny, jeśli odwracając jego diagram Ferrersa o $90$ stopni otrzymamy ten sam diagram.

MD1-SW 6.7.swf

MD1-SW 6.8.swf

Przykład

$6 + 5 + 3 + 2 + 2 + 1 = 19$

$6, 5, 3, 2, 2, 1$ jest podziałem symetrycznym $19$ .

$5 + 2 + 1 = 8$

$5, 2, 1$ nie jest podziałem symetrycznym $8$ .

Pokaż, że liczba podziałów symetrycznych liczby $n$ pokrywa się z liczbą podziałów liczby $n$ na różne i nieparzyste składniki.

Wskazówka

Rozwiązanie

MD1-SW 6.9.swf

Rozważmy $n = a_{0} + \dots + a_{k - 1}$ symetryczny podział liczby $n$ na sumę. Z symetryczności wiemy, iż liczba krzyżyków w ostatnim wierszu (tzn. liczba $a_{k - 1}$ ) jest równa liczbie krzyżyków w pierwszej kolumnie, a ponieważ mają one jeden krzyżyk wspólny to w sumie jest ich nieparzyście wiele ( $2 a_{k - 1} - 1$ ). Po wycięciu ostatniego wiersza i pierwszej kolumny pozostaje wciąż symetryczny diagram Ferrersa, zatem jego ostatni wiersz i pierwsza kolumna mają także w sumie nieparzystą liczbę krzyżyków ( $2 (a_{k - 2} - 1) - 1$ ), przy czym jest ich mniej niż poprzednio, gdyż $2 (a_{k - 2} - 1) - 1 < 2 a_{k - 1} - 1$ jak że $a_{k - 2} ⩽ a_{k - 1}$ . Tą metodą możemy przekształcić dowolny symetryczny podział liczby $n$ na podział liczby liczby $n$ na składniki parami różne i nieparzyste.

Na odwrót, podział liczby $n$ na różne nieparzyste składniki $b_{0}, \dots, b_{m - 1}$ można "zwinąć" do symetrycznego podziału $n$ "łamiąc w połowie" składniki $b_{i}$ .

Matematyka dyskretna 1/Ćwiczenia 6: Permutacje i podziały: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:37, 11 wrz 2023

Permutacje i Podziały

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 2: / Linia 2: @@
 {{cwiczenie|1|cw 1|
-Policz średnią liczbę cykli w permutacji <math>\displaystyle n</math> zbioru elementowego.
+Policz średnią liczbę cykli w permutacji <math>n</math> zbioru elementowego.
 }}
@@ Linia 15: / Linia 15: @@
-<center><math>\displaystyle \sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n! H_n
+<center><math>\sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n! H_n
 </math></center>
 a suma po lewej stronie to sumaryczna liczba cykli we wszystkich permutacjach zbioru
-<math>\displaystyle n</math>-elementowego, więc średnia liczba cykli
+<math>n</math>-elementowego, więc średnia liczba cykli
 równa jest wartości tej sumy podzielonej
-przez liczbę wszystkich permutacji zbioru <math>\displaystyle n</math>-elementowego, czyli <math>\displaystyle n!</math>:
+przez liczbę wszystkich permutacji zbioru <math>n</math>-elementowego, czyli <math>n!</math>:
-<center><math>\displaystyle \frac{\sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]}{n!}=H_n.
+<center><math>\frac{\sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]}{n!}=H_n</math></center>
-</math></center>
@@ Linia 32: / Linia 31: @@
 {{cwiczenie|2|cw 2|
-Oblicz postać zwartą symbolu <math>\displaystyle \left\{\begin{array} {c}n\\ 4\end{array} \right\}</math>.
+Oblicz postać zwartą symbolu <math>\left\{\begin{array} {c}n\\ 4\end{array} \right\}</math>.
 }}
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Skorzystaj z przestawienia <math>\displaystyle \left\{\begin{array} {c}n\\ k\end{array} \right\}</math>
+Skorzystaj z przestawienia <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}</math>
 w postaci sumy iloczynów współczynników dwumianowych.
 </div></div>
@@ Linia 44: / Linia 43: @@
-<center><math>\displaystyle \aligned \left\{\begin{array} {c}n\\ 4\end{array} \right\}
+<center><math>\begin{align} \left\{\begin{array} {c}n\\ 4\end{array} \right\}
 &=\frac{1}{4!}\sum_{0<i_0<i_1<i_2<n}{n\choose i_2}{i_2\choose i_1}{i_1\choose i_0}\\
 &=\frac{1}{24}\sum_{0<i_1<i_2<n}{n\choose i_2}{i_2\choose i_1}\sum_{0<i_0<i_1}{i_1\choose i_0}\\
@@ Linia 52: / Linia 51: @@
 &=\frac{1}{24}\sum_{0<i_2<n}{n\choose i_2}(3^{i_2}-3\cdot2^{i_2}+3)\\
 &=\frac{1}{24}((4^n-1-3^n)-3(3^n-1-2^n)+3\cdot(2^n-2))\\
-&=\frac{1}{24}(4^n-4\cdot3^n+6\cdot2^n-4).
+&=\frac{1}{24}(4^n-4\cdot3^n+6\cdot2^n-4)
-\endaligned</math></center>
+\end{align}</math></center>
@@ Linia 60: / Linia 59: @@
 {{cwiczenie|3|cw 3|
 Udowodnij wzór na odwracanie liczb Stirlinga,
-czyli że dla dowolnych funkcji <math>\displaystyle f,g</math> określonych na <math>\displaystyle \mathbb{N}</math> zachodzi:
+czyli że dla dowolnych funkcji <math>f,g</math> określonych na <math>\mathbb{N}</math> zachodzi:
-<center><math>\displaystyle f(n)=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ig(i)
+<center><math>f(n)=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ig(i)
 </math></center>
@@ Linia 70: / Linia 69: @@
-<center><math>\displaystyle g(n)=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i).
+<center><math>g(n)=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i)
 </math></center>
@@ Linia 80: / Linia 79: @@
-<center><math>\displaystyle \sum_i\left[\begin{array} {c}m\\ i\end{array} \right]\left\{\begin{array} {c}i\\ n\end{array} \right\}(-1)^{m-i}
+<center><math>\sum_i\left[\begin{array} {c}m\\ i\end{array} \right]\left\{\begin{array} {c}i\\ n\end{array} \right\}(-1)^{m-i}
-=\left\{
+=\begin{cases}
-\begin{array} {cl}
+, & \text{dla } m\neq n,\\
-,&\ \textrm{dla $m\neq n$},\\
+, & \text{dla } m=n
-,&\ \textrm{dla $m=n$}.
+\end{cases}
-\end{array}
-\right.
 </math></center>
@@ Linia 94: / Linia 91: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Pokażemy jedynie implikację w dół (drugą można udowodnić analogicznie).
-Załóżmy zatem, iż <math>\displaystyle f(n)=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ig(i)</math>.
+Załóżmy zatem, iż <math>f(n)=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ig(i)</math>.
 Przekształcając sumę z prawej części tezy otrzymujemy:
-<center><math>\displaystyle \aligned \sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i)
+<center><math>\begin{align} \sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i)
 &=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^i\sum_j\left\{\begin{array} {c}n\\ j\end{array} \right\}(-1)^jg(j)\\
 &=\sum_j\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{i+j}g(j)\\
-&=\sum_j(-1)^{n+j}g(j)\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{n-i}.
+&=\sum_j(-1)^{n+j}g(j)\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{n-i}
-\endaligned</math></center>
+\end{align}</math></center>
@@ Linia 108: / Linia 105: @@
-<center><math>\displaystyle \sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{n-i}
+<center><math>\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{n-i}
-=\left\{
+=\begin{cases}
-\begin{array} {cl}
+, & \mbox{dla } n \neq j,\\
-,&\ \textrm{dla $n\neq j$},\\
+, & \mbox{dla } n=j,
-,&\ \textrm{dla $n=j$},
+\end{cases}
-\end{array}
-\right.
 </math></center>
-więc wszystkie składniki, poza <math>\displaystyle j=n</math>, zewnętrznej sumy zerują się, więc:
+więc wszystkie składniki, poza <math>j=n</math>, zewnętrznej sumy zerują się, więc:
-<center><math>\displaystyle \aligned \sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i)
+<center><math>\begin{align} \sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i)
 &=\sum_j(-1)^{n+j}g(j)\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]\left\{\begin{array} {c}i\\ j\end{array} \right\}(-1)^{n-i}\\
 &=(-1)^{n+n}g(n)\cdot1\\
-&=g(n).
+&=g(n)
-\endaligned</math></center>
+\end{align}</math></center>
@@ Linia 134: / Linia 129: @@
-<center><math>\displaystyle \left\{\begin{array} {c}n+1\\ m+1\end{array} \right\}
+<center><math>\left\{\begin{array} {c}n+1\\ m+1\end{array} \right\}
-=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}.
+=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}
 </math></center>
@@ Linia 142: / Linia 137: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Wyraź liczbę podziałów zbioru <math>\displaystyle (n+1)</math>-elementowego na <math>\displaystyle m+1</math> bloków
+Wyraź liczbę podziałów zbioru <math>(n+1)</math>-elementowego na <math>m+1</math> bloków
 poprzez wyróżnienie jednego z elementów,
 rozważenie w jak licznym bloku może się on znajdować
-i na ile sposobów można podzielić resztę elementów spoza tego bloku na <math>\displaystyle m</math> bloków.
+i na ile sposobów można podzielić resztę elementów spoza tego bloku na <math>m</math> bloków.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Rozważmy podziały zbioru <math>\displaystyle (n+1)</math>-elementowego na <math>\displaystyle m+1</math> bloków.
+Rozważmy podziały zbioru <math>(n+1)</math>-elementowego na <math>m+1</math> bloków.
-Dla ustalenia uwagi, rozważamy zbiór <math>\displaystyle \left\lbrace 1,\ldots,n+1 \right\rbrace</math>.
+Dla ustalenia uwagi, rozważamy zbiór <math>\left\lbrace 1,\ldots,n+1 \right\rbrace</math>.
-Zauważmy, że w dowolnym podziale naszego zbioru na <math>\displaystyle m+1</math> bloków,
+Zauważmy, że w dowolnym podziale naszego zbioru na <math>m+1</math> bloków,
-liczba elementów nie będących w bloku elementu <math>\displaystyle n+1</math>
+liczba elementów nie będących w bloku elementu <math>n+1</math>
-może przybrać wartość <math>\displaystyle k\in\left\lbrace m,\ldots,n \right\rbrace</math>.
+może przybrać wartość <math>k\in\left\lbrace m,\ldots,n \right\rbrace</math>.
-Elementy te możemy wybrać ze zbioru <math>\displaystyle \left\lbrace 1,\ldots,n \right\rbrace</math> na <math>\displaystyle {n\choose k}</math> sposobów
+Elementy te możemy wybrać ze zbioru <math>\left\lbrace 1,\ldots,n \right\rbrace</math> na <math>{n\choose k}</math> sposobów
-i potem podzielić na <math>\displaystyle m</math> bloków na <math>\displaystyle \left\{\begin{array} {c}k\\ m\end{array} \right\}</math> sposobów.
+i potem podzielić na <math>m</math> bloków na <math>\left\{\begin{array} {c}k\\ m\end{array} \right\}</math> sposobów.
-Sumując po wszystkich, możliwych wartościach <math>\displaystyle k</math> wnioskujemy,
+Sumując po wszystkich, możliwych wartościach <math>k</math> wnioskujemy,
-iż liczba podziałów zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+1 \right\rbrace</math> na <math>\displaystyle m+1</math> bloków wynosi
+iż liczba podziałów zbioru <math>\left\lbrace 1,\ldots,n+1 \right\rbrace</math> na <math>m+1</math> bloków wynosi
-<center><math>\displaystyle \sum_{k=m}^n{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}
+<center><math>\sum_{k=m}^n{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}
-=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}.
+=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ m\end{array} \right\}</math></center>
-</math></center>
@@ Linia 171: / Linia 165: @@
-<center><math>\displaystyle \left[\begin{array} {c}n+1\\ m+1\end{array} \right]
+<center><math>\left[\begin{array} {c}n+1\\ m+1\end{array} \right]
-=n!\sum_{k=0}^n \frac{1}{k!}\left[\begin{array} {c}k\\ m\end{array} \right].
+=n!\sum_{k=0}^n \frac{1}{k!}\left[\begin{array} {c}k\\ m\end{array} \right]
 </math></center>
@@ Linia 179: / Linia 173: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Wyraź liczbę permutacji zbioru <math>\displaystyle (n+1)</math>-elementowego o <math>\displaystyle m+1</math> cyklach
+Wyraź liczbę permutacji zbioru <math>(n+1)</math>-elementowego o <math>m+1</math> cyklach
 poprzez wyróżnienie jednego z elementów,
 rozważenie w jak licznym cyklu może się on znajdować
 i na ile sposobów można zbudować ten cykl przy ustalonej liczbie elementów
-oraz na ile sposobów można podzielić resztę zbioru na <math>\displaystyle m</math> cykli.
+oraz na ile sposobów można podzielić resztę zbioru na <math>m</math> cykli.
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Policzmy permutacje zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+1 \right\rbrace</math> o <math>\displaystyle m+1</math> cyklach.
+Policzmy permutacje zbioru <math>\left\lbrace 1,\ldots,n+1 \right\rbrace</math> o <math>m+1</math> cyklach.
-W dowolnej, takiej permutacji liczba elementów nie będących w cyklu z elementem  <math>\displaystyle n+1</math>
+W dowolnej, takiej permutacji liczba elementów nie będących w cyklu z elementem  <math>n+1</math>
-wynosi <math>\displaystyle k\in\left\lbrace m,\ldots,n \right\rbrace</math>.
+wynosi <math>k\in\left\lbrace m,\ldots,n \right\rbrace</math>.
-Elementy te możemy wybrać ze zbioru <math>\displaystyle \left\lbrace 1,\ldots,n \right\rbrace</math>
+Elementy te możemy wybrać ze zbioru <math>\left\lbrace 1,\ldots,n \right\rbrace</math>
-na <math>\displaystyle {n\choose k}</math> sposobów
+na <math>{n\choose k}</math> sposobów
-i podzielić na <math>\displaystyle m</math> cykli na <math>\displaystyle \left[\begin{array} {c}k\\ m\end{array} \right]</math> sposobów.
+i podzielić na <math>m</math> cykli na <math>\left[\begin{array} {c}k\\ m\end{array} \right]</math> sposobów.
-Do tego jeszcze <math>\displaystyle n-k</math> elementów będących w cyklu z elementem <math>\displaystyle n+1</math>
+Do tego jeszcze <math>n-k</math> elementów będących w cyklu z elementem <math>n+1</math>
-może stworzyć ten cykl na <math>\displaystyle (n-k)!</math> sposobów. Podsumowując mamy
+może stworzyć ten cykl na <math>(n-k)!</math> sposobów. Podsumowując mamy
-<center><math>\displaystyle \sum_{k=m}^n{n\choose k}\left[\begin{array} {c}k\\ m\end{array} \right](n-k)!
+<center><math>\sum_{k=m}^n{n\choose k}\left[\begin{array} {c}k\\ m\end{array} \right](n-k)!
 =\sum_{k=m}^n\frac{n!}{k!}\left[\begin{array} {c}k\\ m\end{array} \right]
 =n!\sum_{k=0}^n \frac{1}{k!}\left[\begin{array} {c}k\\ m\end{array} \right]
@@ Linia 203: / Linia 197: @@
-permutacji zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+1 \right\rbrace</math> o <math>\displaystyle m+1</math> cyklach.
+permutacji zbioru <math>\left\lbrace 1,\ldots,n+1 \right\rbrace</math> o <math>m+1</math> cyklach.
 </div></div>
@@ Linia 210: / Linia 204: @@
-<center><math>\displaystyle \left\{\begin{array} {c}m+n+1\\ m\end{array} \right\}
+<center><math>\left\{\begin{array} {c}m+n+1\\ m\end{array} \right\}
-=\sum_{i=0}^m i\left\{\begin{array} {c}n+i\\ i\end{array} \right\}.
+=\sum_{i=0}^m i\left\{\begin{array} {c}n+i\\ i\end{array} \right\}</math></center>
-</math></center>
@@ Linia 218: / Linia 211: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozwiń <math>\displaystyle \left\{\begin{array} {c}n+m+1\\ m\end{array} \right\}</math> używając wielokrotnie
+Rozwiń <math>\left\{\begin{array} {c}n+m+1\\ m\end{array} \right\}</math> używając wielokrotnie
 podstawowej zależności rekurencyjnej dla podziałowych liczb Stirlinga.
 </div></div>
@@ Linia 224: / Linia 217: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Wystarczy pokazać, iż prawa strona równości zlicza podziały
-zbioru <math>\displaystyle (n+m+1)</math>-elementowego na <math>\displaystyle m</math> bloków.
+zbioru <math>(n+m+1)</math>-elementowego na <math>m</math> bloków.
-W dowolnym podziale zbioru <math>\displaystyle \left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace</math>
+W dowolnym podziale zbioru <math>\left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace</math>
-na <math>\displaystyle m</math> bloków:
+na <math>m</math> bloków:
-* albo element <math>\displaystyle n+m+1</math> nie jest sam w swoim bloku.
+* albo element <math>n+m+1</math> nie jest sam w swoim bloku.
-Taki podział jest wyznaczony jednoznacznie przez podział zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+m \right\rbrace</math> na <math>\displaystyle m</math> bloków i dołożenie elementu <math>\displaystyle n+m+1</math> do jednego z <math>\displaystyle m</math> bloków.
+Taki podział jest wyznaczony jednoznacznie przez podział zbioru <math>\left\lbrace 1,\ldots,n+m \right\rbrace</math> na <math>m</math> bloków i dołożenie elementu <math>n+m+1</math> do jednego z <math>m</math> bloków.
-Zatem takich podziałów jest <math>\displaystyle m\left\{\begin{array} {c}n+m\\ m\end{array} \right\}</math>.
+Zatem takich podziałów jest <math>m\left\{\begin{array} {c}n+m\\ m\end{array} \right\}</math>.
-* albo element <math>\displaystyle n+m+1</math> jest sam w swoim bloku.
+* albo element <math>n+m+1</math> jest sam w swoim bloku.
-Wtedy pozostałe <math>\displaystyle n+m</math> elementy są podzielone na <math>\displaystyle m-1</math> bloków. Znów w dowolnym takim podziale:
+Wtedy pozostałe <math>n+m</math> elementy są podzielone na <math>m-1</math> bloków. Znów w dowolnym takim podziale:
-** albo element <math>\displaystyle n+m</math> nie jest sam w swoim bloku. Analogiczne rozumowanie do wcześniejszego wskazuje, że takich podziałów jest <math>\displaystyle (m-1)\left\{\begin{array} {c}n+m-1\\ m-1\end{array} \right\}</math>.
+** albo element <math>n+m</math> nie jest sam w swoim bloku. Analogiczne rozumowanie do wcześniejszego wskazuje, że takich podziałów jest <math>(m-1)\left\{\begin{array} {c}n+m-1\\ m-1\end{array} \right\}</math>.
-** albo element <math>\displaystyle n+m</math> stanowi jednoelementowy blok, itd.
+** albo element <math>n+m</math> stanowi jednoelementowy blok, itd.
-Po <math>\displaystyle m</math> krokach powyższego wywodu otrzymujemy, że jest
+Po <math>m</math> krokach powyższego wywodu otrzymujemy, że jest
-<center><math>\displaystyle n\left\{\begin{array} {c}n+m\\ m\end{array} \right\}+(n-1)\left\{\begin{array} {c}n+m-1\\ m-1\end{array} \right\}+\ldots+1\left\{\begin{array} {c}n+1\\ 1\end{array} \right\}
+<center><math>n\left\{\begin{array} {c}n+m\\ m\end{array} \right\}+(n-1)\left\{\begin{array} {c}n+m-1\\ m-1\end{array} \right\}+\ldots+1\left\{\begin{array} {c}n+1\\ 1\end{array} \right\}
 </math></center>
-podziałów zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+m+1 \right\rbrace</math> na <math>\displaystyle m</math> bloków.
+podziałów zbioru <math>\left\lbrace 1,\ldots,n+m+1 \right\rbrace</math> na <math>m</math> bloków.
 </div></div>
@@ Linia 251: / Linia 244: @@
-<center><math>\displaystyle \left[\begin{array} {c}m+n+1\\ m\end{array} \right]=\sum_{i=0}^m(n+i)\left[\begin{array} {c}n+i\\ i\end{array} \right].
+<center><math>\left[\begin{array} {c}m+n+1\\ m\end{array} \right]=\sum_{i=0}^m(n+i)\left[\begin{array} {c}n+i\\ i\end{array} \right]</math></center>
-</math></center>
@@ Linia 258: / Linia 250: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Rozwiń <math>\displaystyle \left[\begin{array} {c}n+m+1\\ m\end{array} \right]</math> wielokrotnie używając
+Rozwiń <math>\left[\begin{array} {c}n+m+1\\ m\end{array} \right]</math> wielokrotnie używając
 podstawowej zależności rekurencyjnej dla cyklowych liczb Stirlinga.
 </div></div>
@@ Linia 265: / Linia 257: @@
 Analogicznie jak w [[#cw_6|Ćwiczeniu 6]]
 wystarczy wykazać, iż prawa strona tożsamości zlicza permutacje zbioru
-<math>\displaystyle (n+m+1)</math>-elementowego o <math>\displaystyle m</math> cyklach.
+<math>(n+m+1)</math>-elementowego o <math>m</math> cyklach.
-W dowolnej permutacji zbioru <math>\displaystyle \left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace</math> o <math>\displaystyle m</math> cyklach:
+W dowolnej permutacji zbioru <math>\left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace</math> o <math>m</math> cyklach:
-* albo element <math>\displaystyle n+m+1</math> nie jest sam w swoim cyklu.
+* albo element <math>n+m+1</math> nie jest sam w swoim cyklu.
 Dowolną taką permutację jednoznacznie wyznaczamy poprzez permutację zbioru
-<math>\displaystyle \left\lbrace 1,\ldots,n+m \right\rbrace</math> o <math>\displaystyle m</math> cyklach
+<math>\left\lbrace 1,\ldots,n+m \right\rbrace</math> o <math>m</math> cyklach
-z dołożonym elementem <math>\displaystyle n+m+1</math> na jednej z <math>\displaystyle n+m</math> możliwych pozycji.
+z dołożonym elementem <math>n+m+1</math> na jednej z <math>n+m</math> możliwych pozycji.
-Zatem takich permutacji jest dokładnie <math>\displaystyle (n+m)\left[\begin{array} {c}n+m\\ m\end{array} \right]</math>.
+Zatem takich permutacji jest dokładnie <math>(n+m)\left[\begin{array} {c}n+m\\ m\end{array} \right]</math>.
-* albo element <math>\displaystyle n+m+1</math> stanowi jednoelementowy cykl.
+* albo element <math>n+m+1</math> stanowi jednoelementowy cykl.
-Wtedy elementy <math>\displaystyle 1,\ldots,n+m</math> są rozłożone w <math>\displaystyle m-1</math> cyklach. Znów w dowolnej takiej permutacji:
+Wtedy elementy <math>1,\ldots,n+m</math> są rozłożone w <math>m-1</math> cyklach. Znów w dowolnej takiej permutacji:
-** albo element <math>\displaystyle n+m</math> nie jest sam w swoim cyklu.
+** albo element <math>n+m</math> nie jest sam w swoim cyklu.
-Wtedy rozumując analogicznie jak wcześniej wiemy, iż takich permutacji jest <math>\displaystyle (n+m-1)\left[\begin{array} {c}n+m-1\\ m-1\end{array} \right]</math>.
+Wtedy rozumując analogicznie jak wcześniej wiemy, iż takich permutacji jest <math>(n+m-1)\left[\begin{array} {c}n+m-1\\ m-1\end{array} \right]</math>.
-** albo element <math>\displaystyle n+m</math> stanowi jednoelementowy cykl, itd.
+** albo element <math>n+m</math> stanowi jednoelementowy cykl, itd.
-Po <math>\displaystyle m</math> krokach powyższy wywód daje
+Po <math>m</math> krokach powyższy wywód daje
-<center><math>\displaystyle (n+m)\left[\begin{array} {c}n+m\\ m\end{array} \right]+
+<center><math>(n+m)\left[\begin{array} {c}n+m\\ m\end{array} \right]+
 (n+m-1)\left[\begin{array} {c}n+m-1\\ m-1\end{array} \right]+\ldots+
 n\left[\begin{array} {c}n\\ 0\end{array} \right]
@@ Linia 288: / Linia 280: @@
-permutacji zbioru <math>\displaystyle \left\lbrace 1,\ldots,n+m+1 \right\rbrace</math> o <math>\displaystyle m</math> cyklach.
+permutacji zbioru <math>\left\lbrace 1,\ldots,n+m+1 \right\rbrace</math> o <math>m</math> cyklach.
 </div></div>
@@ Linia 295: / Linia 287: @@
-<center><math>\displaystyle \left\{\begin{array} {c}n\\ l+m\end{array} \right\}{l+m\choose l}
+<center><math>\left\{\begin{array} {c}n\\ l+m\end{array} \right\}{l+m\choose l}
-=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ l\end{array} \right\}\left\{\begin{array} {c}n-k\\ m\end{array} \right\}.
+=\sum_k{n\choose k}\left\{\begin{array} {c}k\\ l\end{array} \right\}\left\{\begin{array} {c}n-k\\ m\end{array} \right\}</math></center>
-</math></center>
@@ Linia 303: / Linia 294: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
-Zauważ, że obie strony równości to liczba podziałów zbioru <math>\displaystyle n</math>-elementowego
+Zauważ, że obie strony równości to liczba podziałów zbioru <math>n</math>-elementowego
-na <math>\displaystyle l+m</math> bloków, przy czym <math>\displaystyle l</math> bloków jest wyróżnionych (pomalowanych na czerwono).
+na <math>l+m</math> bloków, przy czym <math>l</math> bloków jest wyróżnionych (pomalowanych na czerwono).
 </div></div>
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Lewą stronę tożsamości możemy interpretować jako liczbę podziałów
-zbioru <math>\displaystyle n</math>-elementowego na <math>\displaystyle l+m</math> bloków, w których <math>\displaystyle l</math> bloków jest wyróżnionych
+zbioru <math>n</math>-elementowego na <math>l+m</math> bloków, w których <math>l</math> bloków jest wyróżnionych
 (pomalowanych na czerwono).
 Policzmy te specjalne podziały inną metodą.
-Wybierzmy najpierw <math>\displaystyle k</math>-elementowy podzbiór zbioru <math>\displaystyle n</math>-elementowego
+Wybierzmy najpierw <math>k</math>-elementowy podzbiór zbioru <math>n</math>-elementowego
-(na jeden z <math>\displaystyle {n\choose k}</math> sposobów),
+(na jeden z <math>{n\choose k}</math> sposobów),
 którego elementy będą stanowić wyróżnione bloki.
-Wybrany <math>\displaystyle k</math>-elementowy podzbiór możemy podzielić
+Wybrany <math>k</math>-elementowy podzbiór możemy podzielić
-na docelowe <math>\displaystyle l</math> wyróżnionych bloków
+na docelowe <math>l</math> wyróżnionych bloków
-na <math>\displaystyle \left\{\begin{array} {c}k\\ l\end{array} \right\}</math> sposobów.
+na <math>\left\{\begin{array} {c}k\\ l\end{array} \right\}</math> sposobów.
-Pozostałe, zaś <math>\displaystyle n-k</math> elementów możemy podzielić na <math>\displaystyle m</math>,
+Pozostałe, zaś <math>n-k</math> elementów możemy podzielić na <math>m</math>,
-(nie czerwonych) bloków na <math>\displaystyle \left\{\begin{array} {c}n-k\\ m\end{array} \right\}</math> sposobów.
+(nie czerwonych) bloków na <math>\left\{\begin{array} {c}n-k\\ m\end{array} \right\}</math> sposobów.
-Zatem dla ustalonego <math>\displaystyle k</math> mamy
+Zatem dla ustalonego <math>k</math> mamy
-<math>\displaystyle \displaystyle{{n\choose k}\left\{\begin{array} {c}k\\ l\end{array} \right\} \left\{\begin{array} {c}n-k\\ m\end{array} \right\}}</math>
+<math>{{n\choose k}\left\{\begin{array} {c}k\\ l\end{array} \right\} \left\{\begin{array} {c}n-k\\ m\end{array} \right\}}</math>
-podziałów zbioru <math>\displaystyle n</math>-elementowego na <math>\displaystyle l+m</math> bloków,
+podziałów zbioru <math>n</math>-elementowego na <math>l+m</math> bloków,
-przy czym wyróżnione <math>\displaystyle l</math> bloków ma w sumie <math>\displaystyle k</math> elementów.
+przy czym wyróżnione <math>l</math> bloków ma w sumie <math>k</math> elementów.
-Sumując teraz po wszystkich możliwych wartościach <math>\displaystyle k</math> możemy zakończyć dowód.
+Sumując teraz po wszystkich możliwych wartościach <math>k</math> możemy zakończyć dowód.
 </div></div>
 {{cwiczenie|9|cw 9|
-Podział liczby <math>\displaystyle n</math> na sumę jest symetryczny,
+Podział liczby <math>n</math> na sumę jest symetryczny,
-jeśli odwracając jego diagram Ferrersa o <math>\displaystyle 90</math> stopni otrzymamy ten sam diagram.
+jeśli odwracając jego diagram Ferrersa o <math>90</math> stopni otrzymamy ten sam diagram.
 }}
-{{przyklad|||
+[[File:MD1-SW 6.7.mp4|250x250px|thumb|left|MD1-SW 6.7.swf]]
+[[File:MD1-SW 6.8.mp4|250x250px|thumb|right|MD1-SW 6.8.swf]]
-<center><math>\displaystyle 6+5+3+2+2+1=19.
+{{przyklad|||
-</math></center>
-* <math>\displaystyle 6,5,3,2,2,1</math> jest podziałem symetrycznym <math>\displaystyle 19</math>.
-[[Rysunek: 6.7 Szkic na kartce.]]
+<center>
+<math>6+5+3+2+2+1=19</math>
+</center>
-<center><math>\displaystyle 5+2+1=8.
+* <math>6,5,3,2,2,1</math> jest podziałem symetrycznym <math>19</math>.
-</math></center>
-* <math>\displaystyle 5,2,1</math> nie jest podziałem symetrycznym <math>\displaystyle 8</math>.
+<center>
+<math>5+2+1=8</math>
+</center>
-[[Rysunek: 6.8 Szkic na kartce.]]
+* <math>5,2,1</math> nie jest podziałem symetrycznym <math>8</math>.
 }}
-Pokaż, że liczba podziałów symetrycznych liczby <math>\displaystyle n</math>
+Pokaż, że liczba podziałów symetrycznych liczby <math>n</math>
-pokrywa się z liczbą podziałów liczby <math>\displaystyle n</math> na różne i nieparzyste składniki.
+pokrywa się z liczbą podziałów liczby <math>n</math> na różne i nieparzyste składniki.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
@@ Linia 364: / Linia 355: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
-Rozważmy <math>\displaystyle n=a_0+\ldots+a_{k-1}</math> symetryczny podział liczby <math>\displaystyle n</math> na sumę.
+[[File:MD1-SW 6.9.mp4|250x250px|thumb|right|MD1-SW 6.9.swf]]
+Rozważmy <math>n=a_0+\ldots+a_{k-1}</math> symetryczny podział liczby <math>n</math> na sumę.
 Z symetryczności wiemy,
-iż liczba krzyżyków w ostatnim wierszu (tzn. liczba <math>\displaystyle a_{k-1}</math>)
+iż liczba krzyżyków w ostatnim wierszu (tzn. liczba <math>a_{k-1}</math>)
 jest równa liczbie krzyżyków w pierwszej kolumnie,
 a ponieważ mają one jeden krzyżyk wspólny to w sumie jest ich nieparzyście wiele
-(<math>\displaystyle 2a_{k-1}-1</math>).
+(<math>2a_{k-1}-1</math>).
 Po wycięciu ostatniego wiersza i pierwszej kolumny pozostaje
 wciąż symetryczny diagram Ferrersa,
 zatem jego ostatni wiersz i pierwsza kolumna
-mają także w sumie nieparzystą liczbę krzyżyków (<math>\displaystyle 2(a_{k-2}-1)-1</math>),
+mają także w sumie nieparzystą liczbę krzyżyków (<math>2(a_{k-2}-1)-1</math>),
-przy czym jest ich mniej niż poprzednio, gdyż <math>\displaystyle 2(a_{k-2}-1)-1<2a_{k-1}-1</math>
+przy czym jest ich mniej niż poprzednio, gdyż <math>2(a_{k-2}-1)-1<2a_{k-1}-1</math>
-jak że <math>\displaystyle a_{k-2}\leqslant a_{k-1}</math>.
+jak że <math>a_{k-2}\leqslant a_{k-1}</math>.
-Tą metodą możemy przekształcić dowolny symetryczny podział liczby <math>\displaystyle n</math>
+Tą metodą możemy przekształcić dowolny symetryczny podział liczby <math>n</math>
-na podział liczby liczby <math>\displaystyle n</math> na składniki parami różne i nieparzyste.
+na podział liczby liczby <math>n</math> na składniki parami różne i nieparzyste.
-[[Rysunek: 6.9 Szkic na kartce.]]
-Na odwrót, podział liczby <math>\displaystyle n</math> na różne nieparzyste składniki <math>\displaystyle b_0,\ldots,b_{m-1}</math>
+Na odwrót, podział liczby <math>n</math> na różne nieparzyste składniki <math>b_0,\ldots,b_{m-1}</math>
-można "zwinąć" do symetrycznego podziału <math>\displaystyle n</math> "łamiąc w połowie" składniki <math>\displaystyle b_i</math>.
+można "zwinąć" do symetrycznego podziału <math>n</math> "łamiąc w połowie" składniki <math>b_i</math>.
 </div></div>