Matematyka.pl

Wyobraźmy sobie, że mamy \(\displaystyle{ n}\) podwójnych ławek (tj. ławka z dwoma miejscami) oraz jedną pojedynczą (z jednym miejscem). Zastanówmy się na ile sposobów można wybrać \(\displaystyle{ n}\) miejsc spośród wszystkich \(\displaystyle{ 2n+1}\) miejsc. Jest to oczywiście lewa strona równości.

Ale policzymy to inaczej: wybieramy najpierw spośród \(\displaystyle{ n}\) podwójnych ławek \(\displaystyle{ k}\), w których zajęte będzie dokładnie jedno miejsce. W każdej takiej ławce zajęte miejsce można wybrać na \(\displaystyle{ 2}\) sposoby. Stąd czynnik \(\displaystyle{ {n \choose k} \cdot 2^k}\). Pozostało nam do wybrania \(\displaystyle{ n-k}\) miejsc.

Wybierzmy \(\displaystyle{ \lfloor \frac{n-k}{2} \rfloor}\) podwójnych ławek spośród pozostałych \(\displaystyle{ n-k}\). Robimy to na \(\displaystyle{ {n-k \choose \lfloor \frac{n-k}{2} \rfloor}}\) sposobów. W każdej z nich bierzemy oba miejsca. W ten sposób wybraliśmy już \(\displaystyle{ k + 2 \cdot \lfloor \frac{n-k}{2} \rfloor}\) miejsc. Do wybrania zostało nam \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) miejsce, do którego realizacji bierzemy pojedynczą ławkę.

Sumujemy po \(\displaystyle{ k=0,1,...,n}\). Otrzymaliśmy prawą stronę.

Rozważmy punkty kratowe na pewnej przekątnej kwadratu.
1. Każdy zbiór dwuelementowy punktów wyznacza jednoznacznie prostokąt, którego dwa wierzchołki leżą na tej przekątnej. Liczba par punktów (i odpowiednich prostokątów) to \(\displaystyle{ {n+1 \choose 2}}\).
2. Każdy ciąg trójwyrazowy {a,b,c} rozpatrywanych punktów wyznacza prostokąt, którego jeden wierzchołek leży na naszej przekątnej. Mianowicie a jest wierzchołkiem prostokąta, b leży na prostej poziomej zawierającej bok prostokąta, ale nie zawierającej punktu a, c leży na prostej pionowej zawierającej bok prostokąta, ale nie zawierającej punktu a. Liczba ciągów trójwyrazowych wynosi \(\displaystyle{ {n+1 \choose 3}\cdot 3!}\).
3. Każda para dwóch podzbiorów {a,b},{c,d} rozpatrywanych punktów wyznacza prostokąt, którego żaden wierzchołek nie leży na naszej przekątnej. Mianowicie a,b leżą na prostych zawierających boki poziome, zaś c,d leżą na prostych zawierających boki pionowe. Parę dwóch podzbiorów {a,b},{c,d} tworzymy następująco: wybieramy najpierw podzbiór czteroelementowy - \(\displaystyle{ {n+1 \choose 4}}\) sposobów. Wybieramy z niego podzbiór dwuelementowy punktów, które leżą na prostych zawierających boki poziome - \(\displaystyle{ {4 \choose 2}=6}\) sposobów.
Sumując wyniki z trzech powyższych przypadków otrzymujemy prawą stronę.

Znany jest fakt:
\(\displaystyle{ F_{n}}\) można interpretować jako liczba ciągów o wyrazach 1 lub 2 , których suma wyrazów wynosi \(\displaystyle{ n-1}\).

Liczba ciągów o wyrazach 1 lub 2 , których suma wyrazów wynosi \(\displaystyle{ 2n-1}\) jest równa \(\displaystyle{ F_{2n}}\).
Policzmy tę liczbę inaczej. Ze zbioru\(\displaystyle{ \left\{ 1,...,n\right\}}\) wybierzmy podzbiór k elementowy I. Definiujemy ciąg n elementowy następująco Suma wyrazów ciągu wynosi \(\displaystyle{ 2\left( n-k\right) +k = 2n-k}\). Liczba takich ciągów wynosi \(\displaystyle{ {n \choose k}}\).
Dołączamy na końcu ciągu dowolny ciąg o wyrazach 1 lub 2 , którego suma wyrazów wynosi \(\displaystyle{ k-1}\). Można to zrobić na \(\displaystyle{ F_{k}}\) sposobów. Otrzymujemy ciąg o wyrazach 1 lub 2 , którego suma wyrazów wynosi \(\displaystyle{ 2n-k+k-1=2n-1}\).
Sumując liczby ciągów dla \(\displaystyle{ k=1,..,n}\) (k nie może być równe zero, bo wprzeciwnym razie suma to 2n) otrzymujemy:

Lewa strona, to oczywiście liczba permutacji zbioru 1, 2, ..., n. W celu pokazania, że to jest też prawa strona, ułóżmy liczby 1, 2, ..., n na okręgu i udowodnimy, że liczba permutacji, to \(\displaystyle{ n+\sum_{k=1}^{n-1} {n \choose k} (n-k-1)k!}\), co oczywiście jest równe prawej stronie. Wyobraźmy sobie, że permutacja, to po kolei zaznaczanie jakichś punktów na tym okręgu. W każdej permutacji można wtedy wyszczególnić kawałek, w którym od pewnego momentu do końca zaznaczamy pierwszy niezaznaczony punkt, po tym ostatnim zaznaczonym. Jak takie coś zliczać? Najpierw wybieramy k punktów nienależących do tego wyszczególnionego kawałka i zaznaczamy je w dowolnej kolejności, co robimy na \(\displaystyle{ {n /choose k} k!}\) sposobów, a następnie wybieramy któryś z pozostałych punktów, ale nie ten, który jest następny po ostatnio zaznaczonym i do końca zaznaczamy pierwsze wolne punkty. Pozostałych punktów jest n-k, ale nie możemy zaznaczyć następnego po ostatnio zaznaczonym zatem możemy to zrobić na n-k-1 sposobów. Zatem jeżeli permutację można podzielić na 2 kawałki, z czego 1 jest wyszczególniony w taki sposób w jaki opisałem, a drugi to jest ten, co jest przed nim i oba są niepuste, to możemy to zrobić na \(\displaystyle{ \sum_{k=1}^{n-1} {n \choose k} (n-k-1) k!}\) sposobów. Pozostają jeszcze te permutacje, w których wyszczególniony kawałek jest całą permutacją, a takich jest oczywiście n.
c. K. u. z. s

ze zbioru \(\displaystyle{ \{1,2,...,2n+1\}}\) wybieramy podzbiory co najmniej \(\displaystyle{ n+1}\)- elementowe. takich zbiorów jest oczywiście \(\displaystyle{ 2^{2n}}\) (co drugi).
możemy je też zliczyć wybierając najpierw \(\displaystyle{ n+1}\)-szy element czyli
\(\displaystyle{ \sum_{k=n+1}^{2n+1} {k-1 \choose n}2^{2n+1-k} = \sum_{k=n}^{2n}{k \choose n}2^{2n-k} = \sum_{k=n}^{2n}2^{2n-k}{k \choose k-n}}\)