[MIX][Kombinatoryka] Tożsamości kombinatoryczne

[KPR]

Tak sobie znalazłem trochę tożsamości. Polecam oczywiście kombinatoryczne rozwiązania.

1.\(\displaystyle{ \sum\limits_{i=0}^{n}\frac1{i+1}{n\choose i}=\frac1{n+1}\left(2^{n+1}-1\right)}\)

2.\(\displaystyle{ \sum\limits_{i=1}^{n}(-1)^{n+1}\frac1i{n\choose i}=\sum\limits_{i=1}^{n}\frac1i}\)

3.\(\displaystyle{ \sum\limits_{i=0}^{n-1}\sum\limits_{j=i+1}^{n+1} {n+1\choose j}{n\choose i}=2^{2n}-1}\)

4.\(\displaystyle{ \sum\limits_{i=1}^{n} (-1)^i{n\choose i}\frac1{i+m+1}=\sum\limits_{i=1}^{m} (-1)^i{m\choose i}\frac1{i+n+1}}\)

5.\(\displaystyle{ \sum\limits_{i=0}^{n-1}(i+1){n\choose i}a_{n-i}=2\cdot n!-n-1}\), gdzie \(\displaystyle{ a_n=\sum\limits_{i=0}^{n}(-1)^i\frac{n!}{i!}}\)

6.\(\displaystyle{ \sum\limits_{i=r}^{n} (-1)^{i-r}{i\choose r}{n-i\choose i}2^{n-2i}={n+1\choose 2r+1}}\)

7.\(\displaystyle{ \sum\limits_{i=0}^n i{n\choose i}^2=n{2n-1\choose n-1}}\)

8.\(\displaystyle{ \sum\limits_{i=0}^{n-1} (-1)^i{n \choose i}(2^{n-i}-1)^m=\sum\limits_{i=0}^{m-1} (-1)^i{m \choose i}(2^{m-i}-1)^n}\)

9.\(\displaystyle{ \sum\limits_{i=0}^{n}{n\choose i}{i\choose m}(-1)^i=(-1)^n\delta_{n,m}}\), gdzie \(\displaystyle{ \delta_{m,n}=\begin{cases}1,\mathrm{ gdy }\,m=n \\ 0, \mathrm{ gdy }\,m\neq n\end{cases}}\)

10.\(\displaystyle{ \sum\limits_{i=0}^{n}{n\choose i}(n-i)^{n+1}(-1)^i=n\frac{(n+1)!}2}\)

