szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 17 kwi 2016, o 13:47 
Użytkownik

Posty: 9
Lokalizacja: Warszawa
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)
\sum_{k = 0}^{n} \binom{r + k}{k} = \binom{r+n+1}{n}

2)
\sum_{r = 0}^{n} \binom{r}{k} = \binom{n+1}{k+1}
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 17 kwi 2016, o 15:55 
Użytkownik

Posty: 3158
1)
Tożsamość jest związana ze zliczaniem na dwa sposoby n - elementowych podzbiorów 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 j, 1\leq j \leq n+1.

Grupa taka zawiera {r+n+1- j \choose n-(j - 1)}= {r+n+1 - j \choose n - j + 1 } podzbiorów.

Podstawiając k = n+1-j, gdzie j jest elementem minimalnym podzbioru otrzymujemy żądaną tożsamość.

2)
W podobny sposób tożsamość ta "zlicza" podzbiory (k+1) - elementowe zbioru

\left\{  1,2.3,..., n+1 \right\} ze względu na parametr r= n+1 -j,

gdzie j jest elementem minimalnym podzbioru.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Tożsamości kombinatoryczne  karad  1
 Tożsamości kombinatoryczne - zadanie 2  Incoobus  1
 Tożsamości kombinatoryczne - zadanie 5  pelas_91  1
 Tożsamości kombinatoryczne - zadanie 3  tajner  1
 Podaj dowody kombinatoryczne następujących tożsamości.  Oleszko12  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl