Tożsamość z dwumianem Newtona

[marcelina4424]

Witam, proszę o pomoc w rozwiązaniu zadania o treści: wykaż, że dla dowolnych liczb naturalnych \(\displaystyle{ n}\) oraz \(\displaystyle{ k}\) takich, że \(\displaystyle{ n > k}\) spełniona jest równość \(\displaystyle{ {n \choose k} = {n \choose n-k}}\).

Proszę też o wyjaśnienie rozwiązania. Z góry dziękuje
Marcelina

[vpprof]

Znasz definicję symbolu Newtona? Możesz podać dowód symboliczny.

Zastanów się, co się dzieje z resztą elementów, gdy wybieramy \(\displaystyle{ k}\) elementów z \(\displaystyle{ n}\). Możesz podać dowód kombinatoryczny.

[marcelina4424]

Według mnie z definicji wychodzi mi coś takiego :
\(\displaystyle{ {n \choose n-k} = \frac{n!}{\left( n-k\right)!\left( n-n+k\right)!}= \frac{n!}{\left( n-k\right)! \cdot k! }= {n \choose k}}\)

Czy dobrze to rozwiązuje?

[Jan Kraszewski]

Dobrze.

JK

[marcelina4424]

Mam jeszcze problem z następnym przykładem. Treść zadania taka sama.
\(\displaystyle{ {n \choose k+1} + {n \choose k} = {n+1 \choose k+1}}\)

[vpprof]

Tu też można rozpisać z definicji a także można podać dowód słowny (kombinatoryczny).

[marcelina4424]

A czy mógłbyś przedstawić ten słowny dowód ?

[vpprof]

Owszem. Podzbiory \(\displaystyle{ k+1}\)-elementowe zbioru \(\displaystyle{ n+1}\)-elementowego zawierają w sobie:

• podzbiory, w których element \(\displaystyle{ n+1}\) nie występuje — jest ich tyle ile zbiorów \(\displaystyle{ k+1}\)-elementowych złożonych z elementów należących do \(\displaystyle{ \left\{ 1,…,n\right\}}\), a więc \(\displaystyle{ {n \choose k+1}}\) oraz
• podzbiory, w których element \(\displaystyle{ n+1}\) występuje — jeśli z każdego z nich usuniemy element \(\displaystyle{ n+1}\), liczba tych podzbiorów się nie zmieni a łatwo będzie zauważyć, że są to zbiory \(\displaystyle{ k}\)-elementowe (bo odjęliśmy jeden element) złożone z elementów należących do \(\displaystyle{ \left\{ 1,…,n\right\}}\), (wiemy, że \(\displaystyle{ n+1}\) nie występuje w tych zbiorach, gdyż nie może wystąpić dwa razy a został już usunięty) a więc \(\displaystyle{ {n \choose k}}\)

Ergo: \(\displaystyle{ {n+1 \choose k+1} = {n \choose k+1} + {n \choose k}}\)