11.\(\displaystyle{ \sum\limits_{x_1\geq 0}\sum\limits_{x_2\geq 0}\dots\sum\limits_{x_0=x_t\geq 0}\prod\limits_{i=1}^t {n-x_{i-1}\choose x_i}=\frac{f_{tn+t}}{f_{t}}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego.

12.\(\displaystyle{ \sum\limits_{x_1\geq 0}\sum\limits_{x_2\geq 0}\dots\sum\limits_{x_t\geq 0}\left(\prod\limits_{i=1}^t {n-x_{i-1}\choose x_i}g_1^{x_1}g_2^{n-x_1}\right)=(g_2f_{t+1})^cg_{t+2}^{n-c}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego, \(\displaystyle{ g}\)-dowolnym ciągiem spełniającym rekurencję \(\displaystyle{ g_n=g_{n-1}+g_{n-2}}\) dla \(\displaystyle{ n>2}\) oraz \(\displaystyle{ x_0=n-c}\).

Znalazłem jeszcze jedną fajną tożsamość, to pomyślałem, ze dorzucę:
13.\(\displaystyle{ \sum\limits_{i\geq 0}\sum\limits_{j\geq 0}{i+j\choose i}{n-i-j\choose j}f_{t-1}^if_t^{2j-1}f_{t+1}^{n-2j-i}=f_{(n+1)t}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego.

[marcin_smu]

1:    

Pomnóżmy obie strony przez \(\displaystyle{ n+1}\) i dodajmy \(\displaystyle{ 1}\). Otrzymujemy:
\(\displaystyle{ \sum_{i=0}^{n+1} {n+1 \choose i} = 2^{n+1}}\)
I teraz, żeby nie było że nie ma historyjki:
Pewnego dnia w Serockim lesie mały Świstak zastanawia się na ile sposobów może wybrać podzbiór ze zbioru o \(\displaystyle{ n+1}\) elementach. Przypomniał sobie wzór na liczbę sposobów wybrania podzbioru o danej liczbie elementów tak zwany dwumian Newtona. Zapisał więc szukaną liczbę sposobów, jako sumę dwumianów po każdej możliwej liczbie elementów(lewa strona równości). Jednak w praktyce wzór małego Świstaka się nie sprawdzał. Wynik liczyło się dość długo nawet dla bardzo małych zbiorów. Zrezygnowany poszedł, więc do mamy Jeża. Opowiedział o swoim problemie. Rozmowie przysłuchiwali się mały Jeż i mały Zając zajęci jakąś dziwną grą karcianą. Po chwili jeż krzykną:
-Tych zbiorów jest \(\displaystyle{ 2^{n+1}}\)
-Przecież dla każdego z \(\displaystyle{ n+1}\) elementów masz 2 możliwości: wybrać go bądź nie. - dokończył Zając.

Ale się rozpisałem. xD

[Swistak]

zad. 7:    

Rozpatrujemy liczbę wyborów w następującej sytuacji:
Mamy sobie zbiór \(\displaystyle{ n}\) chłopców i \(\displaystyle{ n}\) dziewczynek. Chcemy z tych wszystkich osób wybrać \(\displaystyle{ n}\)-osobową grupę, a w niej lidera, przy czym zgodnie z prawami natury liderem grupy musi być oczywiście chłopiec.
Możemy to policzyć na 2 sposoby.
Wybierzemy najpierw lidera, możemy to zrobić na \(\displaystyle{ n}\) sposobów. Pozostaje dobrać z reszty \(\displaystyle{ n-1}\) osób, co czynimy na \(\displaystyle{ {2n-1 \choose n-1}}\), zatem łącznie mamy \(\displaystyle{ n{2n-1 \choose n-1}}\) sposobów.
Możemy to zrobić trochę inaczej. Najpierw wybieramy

Ukryta treść:    

i

chłopców, a spośród nich lidera, co czynimy na \(\displaystyle{ i {n \choose i}}\) sposobów i pozostaje nam odrzucić \(\displaystyle{ i}\) dziewczynek, które nie zostaną wybrane, co czynimy na \(\displaystyle{ {n \choose i}}\) sposobów, zatem łącznie mamy sum_{i=0}^{n} i{n choose i}^2[/latex] sposobów.
c.K.u.z.s.

[Damianito]

zad.5:    

Skorzystamy z faktu, że dla \(\displaystyle{ n \geq 0}\) liczba \(\displaystyle{ a_n}\) jest liczbą permutacji \(\displaystyle{ n}\) elementów bez punktów stałych (najprościej to wykazać, zapisując zasadę włączeń i wyłączeń dla sumy zbiorów zdefiniowanych jako \(\displaystyle{ A_i}\) - zbiór permutacji mających \(\displaystyle{ i}\) jako punkt stały)

Dodajemy obustronnie \(\displaystyle{ n+1}\) i mamy dowieść, że
\(\displaystyle{ \sum_{i=0}^{n}(i+1) {n \choose i} a_{n-i} = 2n!}\)

Lewa strona odpowiada liczbie permutacji z wyróżnionym punktem stałym lub niewyróżnionym niczym (tj. liczbie par postaci (permutacja, indeks pewnego punktu stałego permutacji lub liczba 0) ), ponieważ możemy dla ustalonej liczby punktów stałych \(\displaystyle{ i}\) wybrać na \(\displaystyle{ {n \choose i}}\) sposobów punkty stałe, resztę permutacji na \(\displaystyle{ a_{n-i}}\) sposobów, a poza tym wyróżnić (lub nie) punkt stały na \(\displaystyle{ i+1}\) sposobów.

Z drugiej strony, par postaci (permutacja, 0) jest \(\displaystyle{ n!}\) a pary postaci (permutacja, punkt stały) możemy zliczyć, ustalając wyróżniony punkt stały na \(\displaystyle{ n}\) sposobów, a następnie resztę permutacji na sposobów \(\displaystyle{ (n-1)!}\), czyli łącznie tych par jest \(\displaystyle{ n!+n \cdot (n-1)! = 2n!}\), czyli prawa strona równości.

zad.9:    

Przy \(\displaystyle{ m>n}\) lewa strona jest sumą zer, bo \(\displaystyle{ {i \choose m}=0}\) czyli tożsamość się zgadza. Dla \(\displaystyle{ m=n}\) jedynym \(\displaystyle{ i}\) wśród indeksów sumy, dla którego \(\displaystyle{ {i \choose m}\neq 0}\) jest \(\displaystyle{ i=m=n}\), więc lewa strona wynosi \(\displaystyle{ (-1)^n}\) i tożsamość się zgadza. Pozostaje przypadek \(\displaystyle{ m<n}\) i ograniczając się do niezerowych składników lewej sumy, dostajemy do wykazania tożsamość

\(\displaystyle{ \sum_{i=m}^{n} {n \choose i} {i \choose m} (-1)^i = 0}\)

Którą wygodniej rozważać przepisaną jaką:

\(\displaystyle{ \sum_{i=0}^{n-m} {n \choose {i+m}} {{i+m} \choose m} (-1)^i = 0}\) (czynnik \(\displaystyle{ (-1)^m}\) pominęliśmy)

Dla danego \(\displaystyle{ m < n}\) możemy zastanowić się nad problemem KG OMZ - Komitetu Głównego Olimpiady Matematycznej Ziemi, w której udział bierze \(\displaystyle{ n}\) uczestników i \(\displaystyle{ m}\) najlepszych z nich weźmie udział w Międzygalaktycznej Olimpiadzie Matematycznej (ang. Intergalactic Mathematical Olympiad) a inna reprezentacja uczestników, rozłączna z tą na IMO, ma zostać wysłana na Zawody Matematyczne Planet Wewnętrznych (z nieznanych przyczyn językowych zwane MEMO), choć nie wiadomo jeszcze czy się odbędą i jak liczna ma być reprezentacja na nie (możliwe jest nawet, że polecą wszyscy pozostali uczestnicy lub nikt)...

A więc tuż przed zawodami na posiedzeniu KG OMZ padło pytanie: "Ile jest teoretycznie możliwych wyborów obydwu reprezentacji, jeśli na MEMO poleci \(\displaystyle{ i}\) uczestników?" Po burzliwych naradach pewien członek komisji zadaniowej zaproponował
- Możemy najpierw wybrać zbiór uczestników tworzących obie reprezentacje, a następnie ustalić, którzy z nich lecą na IMO, co daje nam łącznie \(\displaystyle{ {n \choose i+m}{i+m \choose m}}\) możliwości.
Inny głos dodał:
- A z drugiej strony, możemy wybrać ludzi lecących na IMO, a potem dopiero resztę reprezentacji, czyli mamy sposobów \(\displaystyle{ {n \choose m}{n-m \choose i}}\)
Zagrzmiały gromkie brawa dla dwójki bohaterów.

Wracając do naszej tożsamości, otrzymujemy stąd sposób na uproszczenie lewej strony (wszak nie ma wątpliwości, że obydwie powyższe odpowiedzi są tak samo poprawne):

\(\displaystyle{ \sum_{i=0}^{n-m} {n \choose {i+m}} {{i+m} \choose m} (-1)^i = \sum_{i=0}^{n-m} {n \choose {m}} {{n-m} \choose i} (-1)^i = {n \choose {m}} \sum_{i=0}^{k} {{k} \choose i} (-1)^i}\), gdzie \(\displaystyle{ k=n-m}\).

Ktoś na posiedzeniu zadał w tym momencie kolejne pytanie:
-Jeśli już mamy wybraną reprezentację na IMO, to czy więcej jest sposobów wyboru reprezentacji na MEMO z parzystą, czy nieparzystą liczbą reprezentantów?
Na pierwszą odpowiedź nie trzeba było długo czekać:
-Liczba sposobów przy parzystej liczbie reprezentantów to po prostu suma \(\displaystyle{ {k \choose i}}\) po \(\displaystyle{ i}\) parzystych, a dla nieparzystej - po \(\displaystyle{ i}\) nieparzystych. Policzmy i wyjdzie.
Zanim jednak ktoś naprawdę zaczął to liczyć, głos zabrał matematyk przypominający Meksykanina:
-Wybierzmy sobie jakiegoś nielecącego na IMO uczestnika \(\displaystyle{ a}\) i zauważmy, że możemy jednoznacznie przyporządkować każdej możliwej reprezentacji, do której on należy, reprezentację, która powstaje z niej przez usunięcie uczestnika \(\displaystyle{ a}\) i podobnie każdej reprezentacji bez niego możemy przypisać jej wersję z dołożonym \(\displaystyle{ a}\). Łatwo widać, że w ten sposób wszystkie możliwe reprezentacje zostają podzielone na pary przypisanych sobie reprezentacji różniących się tylko przynależnością \(\displaystyle{ a}\), czyli każda para zawiera jedną reprezentację parzystej i drugą nieparzystej liczności, co przekonuje, że każda parzystość jest realizowana na tę samą liczbę sposobów, równą liczbie par w podziale.

Owacjom nie było końca. Różnicę między liczbą reprezentacji parzystych a nieparzystych można, zgodnie z pierwszą sugestią, zapisać jako \(\displaystyle{ \sum_{i=0}^{k} {k \choose i}(-1)^i}\), a przecież jest to na mocy wywodu Meksykanina zero, czyli przekształcając dalej lewą stronę tożsamości, dostajemy

\(\displaystyle{ \sum_{i=0}^{n-m} {n \choose {i+m}} {{i+m} \choose m}(-1)^i = {n \choose {m}} \sum_{i=0}^{k} {{k} \choose i} (-1)^i=0}\), co chcieliśmy pokazać.

-- 2 sierpnia 2011, 00:45 --

W 2. jest błąd, być może zamiast \(\displaystyle{ (-1)^{n+1}}\) miało być \(\displaystyle{ (-1)^{i+1}}\), co założono w poniższym dowodzie.

zad.2:    

Rozważmy funkcję \(\displaystyle{ F(x)= \sum_{i=1}^{n} \frac{x^i}{i} {n \choose i}}\), której pochodna wynosi \(\displaystyle{ F'(x)=\sum_{i=1}^{n}x^{i-1}{n \choose i} = \frac{1}{x}(\sum_{i=0}^{n}x^{i}{n \choose i}-1)=\frac{(x+1)^n-1}{(x+1)-1}}\)
czyli jest to suma szeregu geometrycznego
\(\displaystyle{ \sum_{i=0}^{n-1}(x+1)^i}\)

Lewa strona dowodzonej tożsamości wynosi \(\displaystyle{ -F(-1)}\), czyli kolejno:
\(\displaystyle{ -F(-1)=F(0)-F(-1)= \int_{-1}^{0} F'(x)dx=\sum_{i=0}^{n-1}\int_{-1}^{0}(x+1)^idx=}\)
\(\displaystyle{ =\sum_{i=0}^{n-1}(\frac{(0+1)^{i+1}}{i+1}-\frac{(-1+1)^{i+1}}{i+1})=\sum_{i=1}^{n}\frac{1}{i}}\), c.n.d.

zad.3:    

Łatwo zauważyć, że tożsamość jest równoważna tożsamości
\(\displaystyle{ \sum_{i=0}^{n}\sum_{j=i+1}^{n+1}{{n+1} \choose j}{n \choose i} = 2^{2n}}\)

Załóżmy, że mamy \(\displaystyle{ n+1}\) dziewczynek i \(\displaystyle{ n}\) chłopców w klasie i chcemy wybrać dowolny podzbiór uczniów, ale tak, by dziewczynek było więcej niż chłopców, takie podzbiory uczniów nazwijmy dobrymi. Suma po lewej stronie to liczba sposobów dokonania tego, przy czym każdy składnik odpowiada wyborowi \(\displaystyle{ i}\) chłopców i \(\displaystyle{ j}\) dziewczynek. Z drugiej strony, wszystkie podzbiory uczniów klasy możemy sparować w rozłączne pary postaci (zbiór, dopełnienie zbioru do całości klasy) i jeśli w parze w którymś podzbiorze jest \(\displaystyle{ i}\) chłopców oraz \(\displaystyle{ j}\) dziewczynek, to ten zbiór jest dobry wtedy i tylko wtedy, gdy \(\displaystyle{ i<j}\), czyli \(\displaystyle{ n-i>n-j}\), czyli (nierówność liczb całkowitych) równoważnie \(\displaystyle{ n-i\geq (n+1)-j}\), czyli wtedy i tylko wtedy, gdy zbiór w parze z nim nie jest dobry, więc w każdej parze jest dokładnie jeden zbiór dobry i dokładnie jeden zły, czyli podzbiorów dobrych jest tyle, co par, czyli \(\displaystyle{ \frac{2^{2n+1}}{2}=2^{2n}}\), co daje prawą stronę tożsamości.

-- 2 sierpnia 2011, 01:21 --

zad.8:    

Mamy kolejno

\(\displaystyle{ \sum_{i=0}^{n}(-1)^i{n\choose i}(2^{n-i}-1)^m=\sum_{i=0}^{n}(-1)^i{n\choose i}\sum_{j=0}^{m}{m \choose j}(-1)^j2^{(m-j)(n-i)}=\sum_{i=0}^{n}\sum_{j=0}^{m}{n \choose i}{m \choose j}(-1)^{i+j}2^{(n-i)(m-j)}}\)

Analogicznie dostajemy:
\(\displaystyle{ \sum_{j=0}^{m}(-1)^j{m\choose j}(2^{m-j}-1)^n=\sum_{j=0}^{m}\sum_{i=0}^{n}{m \choose j}{n \choose i}(-1)^{j+i}2^{(m-j)(n-i)}}\) otrzymując sumę tych samych wyrażeń co poprzednio, tylko w innej kolejności, skąd wniosek, że

\(\displaystyle{ \sum_{i=0}^{n}(-1)^i{n\choose i}(2^{n-i}-1)^m=\sum_{j=0}^{m}(-1)^j{m\choose j}(2^{m-j}-1)^n}\)

co oznacza tezę (po usunięciu w obydwu sumach wyrazów o najwyższym indeksie, a te są obydwa równe zero).

-- 2 sierpnia 2011, 14:04 --

zad.10:    

Tożsamość po podstawieniu w składnikach sumy za \(\displaystyle{ i}\) indeksu \(\displaystyle{ n-i}\) jest podobna do tej z https://www.matematyka.pl/259348.htm, przy czym zamiast \(\displaystyle{ i^n}\) w składnikach występuje \(\displaystyle{ i^{n+1}}\). Zastosujemy analogiczną metodę do rozwiązania, które zamieściłem w tym temacie, próbując ją nieco uogólnić. Niech \(\displaystyle{ m}\) będzie liczbą całkowitą dodatnią. Dla \(\displaystyle{ 1\leq i\leq n}\) niech \(\displaystyle{ A_i}\) będzie zbiorem ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\} \setminus \left\{ i \right\}}\)

Przez \(\displaystyle{ t}\) oznaczmy liczbę ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\}}\), w których występuje każda liczba z tego zbioru co najmniej raz, a więc (każdy ciąg ma albo tę własność, albo istnieje liczba ze zbioru, która nie jest jego elementem)
\(\displaystyle{ t=n^m-|A_1 \cup A_2 \cup ... \cup A_n|}\)

Moc sumy zbiorów \(\displaystyle{ A_i}\) możemy wyrazić przy pomocy zasady włączen i wyłączeń, pamiętając, że \(\displaystyle{ |A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}|=(n-k)^m}\) dla dowolnych \(\displaystyle{ 1\leq i_1 < i_2 <...<i_k \leq n}\), gdyż liczba ta jest liczbą ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\} \setminus \left\{ i_1, i_2, ..., i_k \right\}}\). Otrzymujemy mianowicie, że \(\displaystyle{ n^m-|A_1 \cup A_2 \cup ... \cup A_n|=n^m-\sum{k=1}^{n}(-1)^{k+1}{n \choose k}(n-k)^m = \sum{k=0}^{n}(-1)^{k}{n \choose k}(n-k)^m}\)

-- 2 sierpnia 2011, 14:23 --Poprawiona wersja zad.10, tamta ma błędny zapis i jest niedokończona, ale nie mogę edytować:

zad.10:    

Tożsamość po podstawieniu w składnikach sumy za \(\displaystyle{ i}\) indeksu \(\displaystyle{ n-i}\) jest podobna do tej z https://www.matematyka.pl/259348.htm, przy czym zamiast \(\displaystyle{ i^n}\) w składnikach występuje \(\displaystyle{ i^{n+1}}\). Zastosujemy analogiczną metodę do rozwiązania, które zamieściłem w tym temacie, próbując ją nieco uogólnić. Niech \(\displaystyle{ m}\) będzie liczbą całkowitą dodatnią. Dla \(\displaystyle{ 1\leq i\leq n}\) niech \(\displaystyle{ A_i}\) będzie zbiorem ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\} \setminus \left\{ i \right\}}\)

Przez \(\displaystyle{ t}\) oznaczmy liczbę ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\}}\), w których występuje każda liczba z tego zbioru co najmniej raz, a więc (każdy ciąg ma albo tę własność, albo istnieje liczba ze zbioru, która nie jest jego elementem)
\(\displaystyle{ t=n^m-|A_1 \cup A_2 \cup ... \cup A_n|}\)

