Zaje_{}cia na mie_{}dzyszkolne kółko - wielomiany a kombinatoryka (szkic)

Na zaje_{}ciach z kombinatoryki poznaliście techniki rozwia_{}zywania problemów kombinatorycznych przy pomocy ”bajeczek” - na pewne wyrażenie patrzyło sie_{}jako na liczbe_{}możliwych układów czegoś, naste_{}pnie to samo coś liczyło sie_{}na inny sposób i otrzymywało równość dwóch wyrażeń kombinatorycznych. Zaleta_{}tej techniki jest jej intuicyjność - wiadomo, dlaczego działa, ska_{}d sie_{}bierze, jest zrozumiałe, ska_{}d wynika otrzymana na końcu równość. Ma ona jednak też dwie wady. Pierwsza_{}jest łatwość popełnienia pomyłki - policzenia jakiegoś układu dwa razy, nie policzenia jakiegoś. Przy rozwia_{}zaniach kombinatorycznych zawsze trzeba sprawdzić otrzymany wynik na małych przypadkach, by zobaczyć, czy nie popełniło sie_{}błe_{}du. Druga_{}wada_{}jest trudność zapisu - dobre, formalne przekazanie rozwia_{}zania kombinatorycznego to zazwyczaj niełatwa i czasochłonna sprawa.

Dziś poznamy inna_{}technike_{}rozwia_{}zywania zadań kombinatorycznych - technike_{}wielomianowa_{}. Nie ma ona dwóch wymienionych wad rozwia_{}zań ”bajeczkami” - jest bowiem sformalizowany, a wie_{}c prosty w zapisie i chronia_{}cy przed błe_{}dami. Jest - przynajmniej na pocza_{}tku - mniej intuicyjna i troche_{}trudniejsza w stosowaniu. Należy ja_{}traktować jako dodatkowe narze_{}dzie przy rozwia_{}zywaniu zadań kombinatorycznych - bardzo pomocne, ale nie jedyne. Trzeba bowiem pamie_{}tać, że zadania kombinatoryczne zazwyczaj nie pojawiaja_{}sie_{}pod postacia_{} wyrażeń, które należy uprościć, ale maja_{}pewna_{}fabułe_{}, i pewne otrzaskanie z ”bajeczkami” jest konieczne choćby po to, by z tej fabuły dojść do wyrażenia, do którego można zastosować technike_{}wielomianowa_{}.

Podstawowym narze_{}dziem którego be_{}dziemy używać jest wzór dwumienny Newtona. Mówi on, że dla dowolnej liczby naturalnej n oraz dowolnych liczb rzeczywistych a i b zachodzi równość

(a + b)^{n} = ∑_{i=0}^{n} \binom{n}{i}a^{i}b^{n−i}

Spróbujmy zobaczyć, czemu tak jest. Otóż wyrażenie (a + b)^{n} to w istocie (a + b)(a + b)(a + b) … (a + b) - w sumie n takich nawiasów. Po otworzeniu wszystkich dostaniemy wyrażenia be_{}da_{}ce iloczynami n liczb, po jednej z każdego nawiasu. Be_{}da_{}to zatem wyrażenia postaci a^{i}b^{n−i} - w sumie liczb bowiem musi być n. Ile be_{}dzie takich wyrażeń dla konkretnego i? By uzyskać takie wyrażenie trzeba wybrać i nawiasów, z których do iloczynu wejdzie a, zaś z reszty wejdzie b. Wyboru i nawiasów spośród n możemy oczywiście dokonać na \binom{n}{i} sposobów. Po poła_{}czeniu posiadanych informacji w jedna_{}całość dostaniemy wzór dwumianowy Newtona.

Zadanie 1: Udowodnić wzór dwumianowy Newtona przy pomocy indukcji.

Dodatkowo be_{}dziemy korzystali z dwóch prostych faktów. Po pierwsze, \binom{n}{i} = \binom{n}{n−i}, po drugie zaś, jeżeli równość b_{n}x^{n} + b_{n−1}x^{n−1} + … + b_{1}x + b_{0} = a_{n}x^{n} + a_{n−1}x^{n−1} + … + a_{1}x + a_{0} zachodzi dla wszystkich x (w istocie wystarcza, by zachodziła dla n + 1 różnych liczb x), to b_{n} = a_{n}, b_{n−1} = a_{n−1}, …, b_{1} = a_{1}, b_{0} = a_{0}.

