Matematyka dyskretna 1/Ćwiczenia 6: Permutacje i podziały

Permutacje i Podziały

Ćwiczenie 1

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

Wskazówka

Skorzystaj ze związku między liczbami Stirlinga dla cykli i liczbami harmonicznymi.

Rozwiązanie

Ponieważ

$\sum _{i=0}^{n}i\left[\begin{array}{c}n\\ i\end{array}\right]=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\left[\begin{array}{c}n\\ i\end{array}\right]}{n!}=H_n.$

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

$\begin{array}{rl}\left\{\begin{array}{c}n\\ 4\end{array}\right\}& =\frac{1}{4!}\sum _{0<i_0<i_1<i_2<n}(\genfrac{}{}{0ex}{}{n}{i_2})(\genfrac{}{}{0ex}{}{i_2}{i_1})(\genfrac{}{}{0ex}{}{i_1}{i_0})\\ & =\frac{1}{24}\sum _{0<i_1<i_2<n}(\genfrac{}{}{0ex}{}{n}{i_2})(\genfrac{}{}{0ex}{}{i_2}{i_1})\sum _{0<i_0<i_1}(\genfrac{}{}{0ex}{}{i_1}{i_0})\\ & =\frac{1}{24}\sum _{0<i_1<i_2<n}(\genfrac{}{}{0ex}{}{n}{i_2})(\genfrac{}{}{0ex}{}{i_2}{i_1})(2^{i_1}-2)\\ & =\frac{1}{24}\sum _{0<i_2<n}(\genfrac{}{}{0ex}{}{n}{i_2})(\sum _{0<i_1<i_2}(\genfrac{}{}{0ex}{}{i_2}{i_1})2^{i_1}-2\sum _{0<i_1<i_2}(\genfrac{}{}{0ex}{}{i_2}{i_1}))\\ & =\frac{1}{24}\sum _{0<i_2<n}(\genfrac{}{}{0ex}{}{n}{i_2})((3^{i_2}-1-2^{i_2})-2(2^{i_2}-2))\\ & =\frac{1}{24}\sum _{0<i_2<n}(\genfrac{}{}{0ex}{}{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{array}$

Ćwiczenie 3

Udowodnij wzór na odwracanie liczb Stirlinga, czyli że dla dowolnych funkcji $f,g$ określonych na $\mathbb{\mathbb{N}}$ zachodzi:

$f(n)=\sum _i\left\{\begin{array}{c}n\\ i\end{array}\right\}(-1{)}^{i}g(i)$

wtedy i tylko wtedy, gdy

$g(n)=\sum _i\left[\begin{array}{c}n\\ i\end{array}\right](-1{)}^{i}f(i).$

Wskazówka

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

$\sum _i\left[\begin{array}{c}m\\ i\end{array}\right]\left\{\begin{array}{c}i\\ n\end{array}\right\}(-1{)}^{m-i}=\{\begin{array}{ll}0,& \text{dla }m\ne n,\\ 1,& \text{dla }m=n.\end{array}$

Rozwiązanie

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

$\begin{array}{rl}\sum _i\left[\begin{array}{c}n\\ i\end{array}\right](-1{)}^{i}f(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{)}^{j}g(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}.\end{array}$

Ale

$\sum _i\left[\begin{array}{c}n\\ i\end{array}\right]\left\{\begin{array}{c}i\\ j\end{array}\right\}(-1{)}^{n-i}=\{\begin{array}{ll}0,& \text{dla }n\ne j,\\ 1,& \text{dla }n=j,\end{array}$

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

$\begin{array}{rl}\sum _i\left[\begin{array}{c}n\\ i\end{array}\right](-1{)}^{i}f(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)\cdot 1\\ & =g(n).\end{array}$

Ćwiczenie 4

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

$\left\{\begin{array}{c}n+1\\ m+1\end{array}\right\}=\sum _k(\genfrac{}{}{0ex}{}{n}{k})\left\{\begin{array}{c}k\\ m\end{array}\right\}.$

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 $(\genfrac{}{}{0ex}{}{n}{k})$ sposobów i potem podzielić na $m$ bloków na $\left\{\begin{array}{c}k\\ m\end{array}\right\}$ 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(\genfrac{}{}{0ex}{}{n}{k})\left\{\begin{array}{c}k\\ m\end{array}\right\}=\sum _k(\genfrac{}{}{0ex}{}{n}{k})\left\{\begin{array}{c}k\\ m\end{array}\right\}.$

Ćwiczenie 5

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

$\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].$

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 $(\genfrac{}{}{0ex}{}{n}{k})$ sposobów i podzielić na $m$ cykli na $\left[\begin{array}{c}k\\ m\end{array}\right]$ 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(\genfrac{}{}{0ex}{}{n}{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]$

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

Ćwiczenie 6

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

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

Wskazówka

Rozwiń $\left\{\begin{array}{c}n+m+1\\ m\end{array}\right\}$ 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\left\{\begin{array}{c}n+m\\ m\end{array}\right\}$.

• 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)\left\{\begin{array}{c}n+m-1\\ m-1\end{array}\right\}$.
  • albo element $n+m$ stanowi jednoelementowy blok, itd.

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

$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\}+\dots +1\left\{\begin{array}{c}n+1\\ 1\end{array}\right\}$

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

Ćwiczenie 7

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

$\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].$

Wskazówka

Rozwiń $\left[\begin{array}{c}n+m+1\\ m\end{array}\right]$ 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)\left[\begin{array}{c}n+m\\ m\end{array}\right]$.

• 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)\left[\begin{array}{c}n+m-1\\ m-1\end{array}\right]$.

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

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

$(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]+\dots +n\left[\begin{array}{c}n\\ 0\end{array}\right]$

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

Ćwiczenie 8

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

$\left\{\begin{array}{c}n\\ l+m\end{array}\right\}(\genfrac{}{}{0ex}{}{l+m}{l})=\sum _k(\genfrac{}{}{0ex}{}{n}{k})\left\{\begin{array}{c}k\\ l\end{array}\right\}\left\{\begin{array}{c}n-k\\ m\end{array}\right\}.$

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 $(\genfrac{}{}{0ex}{}{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 $\left\{\begin{array}{c}k\\ l\end{array}\right\}$ sposobów. Pozostałe, zaś $n-k$ elementów możemy podzielić na $m$, (nie czerwonych) bloków na $\left\{\begin{array}{c}n-k\\ m\end{array}\right\}$ sposobów.

Zatem dla ustalonego $k$ mamy $(\genfrac{}{}{0ex}{}{n}{k})\left\{\begin{array}{c}k\\ l\end{array}\right\}\left\{\begin{array}{c}n-k\\ m\end{array}\right\}$ 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.

<flashwrap>file=MD1-SW 6.7.swf|size=small</flashwrap>

<div.thumbcaption>MD1-SW 6.7.swf

<flashwrap>file=MD1-SW 6.8.swf|size=small</flashwrap>

<div.thumbcaption>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

Zauważ, że w diagramie Ferrersa, w podziale symetrycznym liczba krzyżyków znajdujących się w pierwszej kolumnie lub/i ostatnim wierszu jest nieparzysta.

Rozwiązanie

<flashwrap>file=MD1-SW 6.9.swf|size=small</flashwrap>

<div.thumbcaption>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 ($2a_{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<2a_{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$.