Moc sumy zbiorów \(\displaystyle{ A_i}\) możemy wyrazić przy pomocy zasady włączen i wyłączeń, pamiętając, że \(\displaystyle{ |A_{i_1} \cap A_{i_2} \cap ... \cap A_{i_k}|=(n-k)^m}\) dla dowolnych \(\displaystyle{ 1\leq i_1 < i_2 <...<i_k \leq n}\), gdyż liczba ta jest liczbą ciągów \(\displaystyle{ m}\)-elementowych o wyrazach ze zbioru \(\displaystyle{ \left\{ 1,2,...,n\right\} \setminus \left\{ i_1, i_2, ..., i_k \right\}}\). Otrzymujemy mianowicie, że \(\displaystyle{ t=n^m-|A_1 \cup A_2 \cup ... \cup A_n|=n^m-\sum_{k=1}^{n}(-1)^{k+1}{n \choose k}(n-k)^m =}\)
\(\displaystyle{ = \sum_{k=0}^{n}(-1)^{k}{n \choose k}(n-k)^m}\)

Dla \(\displaystyle{ m=n+1}\) możemy łatwo policzyć \(\displaystyle{ t}\), gdyż jest to liczba ciągów, w których prawie każda liczba od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) występuje raz, a jedna z nich dwa razy, czyli możemy najpierw wybrać dwie pozycje ciągu z tą samą wartością na \(\displaystyle{ {n+1 \choose 2}}\) sposobów, wartość przyjmowaną podwójnie na \(\displaystyle{ n}\) sposobów, a ustawienie pozostałych wartości na \(\displaystyle{ (n-1)!}\) sposobów, czyli \(\displaystyle{ t={n+1 \choose 2}n(n-1)!=n\frac{(n+1)!}{2}}\)