Zadanie 2: Udowodnić, że taki sam fakt zachodzi dla wielomianów wie_{}kszej liczby zmiennych, np. (dla dwóch zmiennych), że jeśli ∑ a_{i,j}x^{i}y^{j} = ∑ b_{i,j}x^{i}y^{j} dla każdych x, y, to a_{i,j} = b_{i,j} dla każdych i, j.

Wpierw udowodnijmy dwa znane fakty: ∑_{i=0}^{n} \binom{n}{i} = 2^{n}, zaś ∑_{i=0}^{n}(−1)^{i}\binom{n}{i} = 0. Chcemy korzystać ze wzoru dwumianowego, w wyrażeniu ∑_{i=0}^{n} \binom{n}{i} chcielibyśmy, by pojawiły sie_{}wyrażenia postaci a^{i}b^{n−i}. Dopiszmy je w najprostszy możliwy sposób: ∑_{i=0}^{n} \binom{n}{i} = ∑_{i=0}^{n} 1^{i}1^{n−i}\binom{n}{i}, zaś to ze wzoru dwumianowego jest równe (1 + 1)^{n} = 2^{n}.

Drugiego z tych faktów dowodzi sie_{}podobnie - ∑_{i=0}^{n}(−1)^{i}\binom{n}{i} = ∑_{i=0}^{n}(−1)^{i}1^{n−i}\binom{n}{i} = (1 + (−1))^{n} = 0^{n} = 0 (tu warto zwrócić uwage_{}na to, że dowodzony wzór nie jest prawdziwy dla n = 0, bowiem wyrażenie 0^{0} nie jest dobrze określone).

Nieco trudniejsze sa_{}zadania wymagaja_{}ce porównania współczynników przy pewnej pote_{}dze pewnego wielomianu. Spójrzmy dla przykładu na klasyczne zadanie - obliczyć ∑ \binom{n}{k}^{2} (cze_{}sto przedstawiane np. w postaci ”na ile sposobów wieża może dojść z lewego górnego do prawego dolnego rogu szachownicy, ruszaja_{}c sie_{}wyła_{}cznie w góre_{}i w prawo?”). Spójrzmy mianowicie na wielomian (x + 1)^{2n}. Jaki jest współczynnik przy x^{n} w tym wielomianie? Ze wzoru dwumianowego otrzymujemy (x + 1)^{2n} = ∑_{i=0}^{2n} x^{i}\binom{2n}{n}, zatem przy x^{n} stoi \binom{2n}{n}. Rozpiszmy jednak ten wielomian jako (x + 1)^{n} · (x + 1)^{n} = (∑_{i=0}^{n} x^{i}\binom{n}{i}) · (∑_{i=0}^{n} x^{i}\binom{n}{i}). Policzmy w otrzymanym iloczynie współczynnik przy x^{n}. W takim iloczynie x^{n} pojawia sie_{}za każdym razem, gdy mnożymy wyraz x^{k} z lewej strony przez x^{n−k} z prawej. Przy jednym konkretnym mnożeniu otrzymujemy współczynnik \binom{n}{k} pochodza_{}cy od x^{k} mnożony przez \binom{n}{n−k} pochodza_{}cy od x^{n−k}, czyli \binom{n}{k}^{2} (przypomnijmy, że \binom{n}{k} = \binom{n}{n−k}. Współczynnik przy

x^{n} w całym iloczynie wynosi zatem ∑_{k=0}^{n} \binom{n}{k}^{2}. Wobec tego, skoro (x + 1)^{2n} = (∑_{i=0}^{n} x^{i}\binom{n}{i}) · (∑_{i=0}^{n} x^{i}\binom{n}{i}), to (z faktu o równości współczynników) ∑_{k=0}^{n} \binom{n}{k}^{2} = \binom{2n}{n}.

Dla tych, którzy zgubili sie_{}nieco w rachunkach policzmy ten przykład dla n = 2. Rozważamy wtedy (x + 1)^{4} = x^{4} + 4x^{3} + 6x^{2} + 4x + 1, czyli współczynnik przy x^{2} to \binom{4}{2} = 6. Z drugiej strony (x + 1)^{4} = (x+1)^{2} ·(x+1)^{2} = (x^{2} +2x+1)(x^{2} +2x+1). Chcemy liczyć współczynnik przy x^{2}. Po otworzeniu nawiasów x^{2} pojawia sie_{}trzy razy - przy x^{2} · 1, 2x · 2x i 1 · x^{2}. Zatem współczynnik przy x^{2} to \binom{2}{0}^{2} + \binom{2}{1}^{2} + \binom{2}{2}^{2} = 1 + 4 + 1. Po poła_{}czeniu posiadanych faktów otrzymujemy równość ∑_{i=0}^{2} \binom{2}{i}^{2} = \binom{4}{2}, czyli, mówia_{}c po ludzku, 6 = 6.

Naturalnym pytaniem w tym momencie jest ”Ale ska_{}d, tak właściwie, wzia_{}ł sie_{}ten konkretny wielomian?”. Spróbuje_{}na to pytanie przynajmniej po cze_{}ści odpowiedzieć. Wyrażeniem, nad którym pracujemy jest ∑ \binom{n}{k}^{2}. Wpierw trzeba stwierdzić, że szukamy rozwia_{}zania przez wielomian, a konkretnie, że be_{}dziemy próbowali ∑ \binom{n}{k}^{2} przedstawić jako współczynnik pewnego wielomianu. Pojedyncze \binom{n}{k} to współczynnik przy x^{k} w wielomianie (x+1)^{n}. Chcielibyśmy, aby współczynnikiem pewnego wielomianu było ∑ \binom{n}{k}^{2}. By otrzymać taka_{}sume_{}musimy wymnożyć dwa wielomiany takie, że dla każdego k mnoża_{}c wyrazy, przy których stoi \binom{n}{k} dostajemy te_{}sama_{} pote_{}ge_{}x. Jednym z nich jest (x + 1)^{n}, drugim be_{}dzie (1 + x)^{n} - tam \binom{n}{k} jest współczynnikiem przy x^{n−k}. Składamy posiadane fakty razem i dostajemy przedstawione wyżej rozwia_{}zanie.

Oczywiście nie musi być oczywiste, że należy szukać rozwia_{}zania poprzez współczynnik pewnego wielomianu, nie musi być też od razu jasne, że to (x + 1)^{n} be_{}dzie wielomianem, którego użyjemy. Takie intuicje przychodza_{} wraz z doświadczeniem. Aby nabyć go troche_{}wie_{}cej, zróbmy kolejne, troche_{}podobne zadanie. Należy mianowicie udowodnić, że dla dowolnych liczb naturalnych k, m, n zachodzi \binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n−m}{k−m}. Spróbujmy zastanowić sie_{}, jaki typ wielomianu może być tu pomocny. Na pierwszy rzut oka to zadanie przypomina poprzednie - znowu rozważamy iloczyn symboli Newtona. Możnaby wie_{}c pomyśleć, że znowu należy szukać iloczynu dwóch wielomianów. Jednak w poprzednim zadaniu takie iloczyny symboli Newtona sumowaliśmy, co odpowiadało mnożeniu wielomianów. Tu takiej sumy nie mamy. Ska_{}d zatem może pochodzić ten iloczyn?

Iloczyny takie zazwyczaj powstaja_{}przy rozważaniu pote_{}gi sumy wie_{}cej niż dwóch składników. W tym wypadku rozważymy wielomian (x + y + 1)^{n}. Przy pomocy wzoru dwumianowego można go rozpisać na dwa sposoby (tak naprawde_{}na wie_{}cej, ale nam sie_{}przydadza_{}dwa). Wpierw zapiszmy (x + y + 1)^{n} = (x + (y + 1))^{n} = ∑_{m=0}^{n} x^{m}(y + 1)^{n−m}\binom{n}{m} = (tu po raz drugi stosuje wzór dwumianowy do (y + 1)^{n−m}) = ∑_{m=0}^{n} ∑_{k=0}^{n−m} x^{m}y^{k}\binom{n−m}{k}\binom{n}{m}. Z drugiej strony (x + y + 1)^{n} = ((x + y) + 1)^{n} = ∑_{k=0}^{n}(x + y)^{k}\binom{n}{k} = ∑_{k=0}^{n} ∑_{m=0}^{k} x^{m}y^{m−k}\binom{k}{m}\binom{n}{k}. W drugim rozpisaniu mamy już to, co chcemy jako współczynnik przy x^{m}y^{m−k}. W pierwszym rozpisaniu wyste_{}puja_{}wyrazy x^{m}y^{k}, ze współczynnikami \binom{n−m}{k}\binom{n}{m}. Po wstawieniu m − k zamiast k (by uzyskać wspólczynnik przy x^{m}y^{m−k}, a nie przy x^{m}y^{k}) otrzymamy \binom{n−m}{m−k}\binom{n}{m}. Zatem z faktu o równości wspólczynników (a raczej z jego uogólnienia, które sformułowaliśmy jako zadanie 2) dostajemy podana_{} w zadaniu równość.

Czasami - inaczej niż we wszystkich rozpatrywanych dotychczas zadaniach - sumujemy nie po dolnym, ale po górnym wyrazie w symbolu Newtona. Spróbujmy dla przykła_{}du policzyć sume_{}∑_{k=m}^{n} \binom{k}{m}. To powinno być proste. Wiemy już, że \binom{k}{m} to najcze_{}ściej współczynnik przy x^{m} w wyrażeniu (x + 1)^{k}. Chcemy, by ∑_{k=m}^{n} \binom{k}{m} było współczynnikiem przy którejś pote_{}dze pewnego wielomianu. Narzuca sie_{}w tej sytuacji rozważenie (x + 1)^{m}+(x+1)^{m+1}+…+(x+1)^{n} i spojrzenie na współczynnik przy x^{m}. Be_{}dzie to oczywiście nasza suma. Ale czy umiemy ten wielomian zapisać jakoś inaczej (najche_{}tniej prościej)? Chwila zastanowienia pozwala zauważyć, że to, co napisaliśmy to po prostu szereg geometryczny. Suma szeregu geometrycznego a_{1}, a_{2}, …, a_{i} o ilorazie q to a_{1} \frac{q^{n}−1}{q−1}. W tym wypadku dostajemy (x + 1)^{m} \frac{(x+1)^{n−m+1}−1}{x}. Jest to wielomian (pomimo dzielenia), bo wyraz wolny (x+1)^{n−m+1} −1 jest zerem, czyli ten wielomian jest podzielny przez x. Sta_{}d możemy liczyć współczynnik przy x^{m}. Be_{}dzie on oczywiście (z powodu dzielenia przez x) równy współczynnikowi (x+1)^{m}((x+1)^{n−m+1} −1) przy x^{m+1}. Ten jednak jest równy współczynnikowi (x + 1)^{m}(x + 1)^{n−m+1}, gdyż różnica, tj. (x + 1)^{m} jest stopnia m, a zatem ma zerowy współczynnik przy x^{m+1}. Współczynnikiem (x + 1)^{m}(x + 1)^{n−m+1} = (x + 1)^{n+1} przy x^{m+1} jest oczywiście \binom{n+1}{m+1}, ska_{}d otrzymujemy ∑_{k=m}^{n} \binom{k}{m} = \binom{n+1}{m+1}.

Ostatnie zadanie, które rozpatrzymy wymaga użycia pochodnych. Dla tych, którzy nie wiedza_{}, czym jest pochodna, wystarczy informacja o tym, że pochodna_{}wielomianu P jest wielomian oznaczany P′. Pochodna spełnia do tego naste_{}puja_{}ce własności: pochodna_{}x^{n} jest nx^{n−1} (w szczególności pochodna wielomianu stałego to zero), pochodna_{}sumy dwóch wielomianów jest suma ich pochodnych, zaś pochodna iloczynu P ·Q wyraża sie_{} wzorem P′·Q+Q′·P. Do tego, jeśli mamy dwa wielomiany P i Q i rozważymy wielomian P (Q), tj. w wielomianie P w miejsce każdego x-a wstawimy wielomian Q, to pochodna_{}otrzymanego wielomianu be_{}dzie P′(Q) · Q′. Z powyższych warunków już wynika, że jeśli c jest liczba_{}rzeczywista_{}, zaś P wielomianem, to (cP)′ = cP′. Jest to dobrze określona operacja, czyli jeżeli zapiszemy wielomian na dwa różne sposoby i obliczymy pochodna_{}, to otrzymane wielomiany be_{}da_{}równe (dowodem tego nie be_{}dziemy sie_{}tu zajmować, choć nie jest on trudny).

Przy pomocy pochodnych udowodnimy zatem równość ∑_{i=0}^{n} i\binom{n}{i} = n2^{n−1}. Rozważmy najcze_{}ściej używany przez nas wielomian, (x + 1)^{n}. Zróżniczkujmy go - jeżeli przez P oznaczymi x^{n}, zaś przez Q - x + 1, to nasz wielomian ma postać P (Q), czyli jego pochodna to P′(Q) · Q′. P′ to nx^{n−1}, zaś Q′ to 1, czyli ((x + 1)^{n})′ = n(x + 1)^{n−1}.

Teraz wykorzystajmy wzór dwumianowy. (x+1)^{n} = ∑_{i=0}^{n} x^{i}\binom{n}{i}. Zróżniczkujmy ten wielomian. (∑_{i=0}^{n} x^{i}\binom{n}{i})′ = ∑_{i=0}^{n}(x^{i}\binom{n}{i})′ = ∑_{i=0}^{n}(x^{i})′\binom{n}{i} = ∑_{i=0}^{n} ix^{i−1}\binom{n}{i}. Otrzymujemy zatem równość ∑_{i=0}^{n} ix^{i−1}\binom{n}{i} = n(x + 1)^{n−1}. Wstawmy do niej x = 1, a otrzymamy ∑_{i=0}^{n} i\binom{n}{i} = n2^{n−1}, czyli dowodzona_{}równość.

Spróbujmy jeszcze podsumować, tzn. przypomnieć sobie, jakie wyrażenia kombinatoryczne zazwyczaj powoduja_{}pojawienie sie_{}jakich wielomianów. Sumy pojedynczych symboli Newtona to najcze_{}ściej po prostu wzór dwumianowy, w którym za obydwie liczby coś podstawiliśmy. Może sie_{}tam też pojawić c^{k}, gdzie k to indeks sumowania - wtedy za jedna_{}z liczb zapewne podstawiliśmy c. Sumy iloczynów symboli Newtona najcze_{}ściej wymagaja_{}zbadania współczynnika przy pewnej pote_{}dze iloczynu dwóch wielomianów. Iloczyn symboli Newtona (bez sumy) to zazwyczaj porównywanie współczynników przy wyrażeniach typu (a + b + c)^{n}, gdzie za c jest podstawiona konkretna stała. Jeżeli za coś we wzorze dwumianowym chcielbyśmy podstawić stała_{}, ale nie mamy wskazówek jaka_{}, to prawie zawsze podstawiamy jedynke_{}. Sumowanie po górnym polu symbolu Newtona zazwyczaj wymaga użycia wzoru na sume_{}szeregu geometrycznego (czasami, gdy otrzymany wzór nie wygla_{}da na wielomian, można przez mianownik pomnożyć stronami, co niekiedy troche_{}upraszcza rachunki). Pojawienie sie_{}wyrażeń postaci ∑_{i} i·coś, ba_{}dź nawet po prostu mnożenia przez i, zazwyczaj oznacza użycie pochodnej. Jak z tych klocków poskładać rozwia_{}zanie konkretnego zadania musi nam już podpowiedzieć doświadczenie.

By je zdobyć, proponuje_{}naste_{}puja_{}ca_{}serie_{}zadań (moje doświadczenie mówi, że każda tożsamość kombinatoryczna daje sie_{}udowodnić wielomianami, wie_{}c, aby trenować, można wzia_{}ć dowolny inny zestaw tożsamości kombinatorycznych i na nim poćwiczyć):

Zadanie 3: ∑ 2^{i}\binom{n}{i} = 3^{n}

Zadanie 4: ∑(−2)^{i}\binom{n}{i} = (−1)^{n}

Zadanie 5: \binom{n}{k} = \frac{n}{k} \binom{n−1}{k−1}

Zadanie 6: 2^{k}\binom{n}{k} = ∑ \binom{n}{i}\binom{n−i}{k−i}

Zadanie 7: n(n − 1)2^{n−2} = ∑ k(k − 1)\binom{n}{k}

Zadanie 8: \binom{n}{k}\binom{n}{m} = ∑_{j} \binom{k}{j}\binom{m+j}{k}\binom{n}{m+j}

Zadanie 9:∑ 2^{k}\binom{n}{k}^{2} = ∑ \binom{n}{k}\binom{n+k}{n}

Zadanie 10: \binom{n}{n/2} = ∑_{i=0}^{n/2}(−1)^{i}\binom{n}{i}^{2} dla parzystych n.