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}$ .

@@ Linia 25: / Linia 25: @@
-<center><math>\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 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)
 \end{align}</math></center>
@@ Linia 70: / Linia 69: @@
-<center><math>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 83: / Linia 82: @@
 =\begin{cases}
 , & \text{dla } m\neq n,\\
-, & \text{dla } m=n.
+, & \text{dla } m=n
 \end{cases}
 </math></center>
@@ Linia 99: / Linia 98: @@
 &=\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}
 \end{align}</math></center>
@@ Linia 120: / Linia 119: @@
 &=\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)
 \end{align}</math></center>
@@ Linia 131: / Linia 130: @@
 <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 157: / Linia 156: @@
 <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 168: / Linia 166: @@
 <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 207: / Linia 205: @@
 <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 247: / Linia 244: @@
-<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].
+<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 292: / Linia 288: @@
 <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 319: / Linia 314: @@
 Zatem dla ustalonego <math>k</math> mamy
-<math>\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>n</math>-elementowego na <math>l+m</math> bloków,
 przy czym wyróżnione <math>l</math> bloków ma w sumie <math>k</math> elementów.
@@ Linia 338: / Linia 333: @@
 <center>
-<math>6+5+3+2+2+1=19.
+<math>6+5+3+2+2+1=19</math>
-</math>
 </center>
@@ Linia 345: / Linia 339: @@
 <center>
-<math>5+2+1=8.
+<math>5+2+1=8</math>
-</math>
 </center>

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