co daje \(\displaystyle{ \sum_{k=0}^{n}(-1)^{k}{n \choose k}(n-k)^{n+1}=n\frac{(n+1)!}{2}}\), c.n.d.

A co dla innych \(\displaystyle{ m}\)? Możemy zauważyć, że wybór \(\displaystyle{ m}\)-elementowego ciągu zawierającego każdą liczbę co najmniej raz daje się przeprowadzić jako podział zbioru \(\displaystyle{ m}\) pozycji ciągu na \(\displaystyle{ n}\) niepustych podzbiorów, w którym każdy odpowiada tym samym elementom, a następnie przypisanie im liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) na \(\displaystyle{ n!}\) sposobów, czyli \(\displaystyle{ t=n!S(m,n)}\), gdzie \(\displaystyle{ S(m,n)}\) jest liczbą podziałów zbioru \(\displaystyle{ m}\)-elementowego na \(\displaystyle{ n}\) niepustych podzbiorów, czego się nie da już znacząco bardziej uprościć. \(\displaystyle{ S(m,n)}\) jest liczbą Stirlinga drugiego rodzaju. Z naszych rozważań wynika nierekurencyjny wzór na nie:

\(\displaystyle{ S(m,n)=\frac{1}{n!}\sum_{k=0}^{n}(-1)^{k}{n \choose k}(n-k)^m}\)

