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

From Studia Informatyczne

[Edytuj]

Permutacje i Podziały

Ćwiczenie 1

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

Wskazówka

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

Rozwiązanie

Ponieważ


\displaystyle \sum_{i=0}^ni\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 \displaystyle n-elementowego, więc średnia liczba cykli równa jest wartości tej sumy podzielonej przez liczbę wszystkich permutacji zbioru \displaystyle n-elementowego, czyli \displaystyle n!:


\displaystyle \frac{\sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]}{n!}=H_n.

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie


\displaystyle \aligned \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}\\ &=\frac{1}{24}\sum_{0<i_1<i_2<n}{n\choose i_2}{i_2\choose i_1}(2^{i_1}-2)\\ &=\frac{1}{24}\sum_{0<i_2<n}{n\choose i_2}\left(\sum_{0<i_1<i_2}{i_2\choose i_1}2^{i_1}-2\sum_{0<i_1<i_2}{i_2\choose i_1}\right)\\ &=\frac{1}{24}\sum_{0<i_2<n}{n\choose i_2}((3^{i_2}-1-2^{i_2})-2(2^{i_2}-2))\\ &=\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). \endaligned

Ćwiczenie 3

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


\displaystyle f(n)=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ig(i)


wtedy i tylko wtedy, gdy


\displaystyle g(n)=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^if(i).


Wskazówka

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


\displaystyle \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{array} {cl} 0,&\ \textrm{dla $m\neq n$},\\ 1,&\ \textrm{dla $m=n$}. \end{array} \right.

Rozwiązanie

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


\displaystyle \aligned \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}. \endaligned


Ale


\displaystyle \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{array} {cl} 0,&\ \textrm{dla $n\neq j$},\\ 1,&\ \textrm{dla $n=j$}, \end{array} \right.


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


\displaystyle \aligned \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). \endaligned

Ćwiczenie 4

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


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


Wskazówka

Wyraź liczbę podziałów zbioru \displaystyle (n+1)-elementowego na \displaystyle 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 \displaystyle m bloków.

Rozwiązanie

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


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

Ćwiczenie 5

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


\displaystyle \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 \displaystyle (n+1)-elementowego o \displaystyle 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 \displaystyle m cykli.

Rozwiązanie

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


\displaystyle \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]


permutacji zbioru \displaystyle \left\lbrace 1,\ldots,n+1 \right\rbrace o \displaystyle m+1 cyklach.

Ćwiczenie 6

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


\displaystyle \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ń \displaystyle \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 \displaystyle (n+m+1)-elementowego na \displaystyle m bloków. W dowolnym podziale zbioru \displaystyle \left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace na \displaystyle m bloków:

  • albo element \displaystyle n+m+1 nie jest sam w swoim bloku.

Taki podział jest wyznaczony jednoznacznie przez podział zbioru \displaystyle \left\lbrace 1,\ldots,n+m \right\rbrace na \displaystyle m bloków i dołożenie elementu \displaystyle n+m+1 do jednego z \displaystyle m bloków.

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

  • albo element \displaystyle n+m+1 jest sam w swoim bloku.

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

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

Po \displaystyle m krokach powyższego wywodu otrzymujemy, że jest


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


podziałów zbioru \displaystyle \left\lbrace 1,\ldots,n+m+1 \right\rbrace na \displaystyle m bloków.

Ćwiczenie 7

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


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


Wskazówka

Rozwiń \displaystyle \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 \displaystyle (n+m+1)-elementowego o \displaystyle m cyklach. W dowolnej permutacji zbioru \displaystyle \left\lbrace 1,\ldots,n,n+1,\ldots,n+m,n+m+1 \right\rbrace o \displaystyle m cyklach:

  • albo element \displaystyle n+m+1 nie jest sam w swoim cyklu.

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

  • albo element \displaystyle n+m+1 stanowi jednoelementowy cykl.

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

    • albo element \displaystyle n+m nie jest sam w swoim cyklu.

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

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

Po \displaystyle m krokach powyższy wywód daje


\displaystyle (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]


permutacji zbioru \displaystyle \left\lbrace 1,\ldots,n+m+1 \right\rbrace o \displaystyle m cyklach.

Ćwiczenie 8

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


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


Wskazówka

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

Rozwiązanie

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

Policzmy te specjalne podziały inną metodą.

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

Zatem dla ustalonego \displaystyle k mamy

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

Ćwiczenie 9

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



MD1-SW 6.7.swf


MD1-SW 6.8.swf

Przykład

\displaystyle 6+5+3+2+2+1=19.

  • \displaystyle 6,5,3,2,2,1 jest podziałem symetrycznym \displaystyle 19.

\displaystyle 5+2+1=8.

  • \displaystyle 5,2,1 nie jest podziałem symetrycznym \displaystyle 8.

Pokaż, że liczba podziałów symetrycznych liczby \displaystyle n pokrywa się z liczbą podziałów liczby \displaystyle 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>

MD1-SW 6.9.swf


Rozważmy \displaystyle n=a_0+\ldots+a_{k-1} symetryczny podział liczby \displaystyle n na sumę. Z symetryczności wiemy, iż liczba krzyżyków w ostatnim wierszu (tzn. liczba \displaystyle 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 (\displaystyle 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 (\displaystyle 2(a_{k-2}-1)-1), przy czym jest ich mniej niż poprzednio, gdyż \displaystyle 2(a_{k-2}-1)-1<2a_{k-1}-1 jak że \displaystyle a_{k-2}\leqslant a_{k-1}. Tą metodą możemy przekształcić dowolny symetryczny podział liczby \displaystyle n na podział liczby liczby \displaystyle n na składniki parami różne i nieparzyste.

Na odwrót, podział liczby \displaystyle n na różne nieparzyste składniki \displaystyle b_0,\ldots,b_{m-1}

można "zwinąć" do symetrycznego podziału \displaystyle n "łamiąc w połowie" składniki \displaystyle b_i.

Źródło: "http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/%C4%86wiczenia_6:_Permutacje_i_podzia%C5%82y"