Afiliacja: Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
W wielu problemach kombinatorycznych pomocne jest badanie odpowiednio dobranych wielomianów, a dokładniej – analizowanie ich współczynników. Przedstawię kilka przykładów o rosnącym stopniu trudności, wprowadzających kolejne przydatne narzędzia i pomysły. Wielokrotnie korzystać będziemy z ważnego wzoru: \[{\textcolor{var(--primary-color)}{(1+x)^n = \sum_{j=0}^n {\binom{n}{j}} x^j.}} \tag{$*$}\] Wzór ten uzasadnimy, analizując proces wymnażania \(n\) nawiasów. Z każdego z nich wybieramy składnik \(1\) albo \(x\) i mnożymy tak wybranych \(n\) elementów, a następnie wszystkie uzyskane w ten sposób iloczyny dodajemy. W efekcie uzyskujemy sumę wyrażeń postaci \(1^{n-j}x^j\) dla \(j=0, 1, 2, \ldots, n,\) przy czym każde z nich pojawia się dokładnie tyle razy, na ile sposobów da się wybrać \(j\) nawiasów spośród \(n\) (i z nich wziąć element \(x\)), czyli właśnie \(\binom{n}{j}\) razy.\(\Box\)
W całym tekście \(n, j, k\) są nieujemnymi liczbami całkowitymi.
Symbol Newtona \(\binom{n}{j}\) oznacza liczbę sposobów wybrania podzbioru \(j\) elementów spośród \(n\) różnych. Jest to równoważne wskazaniu \(n-j\) elementów niewybranych, więc \(\binom{n}{j} = \binom{n}{n-j}.\)
Przyjmujemy, że \(\binom{0}{0}=1.\)
Dla \(n=0\) we wzorze \((*)\) mamy \(1=1.\)
Podstawiając \(x=1,\) otrzymujemy znany wzór \(2^n= \sum_{j=0}^n\binom{n}{j}.\) Każda z jego stron opisuje liczbę podzbiorów zbioru \(n\)-elementowego. Po lewej podzbiór utożsamiamy z ciągiem decyzji wziąć/nie wziąć, podjętych wobec każdego z \(n\) kolejnych elementów, stąd \(2^n\) możliwości. Po prawej zaś zliczamy podzbiory według mocy, tzn. osobno liczymy podzbiory o \(0, 1, 2, \ldots, n\) elementach.
Dalsze ciekawe tożsamości można uzyskać, przyjmując \(x=-1,\) \(x=2\) itd., a także różniczkując wzór \((*)\) i dopiero później podstawiając za \(x\) jakieś wartości. My jednak będziemy odtąd badać tylko wielomiany i ich współczynniki, traktując \(x\) jako pomocniczy symbol i nie rozważając żadnych konkretnych jego wartości.
Zadanie 1. Dowieść, że \(\displaystyle \sum_{j=0}^n \binom{n}{j}^2 = \binom{2n}{n}\) dla dowolnego \(n.\)
Rozwiązanie. Ze wzoru \((*)\) dla wykładnika \(2n\) mamy \((1+x)^{2n} = \sum_{j=0}^{2n} \binom{2n}{j} x^j.\) Współczynnik przy \(x^n\) w wielomianie \((1+x)^{2n}\) jest więc równy \(\binom{2n}{n}.\)
Z drugiej strony, wymnażając czynniki po prawej stronie w iloczynie \[(1+x)^n \cdot (1+x)^n = \biggl(\sum_{j=0}^n {\binom{n}{j}} x^j\biggr) \cdot \biggl(\sum_{j=0}^n {\binom{n}{j}} x^j\biggr),\] wyraz \(x^n\) otrzymamy jako \(x^j \cdot x^{n-j}\) dla każdego \(j=0, \ldots, n,\) przy czym przy każdym z tych czynników pojawi się odpowiedni współczynnik: \(\binom{n}{j} x^j \cdot \binom{n}{n-j} x^{n-j}.\) Stąd współczynnik przy \(x^n\) w wielomianie \((1+x)^{2n}\) – równy, jak już wiemy, \(\binom{2n}{n}\) – jest jednocześnie równy \(\sum_{j=0}^n \binom{n}{j} \binom{n}{n-j} = \sum_{j=0}^n \binom{n}{j}^2.\) \(\Box\)
Zadanie 2. Dowieść, że \(\binom{n}{k} + \ldots + \binom{k+1}{k} + \binom{k}{k} = \binom{n+1}{k+1}\) dla takich \(n, k,\) że \(n \geq k.\)
Rozwiązanie. Oznaczmy \(a_k = \binom{n}{k} + \ldots + \binom{k+1}{k} + \binom{k}{k}.\) Rozważmy wielomian \[\begin{gathered} \hspace{-8cm} a_nx^n+\ldots+a_2x^2+a_1x^1+a_0 x^0 = \\ \hspace{6cm} \begin{aligned} & = \tbinom{n}{n}x^n + \\ & \ \ \ \ \ \ \vdots \\ & \ \ \ + \tbinom{n}{2}x^2 + \ldots + \tbinom{2}{2}x^2 + \\ & \ \ \ + \tbinom{n}{1}x^1 + \ldots + \tbinom{2}{1}x^1 + \tbinom{1}{1}x^1 + \\ & \ \ \ + \tbinom{n}{0}x^0 + \ldots + \tbinom{2}{0}x^0 + \tbinom{1}{0}x^0 + \tbinom{0}{0}x^0 = \\ & = (1+x)^n + \ldots +(1+x)^2+(1+x)^1+(1+x)^0 = \\ & = \displaystyle{\frac{(1+x)^{n+1}-1}{(1+x)-1} = \frac{(1+x)^{n+1}-1}{x}}. \end{aligned} \end{gathered}\] Uzyskany iloraz jest – wbrew ewentualnym obawom – faktycznie wielomianem zmiennej \(x\): w liczniku po odjęciu 1 zostają wyłącznie składniki o dodatnich potęgach przy \(x\) i po podzieleniu przez \(x\) z mianownika otrzymujemy wielomian.
Dodajemy kolumnami, korzystając ze wzoru \((*).\)
Korzystamy ze wzoru na sumę wyrazów ciągu geometrycznego.
Interesujące nas \(a_k\) to współczynnik przy \(x^k\) w tym wielomianie, czyli współczynnik przy \(x^{k+1}\) w \((1+x)^{n+1}-1,\) a więc – ze wzoru \((*)\) – \(\tbinom{n+1}{k+1},\) co kończy dowód. \(\Box\)
Zadanie 3. W pewnej grze rzuca się jednocześnie dwiema kostkami czworościennymi, na każdej może wypaść 1, 2, 3 lub 4, wynikiem jest suma otrzymanych liczb. Jakie są możliwe wyniki i jakie ich prawdopodobieństwa? Jak by się zmieniły, gdyby na jednej z kostek były liczby 1, 2, 2, 3, a na drugiej 1, 3, 3, 5?
Można oczywiście łatwo sporządzić tabelki możliwych wyników, jednak ten prosty przykład posłuży nam do przedstawienia pewnej ogólniejszej metody.
Rozwiązanie. Rozważmy następujący iloczyn, w którym każdy z czynników odpowiada jednej kostce, a kolejne wykładniki przy \(x\) w danym nawiasie równe są liczbom na tej kostce: \[\begin{gathered} \hspace{-5cm} (x^1+x^2+x^3+x^4) \cdot (x^1+x^2+x^3+x^4) =\\ \hspace{7cm} = \sum_{1\leq j,k \leq 4} x^j \cdot x^k = \sum_{1\leq j,k \leq 4} x^{j+k} = \sum_{n=2}^8 a_nx^n. \end{gathered}\] Mnożąc te nawiasy, uzyskujemy 16 składników postaci \(x^j \cdot x^k = x^{j+k}.\) Niektóre się powtarzają, na przykład \(x^5\) występuje cztery razy, bo \(1+4=2+3=3+2=4+1.\) Współczynniki \(a_n\) to właśnie krotności poszczególnych \(x^n,\) zatem \(a_5=4.\) Tak otrzymany wielomian opisuje więc możliwe wyniki (występujące w nim wartości \(n\)) oraz ich prawdopodobieństwa (w tym przypadku równe \(a_n/16\)).
Analogicznie dla kostek z liczbami 1, 2, 2, 3 oraz 1, 3, 3, 5 mamy wielomian \[\begin{gathered} \hspace{-8cm} (x^1+x^2+x^2+x^3) \cdot (x^1+x^3+x^3+x^5) =\\ \hspace{3cm} \begin{aligned} & = x^2 \cdot (1+2x+x^2) \cdot (1+2x^2+x^4) = x^2 \cdot (1+x)^2 \cdot (1+x^2)^2 = \\&= \left(x \cdot (1+x) \cdot (1+x^2) \right)^2 = \left(x \cdot (1+x+x^2+x^3) \right)^2 =\\& = (x+x^2+x^3+x^4)^2. \end{aligned} \end{gathered}\] Jest to dokładnie ten sam wielomian co wcześniej, ma więc takie same współczynniki. Wobec tego nasze nowe kostki dają identyczne sumy z jednakowymi prawdopodobieństwami. \(\Box\)
Czy można napisać takie liczby na kostce ośmiościennej i monecie, by one też równie dobrze nadawały się do tej gry?
Warto przy okazji zadania 3 wspomnieć też o tzw. kościach Sichermana, czyli dwóch kościach sześciennych różnych od ,,standardowych”, które dają te same co kości ,,standardowe” prawdopodobieństwa otrzymania poszczególnych sum oczek. O problemie tym można przeczytać w \(\Delta^1_{09}\).
Zadanie 4. Kupujemy \(n\) owoców, przy czym liczba gruszek ma być parzysta, moreli – podzielna przez 5, pomarańczy najwyżej 4, arbuz najwyżej 1 (innych owoców nie rozważamy). Na ile sposobów można spełnić te warunki?
Rozwiązanie. Podobnie jak w poprzednim zadaniu, wymnóżmy cztery nawiasy odpowiadające owocom, gdzie wykładniki przy \(x\) w każdym nawiasie odpowiadają dopuszczalnym liczbom owoców. Wówczas uzyskamy sumę jednomianów postaci \(x^g\cdot x^m \cdot x^p \cdot x^a = x^{g+m+p+a},\) gdzie \(g\) odpowiada możliwej liczbie gruszek, \(m\) – moreli itd. oraz chcemy, by \(g+m+p+a=n.\) Wobec tego odpowiedź to współczynnik przy \(x^n\) w iloczynie \[\begin{gathered} (1+ x^2+x^4+\ldots) \cdot (1+ x^5+x^{10}+\ldots) \cdot (1+x^1+x^2+x^3+x^4) \cdot (1+x) =\\ \begin{aligned} & = \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1-x^5}{1-x} \cdot \frac{1-x^2}{1-x} = \left(\frac{1}{1-x}\right)^2 = \\&= (1+x+x^2+\ldots)^2. \end{aligned} \end{gathered}\] Podnosząc \(1+x+x^2+\ldots\) do kwadratu, składnik \(x^n\) dostajemy jako \(x^j \cdot x^{n-j}\) dla każdego \(j=0,1, \ldots, n,\) więc na \(n+1\) sposobów. Taki jest zatem poszukiwany współczynnik przy \(x^n,\) czyli szukana liczba sposobów wybrania owoców. \(\Box\)
Nieskończone sumy w nawiasach nie są przeszkodą, możemy bowiem przyjąć, że \(|x|<1,\) i skorzystać ze wzoru na sumę wyrazów ciągu geometrycznego.
Zadanie 5. Ile podzbiorów zbioru \(\{1, 2, \ldots, 3n\}\) ma podzielną przez 3 liczbę elementów?
Intuicja podpowiada, że co trzeci, czyli \(2^{3n}/3,\) ale ta liczba nie jest całkowita, nie jest więc poprawną odpowiedzią.
Rozwiązanie. Niech \(q\neq 1\) będzie dowolnym zespolonym pierwiastkiem trzeciego stopnia z 1 (drugim jest wtedy \(q^2\)). Wówczas 1, \(q\) i \(q^2\) są rozwiązaniami równania \(z^3-1=0,\) czyli \((z-1)(1+z+z^2)=0.\) Stąd \(q^3=1\) oraz \(1+q+q^2=0\) \((**).\)
Korzystając ze wzoru \((*),\) otrzymujemy \[\begin{gathered} \hspace{-7cm} \ \ \ \textcolor{var(--primary-color)}{(1+q^0)^{3n}+(1+q^1)^{3n}+(1+q^2)^{3n}}=\\ \hspace{8cm} \begin{aligned} & =\displaystyle{\sum_{j=0}^{3n} \tbinom{3n}{j} q^{0 \cdot j} + \sum_{j=0}^{3n} \tbinom{3n}{j} q^{1 \cdot j} + \sum_{j=0}^{3n} \tbinom{3n}{j} q^{2 \cdot j} = } \\ & =\displaystyle{\sum_{j=0}^{3n} \tbinom{3n}{j} (q^0 + q^j + q^{2j})} =\displaystyle{ {\color{black}{3 \cdot \sum_{k=0}^{n} \tbinom{3n}{3k}}}}, \end{aligned} \ \ \ \end{gathered}\] przy czym ostatnia równość wynika z obserwacji \((*{*}*)\) na marginesie.
Obserwacja \((*{*}*)\):
ze wzorów \((**)\) dla \(j=3k\) mamy \(q^0 + q^j + q^{2j} = 1+1+1= 3,\)
a dla pozostałych \(j\) otrzymujemy \(q^0 + q^j + q^{2j} = 1+q+q^2 = 0.\)
Zauważmy teraz, że \(\sum_{k=0}^{n} \tbinom{3n}{3k}\) to dokładnie poszukiwana w zadaniu liczba podzbiorów zbioru \((3n)\)-elementowego o liczbie elementów podzielnej przez 3.
Jednocześnie \[\begin{gathered} \hspace{-9cm} \textcolor{var(--primary-color)}{(1+q^0)^{3n}+(1+q^1)^{3n}+(1+q^2)^{3n}}=\\ \hspace{4cm} \begin{aligned} & = 2^{3n}+(-q^2)^{3n}+(-q)^{3n} = 2^{3n}+(-1)^{3n}q^{6n}+(-1)^{3n}q^{3n} = \\&= 2^{3n}+(-1)^{n}+(-1)^{n} = 2^{3n}+2 \cdot (-1)^{n}. \end{aligned} \end{gathered}\] Stąd ostatecznie mamy wynik: \({\displaystyle \textcolor{var(--primary-color)}{\sum_{k=0}^{n} \tbinom{3n}{3k}} = \frac{2^{3n}+2 \cdot (-1)^{n}}{3}}.\)\({\Box}\) ‘
Korzystamy z własności \((**)\) liczby \(q.\)
Początkowa intuicja nie była zła.
Zadanie 6. Ile podzbiorów zbioru \(\{1, 2, \ldots, 3n\}\) ma podzielną przez 3 sumę elementów?
Intuicja znów podpowiada, że co trzeci, czyli około \(2^{3n}/3\) i znów okazuje się dość trafna.
Rozwiązanie. Rozważmy wielomian \[w(z) = (1+ z) (1+z^2)(1+z^3)\ldots(1+ z^{3n}) = \sum_{j=0}^m a_j z^j \text{ dla }m=1+2+\ldots +3n.\] Po wymnożeniu nawiasów, każdy składnik \(z^j\) pojawia się tyle razy, na ile sposobów można go uzyskać jako iloczyn parami różnych potęg \(z\) (bo wybranych z różnych nawiasów), czyli tyle razy, na ile sposobów można uzyskać wykładnik \(j\) jako sumę elementów pewnego podzbioru zbioru \(\{1, 2, \ldots, 3n\}.\) Szukaną odpowiedzią na pytanie z zadania jest zatem wartość wyrażenia \({\textcolor{var(--primary-color)}{a_0+a_3+a_6+\ldots}}\)
Przykładowo, dla \(n \geq 2\) mamy
\(z^1 \cdot z^2 \cdot z^3=z^1 \cdot z^5=z^2 \cdot z^4=z^6\)
oraz sumę 6 mają cztery podzbiory: \(\{1,2,3\}, \{1,5\}, \{2,4\}, \{6\},\) zatem \(a_6=4\) (podobne rozumowanie pojawiło się w zadaniach 3 i 4).
Niech \(q\) będzie określone tak samo, jak w poprzednim zadaniu. Wówczas \[\begin{aligned} \textcolor{var(--primary-color)}{w(q^0)+w(q^1)+w(q^2)} & = a_0(q^0)^0 + a_1 (q^0)^1 + a_2 (q^0)^2 + \ldots + a_m (q^0)^m + \\ & \ \ \ + a_0(q^1)^0 + a_1 (q^1)^1 + a_2 (q^1)^2 + \ldots + a_m (q^1)^m + \\ & \ \ \ + a_0(q^2)^0 + a_1 (q^2)^1 + a_2 (q^2)^2 + \ldots + a_m (q^2)^m = \\ & = \displaystyle{\sum_{j=0}^m a_j \left( (q^0)^j + (q^1)^j + (q^2)^j \right) = {\color{black}{3 \cdot (a_0+a_3+a_6+\ldots) }}}, \end{aligned}\] ostatnia równość znów wynika z obserwacji \((*\!*\!*),\) na marginesie przy zadaniu 5.
Dodajemy kolumnami, jak w zadaniu 2.
Wyznaczymy ponownie \(\textcolor{var(--primary-color)}{w(q^0)+w(q^1)+w(q^2)}\) korzystając z definicji wielomianu \(w(z),\) liczby \(q\) oraz jej własności \((**)\): \[\begin{aligned} w(q^0) & =w(1)=2^{3n}, \\ w(q^1) & = (1+q) (1+q^2)(1+q^3)\ldots(1+ q^{3n}) = \left((1+q)(1+q^2)(1+q^3)\right)^n = \\ & = \left((-q^2)(-q)(2)\right)^n = 2^n, \\ w(q^2) & = 2^n \ \text{(analogicznie).} \end{aligned}\] Stąd ostatecznie \(\textcolor{var(--primary-color)}{w(q^0)+w(q^1)+w(q^2)} = 2^{3n} + 2 \cdot 2^n\) i wobec tego mamy wynik: \[{\displaystyle \textcolor{var(--primary-color)}{a_0+a_3+a_6+\ldots = \frac{2^{3n} + 2 \cdot 2^n}{3}}}.\Box\] Zachęcam do poszukiwania innych rozwiązań powyższych zadań (zapewniam, że istnieją liczne i różnorodne!) oraz innych problemów, które można rozwiązać przy użyciu zaprezentowanych tu metod. Zainteresowanym dalszą lekturą polecam przedstawione na marginesie teksty, a także wyszukiwanie w literaturze terminu funkcje tworzące.
Dodatkowa literatura:
Joanna Jaszuńska, Sześciany i wielomiany, \(\Delta^{9}_{13}\)
Karol Gryszka, Ułamki Fibonacciego, \(\Delta^{2}_{21}\)
Wojciech Guzicki, Kombinatoryka. Rozszerzony program matematyki w liceum (rozdział 8), Wydawnictwo Szkolne OMEGA, Tarnów 2024