Przy okazji otrzymaliśmy też prosty wniosek, że \(\displaystyle{ S(n+1,n)=\frac{n(n+1)}{2}}\)

[KPR]

Zachęcam do zrobienia 12. Ma fajne, kombinatoryczne rozwiązanie -- 6 sie 2011, o 22:08 --O, ale mam błąd w 12. Powinno być \(\displaystyle{ x_0=c}\). Pewnie przez to nikt nie mógł rozwiązać

[King James]

zad. 6:    

\(\displaystyle{ \sum_{i \geq 0} {i \choose m} x^i = \frac{x^m}{(1-x)^{m+1}}}\)

Kombinatorycznie można to pokazać licząc liczbę całkowitych nieujemnych rozwiązań równania \(\displaystyle{ x_1+...+x_{m+1} = i-m}\) lub niekombinatorycznie rozwijając \(\displaystyle{ (1-x)^{\alpha}}\), dla \(\displaystyle{ \alpha=-m-1}\)
albo wykorzystując f. tworzącą dwóch zmiennych indeksowanych po \(\displaystyle{ i}\) i \(\displaystyle{ m}\).

\(\displaystyle{ \sum_{n \geq 0} x^n \sum_{i \geq 0} (-1)^{i-r}{i\choose r}{n-i\choose i}2^{n-2i} =
\sum_{i \geq 0} (-1)^{i-r}{i\choose r} x^i \cdot 2^{-i} \sum_{n \geq 0} {n-i\choose i} (2x)^{n-i} =
\sum_{i \geq 0} (-1)^{i-r}{i\choose r} x^i \cdot 2^{-i} \frac{(2x)^i}{(1-2x)^{i+1}} =
\frac{(-1)^r}{1-2x} \sum_{i \geq 0} {i\choose r} \left(-\frac{x^2}{1-2x}\right)^i=
\frac{(-1)^r}{1-2x} \cdot \frac{(\frac{-x^2}{1-2x})^r}{(1+\frac{x^2}{1-2x})^{r+1}} =
\frac{x^{2r}}{(1-2x+x^2)^{r+1}} = \frac{1}{x} \cdot \frac{x^{2r+1}}{(1-x)^{2r+2}} =
\sum_{n \geq 0} {n+1 \choose 2r+1} x^n}\)

