Dowód kombinatoryczny

[pg2464]

Witam, mam problem z rozwiązanie poniższych zadań poprzez dowód kombinatoryczny

1. \(\displaystyle{ {n \choose k} = \frac{n!}{k!\left( n-k\right)! }}\)

2.\(\displaystyle{ \sum_{i=0}^{n} {i \choose k} = {n+1 \choose k+1}}\)

3.\(\displaystyle{ \sum_{i=0}^{k} {n+i \choose i}= {n+k+1 \choose k}}\)


do 1 - ze zbioru n-elementowego wybieramy k- elementowe podzbiory, i nie wiem co z prawą stroną

[Mruczek]

1) Ustawiam te \(\displaystyle{ n}\) liczb (każdą z \(\displaystyle{ n!}\)) permutacji na \(\displaystyle{ n}\) kolejnych polach i wybieram z nich pierwsze \(\displaystyle{ k}\) pól od lewej - tworzą one \(\displaystyle{ k}\)-elementowy szukany podzbiór. Ale niektóre podzbiory policzyłem wielokrotnie - \(\displaystyle{ k!}\) razy ze względu na możliwe permutacje elementów na \(\displaystyle{ k}\) pierwszych polach i każdy z nich \(\displaystyle{ (n - k)!}\) razy z powodu permutacji pozostałych \(\displaystyle{ n - k}\) pól.

[Dobrochoczy]

3. zliczmy na dwa sposoby k elementowe podzbiory zbioru n+k+1 elementowego . Jesteśmy w stanie podzielić te podzbiory na rozłączne grupy ze względu na elemement \(\displaystyle{ a}\) , dla zbioru \(\displaystyle{ X=\left\{ 1,2,3,4,...,n+1+k\right\} \right\}}\) wybieramy najperw wszystkie podzbiory nie zawierające 1 ,następnie wzystkie zawierające 1 ale nie zawierające 2 ,następnie wszystkie zawierające 1 i 2 ale nie zawierające 3 i tak dalej . Wszystkich podzbiorow nie zwierających 1 mamy więc \(\displaystyle{ {n+k+1-1\choose k}}\), wszystkich zawierających 1 ale nie zawierających 2 \(\displaystyle{ {n+k+1-2 \choose k-1}}\),więc wszystkich podzbiorów zawierających wszystkie liczby z zakresu 1 - r oprócz r jest \(\displaystyle{ {n+k+1-r\choose k-(r-1)}}\) . Ustalamy \(\displaystyle{ i =k-r+1}\) .Mamy więc \(\displaystyle{ \sum_{0}^{k} {n +i\choose i}}\) takich zbiorów

2. Podobnie do 3
Dla zbioru \(\displaystyle{ X=\left\{ 1,2,3,4,...,n+1\right\} \right\}}\) tworzymy rozłączne grupy podzbiorów w następujący sposób
1.Wszystkie zawierające 1
2.Wszystkie zawierające 2 ale nie zawierające 1
3 .Wszystkie zawierające 3 ale nie zawierające 2,1
.....
Tworzymy więc n takich grup
Których w sumie jest \(\displaystyle{ \sum_{0}^{n} {i \choose k}}\)