[MIX][Kombinatoryka] Tożsamości kombinatoryczne
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.
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.
-
- 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
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.
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 11 kwie 2021, o 13:39 przez Jan Kraszewski, łącznie zmieniany 7 razy.
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 lut 2011, o 20:49
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice
- Pomógł: 10 razy
- Damianito
- 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
zad.5:
zad.9:
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:
zad.8:
zad.10:
zad.10:
-
- 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
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ć
-
- Użytkownik
- Posty: 150
- Rejestracja: 19 kwie 2007, o 22:52
- Płeć: Mężczyzna
- Lokalizacja: Biłgoraj/Kraków
- Pomógł: 39 razy