[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: KPR » 31 lip 2011, o 18:29

Tak sobie znalazłem trochę tożsamości. Polecam oczywiście kombinatoryczne rozwiązania.

1.\(\displaystyle{ \sum\limits_{i=0}^{n}\frac1{i+1}{n\choose i}=\frac1{n+1}\left(2^{n+1}-1\right)}\)

2.\(\displaystyle{ \sum\limits_{i=1}^{n}(-1)^{n+1}\frac1i{n\choose i}=\sum\limits_{i=1}^{n}\frac1i}\)

3.\(\displaystyle{ \sum\limits_{i=0}^{n-1}\sum\limits_{j=i+1}^{n+1} {n+1\choose j}{n\choose i}=2^{2n}-1}\)

4.\(\displaystyle{ \sum\limits_{i=1}^{n} (-1)^i{n\choose i}\frac1{i+m+1}=\sum\limits_{i=1}^{m} (-1)^i{m\choose i}\frac1{i+n+1}}\)

5.\(\displaystyle{ \sum\limits_{i=0}^{n-1}(i+1){n\choose i}a_{n-i}=2\cdot n!-n-1}\), gdzie \(\displaystyle{ a_n=\sum\limits_{i=0}^{n}(-1)^i\frac{n!}{i!}}\)

6.\(\displaystyle{ \sum\limits_{i=r}^{n} (-1)^{i-r}{i\choose r}{n-i\choose i}2^{n-2i}={n+1\choose 2r+1}}\)

7.\(\displaystyle{ \sum\limits_{i=0}^n i{n\choose i}^2=n{2n-1\choose n-1}}\)

8.\(\displaystyle{ \sum\limits_{i=0}^{n-1} (-1)^i{n \choose i}(2^{n-i}-1)^m=\sum\limits_{i=0}^{m-1} (-1)^i{m \choose i}(2^{m-i}-1)^n}\)

9.\(\displaystyle{ \sum\limits_{i=0}^{n}{n\choose i}{i\choose m}(-1)^i=(-1)^n\delta_{n,m}}\), gdzie \(\displaystyle{ \delta_{m,n}=\begin{cases}1,\mathrm{ gdy }\,m=n \\ 0, \mathrm{ gdy }\,m\neq n\end{cases}}\)

10.\(\displaystyle{ \sum\limits_{i=0}^{n}{n\choose i}(n-i)^{n+1}(-1)^i=n\frac{(n+1)!}2}\)

11.\(\displaystyle{ \sum\limits_{x_1\geq 0}\sum\limits_{x_2\geq 0}\dots\sum\limits_{x_0=x_t\geq 0}\prod\limits_{i=1}^t {n-x_{i-1}\choose x_i}=\frac{f_{tn+t}}{f_{t}}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego.

12.\(\displaystyle{ \sum\limits_{x_1\geq 0}\sum\limits_{x_2\geq 0}\dots\sum\limits_{x_t\geq 0}\left(\prod\limits_{i=1}^t {n-x_{i-1}\choose x_i}g_1^{x_1}g_2^{n-x_1}\right)=(g_2f_{t+1})^cg_{t+2}^{n-c}}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego, \(\displaystyle{ g}\)-dowolnym ciągiem spełniającym rekurencję \(\displaystyle{ g_n=g_{n-1}+g_{n-2}}\) dla \(\displaystyle{ n>2}\) oraz \(\displaystyle{ x_0=n-c}\).

Znalazłem jeszcze jedną fajną tożsamość, to pomyślałem, ze dorzucę:
13.\(\displaystyle{ \sum\limits_{i\geq 0}\sum\limits_{j\geq 0}{i+j\choose i}{n-i-j\choose j}f_{t-1}^if_t^{2j-1}f_{t+1}^{n-2j-i}=f_{(n+1)t}}\), gdzie \(\displaystyle{ f}\) jest ciągiem Fibonacciego.
Ostatnio zmieniony 1 sie 2011, o 18:27 przez KPR, łącznie zmieniany 6 razy.

marcin_smu
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 21 lut 2011, o 20:49
Płeć: Mężczyzna
Lokalizacja: Skierniewice
Pomógł: 10 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: marcin_smu » 31 lip 2011, o 20:18

1:    

Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: Swistak » 31 lip 2011, o 20:53

zad. 7:    

Awatar użytkownika
Damianito
Użytkownik
Użytkownik
Posty: 68
Rejestracja: 25 kwie 2007, o 13:44
Płeć: Mężczyzna
Lokalizacja: Zabrze
Pomógł: 7 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: Damianito » 1 sie 2011, o 11:17

zad.5:    
zad.9:    
-- 2 sierpnia 2011, 00:45 --

W 2. jest błąd, być może zamiast \(\displaystyle{ (-1)^{n+1}}\) miało być \(\displaystyle{ (-1)^{i+1}}\), co założono w poniższym dowodzie.
zad.2:    
zad.3:    
-- 2 sierpnia 2011, 01:21 --
zad.8:    
-- 2 sierpnia 2011, 14:04 --
zad.10:    
-- 2 sierpnia 2011, 14:23 --Poprawiona wersja zad.10, tamta ma błędny zapis i jest niedokończona, ale nie mogę edytować:
zad.10:    

KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: KPR » 2 sie 2011, o 23:32

Zachęcam do zrobienia 12. Ma fajne, kombinatoryczne rozwiązanie -- 6 sie 2011, o 22:08 --O, ale mam błąd w 12. Powinno być \(\displaystyle{ x_0=c}\). Pewnie przez to nikt nie mógł rozwiązać

King James
Użytkownik
Użytkownik
Posty: 150
Rejestracja: 19 kwie 2007, o 22:52
Płeć: Mężczyzna
Lokalizacja: Biłgoraj/Kraków
Pomógł: 39 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: King James » 7 sie 2011, o 12:02

zad. 6:    

kaszubki
Użytkownik
Użytkownik
Posty: 867
Rejestracja: 12 kwie 2008, o 13:35
Płeć: Mężczyzna
Podziękował: 6 razy
Pomógł: 78 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: kaszubki » 21 sie 2011, o 21:20

tożsamość 4:    

KPR
Użytkownik
Użytkownik
Posty: 254
Rejestracja: 11 lip 2009, o 20:00
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 1 raz
Pomógł: 31 razy

[MIX][Kombinatoryka] Tożsamości kombinatoryczne

Post autor: KPR » 21 sie 2011, o 22:00

To może zapodam równie piękne rozwiązanie firmowe:
Ukryta treść:    

ODPOWIEDZ