Udowodnij kombinatorycznie następującą tożsamość:
\(\displaystyle{ \sum_{k=m}^{n} {k \choose m}= {n+1 \choose m+1}}\)
Należy opisać pewną sytuację, zadać pytanie typu "ile czegoś jest", a następnie odpowiedzieć na nie na dwa sposoby uzyskując odpowiednio lewą i prawą stronę równości.
Jak to zrobić?
Udowodnij kombinatorycznie
-
Lider_M
- Użytkownik
- Posty: 867
- Rejestracja: 6 maja 2005, o 12:50
- Płeć: Mężczyzna
- Lokalizacja: MiNI PW
- Pomógł: 258 razy
Re: Udowodnij kombinatorycznie
Taki szkic:
Wybierasz \(\displaystyle{ m+1}\) liczb ze zbioru \(\displaystyle{ \{1, 2, \ldots, n+1}\}}\).
W tym wybranym zbiorze może być pewna liczba największa \(\displaystyle{ k}\), oczywiście \(\displaystyle{ k\in\{m+1, \ldots, n+1\}}\).
Wybierasz \(\displaystyle{ m+1}\) liczb ze zbioru \(\displaystyle{ \{1, 2, \ldots, n+1}\}}\).
W tym wybranym zbiorze może być pewna liczba największa \(\displaystyle{ k}\), oczywiście \(\displaystyle{ k\in\{m+1, \ldots, n+1\}}\).
-
max123321
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Udowodnij kombinatorycznie
No ta chyba rozumiem tylko jest konflikt oznaczeń bo to \(\displaystyle{ k}\) oznacza co innego. Wybieramy \(\displaystyle{ m+1}\) elementowe podzbiory zbioru \(\displaystyle{ \left\{ 1,2,...,n+1\right\}}\).
Niech \(\displaystyle{ x}\) oznacza największą liczbę w zbiorze. Pytamy ile jest wśród nich podzbiorów o danym \(\displaystyle{ x}\). Jeśli \(\displaystyle{ x \in \left\{ 1,2,...,m\right\}}\) to tych podzbiorów jest zero, bo nie może istnieć zbiór liczb naturalnych \(\displaystyle{ y}\)-elementowy, w którym największa liczba jest mniejsza od \(\displaystyle{ y}\). Natomiast jeśli \(\displaystyle{ x=m+1}\) to taki podzbiór jest tylko jeden bo skoro element największy \(\displaystyle{ m+1}\) jest już zarezerwowany, to do wybrania pozostaje \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ m}\) ze zbioru \(\displaystyle{ \left\{ 1,2,...,m\right\}}\) czyli \(\displaystyle{ {m \choose m}}\). Jeśli \(\displaystyle{ x=m+2}\) to do wyboru pozostaje \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ m+1}\) liczb czyli \(\displaystyle{ {m+1 \choose m}}\) i tak dalej, dla \(\displaystyle{ x=n}\) pozostaje do wybrania \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ n-1}\) liczb czyli \(\displaystyle{ {n-1 \choose m}}\) i dla \(\displaystyle{ x=n+1}\) pozostaje do wybrania \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ n}\). Suma ilości tych zbiorów jest równa ilości możliwości wyboru zbioru \(\displaystyle{ m+1}\) elementowego ze zbioru \(\displaystyle{ n+1}\) elementowego przyrównując to do siebie otrzymujemy:
\(\displaystyle{ \sum_{k=m}^{n} {k \choose m}= {n+1 \choose m+1}}\).
Czy tak jest dobrze?
Niech \(\displaystyle{ x}\) oznacza największą liczbę w zbiorze. Pytamy ile jest wśród nich podzbiorów o danym \(\displaystyle{ x}\). Jeśli \(\displaystyle{ x \in \left\{ 1,2,...,m\right\}}\) to tych podzbiorów jest zero, bo nie może istnieć zbiór liczb naturalnych \(\displaystyle{ y}\)-elementowy, w którym największa liczba jest mniejsza od \(\displaystyle{ y}\). Natomiast jeśli \(\displaystyle{ x=m+1}\) to taki podzbiór jest tylko jeden bo skoro element największy \(\displaystyle{ m+1}\) jest już zarezerwowany, to do wybrania pozostaje \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ m}\) ze zbioru \(\displaystyle{ \left\{ 1,2,...,m\right\}}\) czyli \(\displaystyle{ {m \choose m}}\). Jeśli \(\displaystyle{ x=m+2}\) to do wyboru pozostaje \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ m+1}\) liczb czyli \(\displaystyle{ {m+1 \choose m}}\) i tak dalej, dla \(\displaystyle{ x=n}\) pozostaje do wybrania \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ n-1}\) liczb czyli \(\displaystyle{ {n-1 \choose m}}\) i dla \(\displaystyle{ x=n+1}\) pozostaje do wybrania \(\displaystyle{ m}\) liczb spośród \(\displaystyle{ n}\). Suma ilości tych zbiorów jest równa ilości możliwości wyboru zbioru \(\displaystyle{ m+1}\) elementowego ze zbioru \(\displaystyle{ n+1}\) elementowego przyrównując to do siebie otrzymujemy:
\(\displaystyle{ \sum_{k=m}^{n} {k \choose m}= {n+1 \choose m+1}}\).
Czy tak jest dobrze?