Udowodnij podane tożsamości kombinatoryczne.
Niestety nie algebraicznie lecz poprzez nadanie odpowiednich interpretacji kombinatorycznych.
Pozostały mi dwie tożsamości, dla których niczego nie mogę wymyślić
1)
\(\displaystyle{ \sum_{k = 0}^{n} \binom{r + k}{k} = \binom{r+n+1}{n}}\)
2)
\(\displaystyle{ \sum_{r = 0}^{n} \binom{r}{k} = \binom{n+1}{k+1}}\)
Tożsamości kombinatoryczne
-
- Użytkownik
- Posty: 7918
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Tożsamości kombinatoryczne
1)
Tożsamość jest związana ze zliczaniem na dwa sposoby \(\displaystyle{ n}\) - elementowych podzbiorów \(\displaystyle{ A \subseteq X = \left\{1,2,3,..., r+n+1 \right\}.}\)
Podzbiory te możemy podzielić na grupy rozłączne ze względu na parametr \(\displaystyle{ j, 1\leq j \leq n+1.}\)
Grupa taka zawiera \(\displaystyle{ {r+n+1- j \choose n-(j - 1)}= {r+n+1 - j \choose n - j + 1 }}\) podzbiorów.
Podstawiając \(\displaystyle{ k = n+1-j}\), gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru otrzymujemy żądaną tożsamość.
2)
W podobny sposób tożsamość ta "zlicza" podzbiory \(\displaystyle{ (k+1)}\) - elementowe zbioru
\(\displaystyle{ \left\{ 1,2.3,..., n+1 \right\}}\) ze względu na parametr \(\displaystyle{ r= n+1 -j}\),
gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru.
Tożsamość jest związana ze zliczaniem na dwa sposoby \(\displaystyle{ n}\) - elementowych podzbiorów \(\displaystyle{ A \subseteq X = \left\{1,2,3,..., r+n+1 \right\}.}\)
Podzbiory te możemy podzielić na grupy rozłączne ze względu na parametr \(\displaystyle{ j, 1\leq j \leq n+1.}\)
Grupa taka zawiera \(\displaystyle{ {r+n+1- j \choose n-(j - 1)}= {r+n+1 - j \choose n - j + 1 }}\) podzbiorów.
Podstawiając \(\displaystyle{ k = n+1-j}\), gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru otrzymujemy żądaną tożsamość.
2)
W podobny sposób tożsamość ta "zlicza" podzbiory \(\displaystyle{ (k+1)}\) - elementowe zbioru
\(\displaystyle{ \left\{ 1,2.3,..., n+1 \right\}}\) ze względu na parametr \(\displaystyle{ r= n+1 -j}\),
gdzie \(\displaystyle{ j}\) jest elementem minimalnym podzbioru.