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

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

Permutacje i Podziały

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia