Skip to Content

Dowody kombinatoryczne

śr., 09/22/2010 - 11:53 — ciebie

W tym rozdziale pokażemy jeszcze kilka dowodów kombinatorycznych.


Przykłady

Zadanie 1.8.1: Udowodnij, że dla każdej liczby naturalnej \(n \ge 1\) prawdziwa jest równość
\(1+2+3+\ldots +n = \frac{n(n+1) }{ 2}.\)

Wskazówka:
Wybierzmy n + 1 punktów na płaszczyźnie. Na przykład, niech te punkty będą położone na jednym okręgu. Następnie każde dwa z tych punktów połączmy odcinkiem. Ile będzie tych odcinków? Spróbuj policzyć je dwiema metodami. Wyobraź sobie, że masz to zrobić przed narysowaniem, planując (sensownie!) proces kreślenia, a potem - że robisz to (znów: sensownie i systematycznie!) wtedy, gdy odcinki już są narysowane.
∎

Rozwiązanie:
Policzymy te odcinki dwiema metodami. Najpierw zliczajmy te odcinki w trakcie rysowania. Weźmy pierwszy punkt. Z niego prowadzimy n odcinków do pozostałych punktów. Teraz bierzemy drugi punkt. Z niego prowadzimy już tylko n − 1 odcinków, bo z jednym punktem jest on już połączony. Trzeci punkt jest połączony z dwoma punktami, więc prowadzimy z niego tylko n − 2 odcinki i tak dalej. Liczba odcinków jest więc równa

\(n+(n-1)+(n-2)+\ldots +2+1,\)

czyli

\(1+2+3+\ldots +n.\)

Teraz będziemy zliczać odcinki wychodzące z poszczególnych punktów. Z każdego punktu wychodzi n odcinków: do każdego innego. Punktów jest n + 1 , więc łącznie wychodzi z nich n(n + 1) odcinków. Ale w ten sposób każdy odcinek został policzony dwukrotnie. Zatem liczba wszystkich odcinków jest równa \(\frac{n(n+1) }{ 2}\) . Stąd mamy wzór

\(1+2+3+\ldots +n = \frac{n(n+1) }{ 2}.\)

Zadanie 1.8.2: Udowodnij, że
\(k \cdot {n \choose k} = n \cdot {{n-1} \choose {k-1}},\)
gdzie \(0<k\le n\) .

Wskazówka:
Wyobraźmy sobie, że z klasy liczącej n uczniów chcemy wybrać k -osobową drużynę sportową i w tej drużynie wskazać kapitana. Na ile sposobów możemy dokonać takiego wyboru? Spróbuj to obliczyć dwiema różnymi metodami (możesz najpierw wybrać drużynę, albo najpierw wskazać kapitana i dobrać mu graczy, prawda?).
∎

Szczegóły rozwiązania:

  1. Pierwsza metoda zliczania. Wykonujemy dwie czynności. Pierwsza polega na wybraniu drużyny, druga na wskazaniu kapitana. Pierwsza czynność daje jeden z \({n \choose k}\) wyników, bo tyle jest k -elementowych podzbiorów zbioru n -elementowego. Druga czynność, niezależnie od wyniku pierwszej, daje jeden z k wyników, bo mamy wskazać jedną z k wybranych osób. Z reguły mnożenia wynika, że łącznie mamy
    \(k \cdot {n \choose k}\)
    wyników i tyle jest sposobów wyboru drużyny wraz z kapitanem.
  2. Druga metoda zliczania. Wykonamy teraz dwie inne czynności. Pierwsza polega na wybraniu kapitana. Druga polega na dobraniu do wybranego kapitana pozostałych członków drużyny. Kapitana możemy wybrać na n sposobów. Niezależnie od tego, kogo wybierzemy, mamy teraz dobrać k − 1 osób spośród pozostałych n − 1 uczniów. Możemy to zrobić na \({n-1 \choose k-1}\) sposobów. Z reguły mnożenia wynika, że wykonanie obu czynności daje jeden z
    \(n \cdot {n-1 \choose k-1}\)
    wyników. Zatem tyle jest sposobów wyboru drużyny i kapitana.

Policzyliśmy sposoby wyboru naszej drużyny dwiema metodami. Otrzymane liczby muszą więc być równe. Stąd otrzymujemy równość

\(\qquad k \cdot {n \choose k} = n \cdot {n-1 \choose k-1}.\)

Zadanie 1.8.3: Udowodnij, że:
\(\qquad {n \choose k} = \frac{n }{ k} \cdot {{n-1} \choose {k-1}},\)
gdzie \(0<k \le n\) .


Rozwiązanie:
Zadanie to wynika natychmiast z zadania poprzedniego. Obie strony równości
\(k \cdot {n \choose k} = n \cdot {n-1 \choose k-1}\)
wystarczy podzielić przez k .
∎

Zadanie 1.8.4: Udowodnij, że jeśli \(1 \le k \le n\) , to
\({n \choose k} = \frac{n! }{ k! \cdot (n-k)!}\)

Rozwiązanie:
Korzystamy z poprzedniego zadania:
\(\qquad\begin{array}{ll} {n \choose k} & = \frac{n }{ k} \cdot {{n-1} \choose {k-1}} = \\ & = \frac{n }{ k} \cdot \frac{n-1 }{ k-1} \cdot {{n-2} \choose {k-2}} = \\ & = \frac{n }{ k} \cdot \frac{n-1 }{ k-1} \cdot \frac{n-2 }{k-2} \cdot {{n-3} \choose {k-3}} = \\ & \ldots \\ & = \frac{n }{ k} \cdot \frac{n-1 }{ k-1} \cdot \frac{n-2 }{k-2} \cdot \frac{n-3 }{ k-3} \cdot \ldots \cdot \frac{n-(k-1) }{k-(k-1)} \cdot {{n-k} \choose {k-k}} = \\ & = \frac{n }{ k} \cdot \frac{n-1 }{ k-1} \cdot \frac{n-2 }{k-2} \cdot \frac{n-3 }{ k-3} \cdot \ldots \cdot \frac{n-k+1 }{1} \cdot {{n-k} \choose 0} = \\ & =\frac {n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \ldots \cdot (n-k+1)}{ k!} \cdot 1. \\ \end{array}\)
Wiemy jednak, że
\(\qquad n \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \ldots \cdot (n-k+1) = \frac{n! }{ (n-k)!}.\)
Zatem
\({n \choose k} = \frac{n! }{ k! \cdot (n-k)!}.\)
∎

Zadanie 1.8.5: Udowodnij, że jeśli liczba p jest pierwsza oraz 0 < k < p , to współczynnik dwumianowy \({p \choose k}\) dzieli się bez reszty przez p .

Rozwiązanie:

Sposób I.
Z zadania 1.8.3. otrzymujemy:
\(\qquad k \cdot {p \choose k} = p \cdot {{p-1} \choose {k-1}}.\)
Liczba pierwsza p jest dzielnikiem prawej strony, więc jest też dzielnikiem lewej strony. Ponieważ k < p , więc liczba p musi być dzielnikiem współczynnika dwumianowego \({p \choose k}\) .
∎


Sposób II.

Wiemy, że ułamek

\(\qquad {p \choose k} = \frac{p \cdot (p-1) \cdot (p-2) \cdot \ldots \cdot (p-k+1) }{ 1 \cdot 2 \cdot \ldots \cdot k}\)

skraca się do liczby całkowitej. Ponieważ wszystkie czynniki w mianowniku są mniejsze od p, więc w trakcie skracania nie skróci się czynnik p w liczniku. Zatem po skróceniu otrzymamy iloczyn p i pewnej liczby całkowitej; ten iloczyn oczywiście dzieli się bez reszty przez p.

Zadanie 1.8.6: Udowodnij, że każdy wiersz trójkąta Pascala jest symetryczny: pierwsza liczba jest równa ostatniej, druga przedostatniej i tak dalej. Możemy to wyrazić wzorem
\({n \choose k} = {n \choose {n-k}}.\)

Rozwiązanie:


Sposób I.
Wzór ten wynika natychmiast ze wzoru na współczynniki dwumianowe:
\({n \choose {n-k}} = \frac{n! }{ (n-k)! \cdot (n-(n-k))!} = \frac{n! }{ (n-k)! \cdot k!} = {n \choose k}.\)
∎


Sposób II (dowód kombinatoryczny).
Współczynnik dwumianowy \({n \choose k}\) wyraża liczbę k -elementowych podzbiorów zbioru n elementowego. Współczynnik \({n \choose n-k}\) wyraża liczbę (n − k) -elementowych podzbiorów zbioru n -elementowego. Wystarczy teraz zauważyć, że dany zbiór n -elementowy ma tyle samo podzbiorów k -elementowych co podzbiorów (n − k) -elementowych. Mianowicie połączmy w parę każdy podzbiór k -elementowy z jego dopełnieniem, które jest podzbiorem (n − k) -e­le­men­to­wym. Z zasady rówoliczności wynika, że jednych i drugich podzbiorów jest tyle samo.


Motywacje: po co szukać dowodów kombinatorycznych?

Można zadać pytanie, po co szukamy dowodów kombinatorycznych, jeśli istnieją równie proste, albo czasami nawet prostsze dowody rachunkowe, algebraiczne. Podamy trzy takie powody.

Po pierwsze, dla lepszego rozumienia matematyki warto znać więcej niż jeden sposób uzasadniania poznawanych twierdzeń. Matematyka nie jest zbiorem oderwanych od siebie faktów, ale twierdzenia należące do pozornie odległych dziedzin wiążą się ze sobą często w sposób nieoczekiwany. Poznanie nowego pomysłu dowodu twierdzenia pozwala spojrzeć na to twierdzenie z innej strony i kiedyś dostrzec jego związki z innymi działami matematyki, dając tym samym możliwość nowego zastosowania.

Po drugie, dowodzone wzory mają sens, którego zrozumienie jest możliwe dzięki odpowiedniemu spojrzeniu. Popatrzmy jeszcze raz na udowodnioną w zadaniu 1.7.3. równość

\({n \choose k} = {{n-1} \choose {k-1}}+{{n-1} \choose k}.\)

Można podać łatwy dowód algebraiczny tej równości:

\(\qquad\begin{array}{ll} {{n-1} \choose {k-1}}+{{n-1} \choose k} & = \frac{(n-1)! }{ (k-1)!(n-k)!} + \frac{(n-1)! }{ k!(n-1-k)!} = \\ & = \frac{(n-1)! }{ (k-1)!(n-k-1)!(n-k)} + \frac{(n-1)! }{ (k-1)!k(n-k-1)!} = \\ & = \frac{(n-1)! }{ (k-1)!(n-k-1)!} \cdot \left(\frac{1 }{ n-k}+\frac{1 }{ k}\right) = \\ & = \frac{(n-1)! }{ (k-1)!(n-k-1)!} \cdot \frac{k+n-k }{ (n-k)k} = \\ & = \frac{(n-1)!\, \cdot \, n }{ (k-1)!k\, \cdot \, (n-k-1)!(n-k)} = \\ & = \frac{n! }{ k! (n-k)!} = \\ & = {n \choose k}. \\ \end{array}\)

Ten rachunkowy dowód nie pokazuje jednak prawdziwego sensu dowodzonego wzoru. Udowodniona równość wynika z szeregu przekształceń algebraicznych, które doprowadzają do wyniku. Dowód kombinatoryczny pokazywał znaczenie każdego symbolu występującego w dowodzonej równości. Po lewej stronie mieliśmy liczbę sposobów wybrania k -elementowej grupy osób z klasy liczącej n − 1 uczniów z wychowawcą. Te sposoby rozdzielały się na dwie grupy, zależnie od tego, czy wychowawca był wybrany, czy nie. Tym dwóm grupom odpowiadały oba składniki po prawej stronie. Wydaje się, że takie spojrzenie na dowodzoną równość pozwala lepiej zrozumieć, o co w niej chodzi. Właściwie każdy wzór matematyczny ma pewien sens. Rozumienie matematyki polega na odkrywaniu tego sensu, a nie tylko na zręcznym przekształcaniu wyrażeń algebraicznych tak, by doprowadzić lewą stronę do prawej lub odwrotnie.

Wreszcie trzeci powód. W niektórych przypadkach dowód kombinatoryczny jest znacznie prostszy od dowodów algebraicznych. Przeprowadzenie takiego dowodu kombinatorycznego wymaga jednak pewnego doświadczenia. Popatrzmy na przykład.


Nieco trudniejszy przykład

Zadanie 1.8.7: Udowodnij równość:
\(\qquad {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 +\ldots + {n \choose n}^2 = {{2n} \choose n}.\)

Rozwiązanie (dowód kombinatoryczny):
Wyobraźmy sobie, że mamy daną grupę n chłopców i n dziewcząt. Z tej grupy mamy wybrać n osób. Na ile sposobów możemy to zrobić? Oczywiście liczba sposobów jest równa \({{2n} \choose n}\) , bo tyle jest n -elementowych podzbiorów zbioru 2n -elementowego. Popatrzmy teraz na to zadanie inaczej.

Zapytajmy najpierw, na ile sposobów można wybrać grupę złożoną z k dziewcząt i n − k chłopców. Oczywiście dziewczęta można wybrać na \({n \choose k}\) sposobów, chłopców zaś na \({n \choose {n-k}}\) sposobów, czyli też na \({n \choose k}\) sposobów. Z reguły mnożenia wynika, że obu wyborów razem można dokonać na \({n \choose k}^2\) sposobów.

Teraz zauważmy, że w naszej grupie n osób może być 0 dziewcząt lub 1 dziewczyna lub 2 dziewczyny lub \(\ldots\) n dziewcząt. Z reguły dodawania wynika, że grupę n osób można wybrać na

\(\qquad {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 +\ldots + {n \choose n}^2\)

sposobów. Tę samą liczbę sposobów obliczyliśmy dwiema metodami, więc wyniki muszą być równe. Stąd otrzymujemy równość

\(\qquad {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 +\ldots + {n \choose n}^2 = {2n \choose n}.\)

∎

Czy potraficie znaleźć równie prosty, ale czysto algebraiczny dowód tej tożsamości...?



Theme by Dr. Radut.