[kaszubki]

tożsamość 4:    

jak się sumuje od jedynki to wychodzi jakiś straszny bulszit, więc sumuję od zera.
\(\displaystyle{ \sum\limits_{i=0}^{n} (-1)^i{n\choose i}\frac1{i+m+1}=(-1)^n \cdot \sum\limits_{i=0}^{n} (-1)^{n-i}{n\choose i}\frac1{i+m+1}}\).
Wprowadzę coś, co nazywane jest operatorem różnicowym. Definiujemy go tak, że jak mamy sobie funkcję\(\displaystyle{ f}\), to \(\displaystyle{ \Delta f(x) = f(x+1) - f(x)}\) i \(\displaystyle{ \Delta^n(f) = \Delta (\Delta^{n-1}(f))}\). Przez indukcję łatwo udowodnić, że \(\displaystyle{ \Delta^n(f(x)) = \sum_{i=0}^{n} (-1)^{n-i} {n \choose i} f(x+i)}\).
No to weźmy sobie jako \(\displaystyle{ f}\) funkcję \(\displaystyle{ \frac{1}{x}}\). Jak widać, lewa strona naszej tożsamości to \(\displaystyle{ (-1)^n \cdot \Delta^n(f(m+1))}\), a prawa to \(\displaystyle{ (-1)^m \cdot \Delta^m(f(n+1))}\). Zatem trzeba tylko wykazać równość tych dwóch rzeczy. No to teraz drugą indukcją:
teza inducyjna - \(\displaystyle{ \Delta^k(f(l)) = \frac{k! \cdot (-1)^k}{l(l+1)(l+2)...(l+k)}}\)
dowód: no widać, że dla zera i jedynki zachodzi, teraz wystarczy po prostu odjąć od siebie takie dwa proste wyrażenia i wychodzi.
No to trzeba pokazać, że \(\displaystyle{ (-1)^n \cdot \Delta^n(f(m+1))= (-1)^m \cdot \Delta^m(f(n+1)) \Leftrightarrow \\ (-1)^n \frac{n! \cdot (-1)^n}{(m+1)...(m+n+1)}=(-1)^m \frac{m! \cdot (-1)^m}{(n+1)...(n+m+1)} \Leftrightarrow \\ \frac{1}{(m+n+1)!} = \frac{1}{(m+n+1)!}}\), c.k.d.

[KPR]

To może zapodam równie piękne rozwiązanie firmowe:

Ukryta treść:    

Skorzystamy z tego, że \(\displaystyle{ \frac1{1+i+m}= \int_{0}^{1} x^{i+m}}\).
Stąd \(\displaystyle{ \sum\limits_{i=1}^{n} (-1)^i{n\choose i}\frac1{i+m+1}=\sum\limits_{i=1}^{n} (-1)^i{n\choose i}\int_{0}^{1} x^{i+m}=\int_{0}^{1} \sum\limits_{i=1}^{n} (-1)^i{n\choose i} x^{i+m}=\int_{0}^{1} x^m(1-x)^n}\).
Wykonując podstawienie \(\displaystyle{ t=1-x}\) i analogicznie licząc całkę, dostajemy równość z zadania.