[MIX][Kombinatoryka] Bajkowy mix

[Swistak]

Na OMie się chyba nigdy żadna bajeczka nie trafiła, ale co tam, są bardzo fajne . Wydaje mi się, że wybrałem raczej dość ciekawe i nietrywialne .

1.\(\displaystyle{ 2^{2n}=\sum_{k=n} ^{2n} 2^{2n-k}{k \choose k-n}}\)
2. (mzs) \(\displaystyle{ P_n}\) - liczba prostokąków w kwadracie n x n
\(\displaystyle{ P_n={n+1 \choose 2} + 6{n+1 \choose 3} + 6{n+1 \choose 4}}\)
3. \(\displaystyle{ F_{2n}=\sum_{k=1}^{n} {n \choose k} F_{k}}\) (F to ciąg Fibonacciego)
4. \(\displaystyle{ n!=1+\sum_{k=0}^{n-1} {n \choose k}(n-k-1)k!}\)
5. (timon92)\(\displaystyle{ {2n+1 \choose n}=\sum_{k=0}^{n} 2^{k} {n \choose k} {n-k \choose [\frac{n-k}{2}]}}\)
6. \(\displaystyle{ \sum_{k=1}^{n} \frac{1}{k}=\sum_{k=1}^{n}\frac{{n \choose k}}{k} \cdot (-1)^{k+1}}\)
7. \(\displaystyle{ \sum_{2|i_{j}+1 \wedge i_{1}+i_{2}+...+i_{n}=k} ^{} {k \choose i_{1} \ i_{2} \ ... \ i_{n}} \cdot 2^{k-n} =\sum_{2|i_{j}+1 \wedge i_{1}+i_{2}+...+i_{2n}=k+n} ^{} {k \choose i_{1} \ i_{2} \ ... \ i_{n} \ i_{n+1}-1 \ ... \ i_{2n}-1}}\)

P.S. Zadania 3 i 4 są żywcem wzięte z wykładu Michała Seweryna z Kongresu (jedyne dwa, do których nie znam rozwiązań), a zad. 2 to mała przeróbka trzeciego zadania stamtąd.
7 może odstraszać wyglądem, ale proszę się nie zrażać ;p.
Btw napisałem ten mix z 1,5-2 miesiąca temu, ale nie było dane mi go wrzucić .

[timon92]

5:    

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ę.

[mzs]

2.

Ukryta treść:    

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ę.

[edmundo]

Dość długo myślałem nad dowodem 4. po czym stwierdzam, że to chyba nie jest prawda.
Prawa strona równania przyjmuje wartość -1 dla n=2 i -2 dla n=3, wiec przypomina to bardziej -n+1 niż n!

[Swistak]

Sry, rzeczywiście był błąd. k ma przebiegać nie od 1 do n, tylko od 0 do n-1.

[arek1357]

Niech będzie zadanie 6:
zacznę od prawej

\(\displaystyle{ \sum_{k=1}^{n}\frac{{n \choose k}}{k} \cdot (-1)^{k+1}=}\)

\(\displaystyle{ \sum_{k=1}^{n}(-1)^{k+1} {n \choose k} \int_{0}^{1}x^{k-1}dx=}\)

\(\displaystyle{ \int_{0}^{1} \sum_{k=1}^{n}(-1)^{k+1}{n \choose k}x^{k-1}dx=}\)

teraz za k-1=i, k=i+1 k=1, i=0, k=n, i=n-1 i mamy:

\(\displaystyle{ \int_{0}^{1} \sum_{i=0}^{n-1}(-1)^{i+2} {n \choose i+1}x^{i}dx=}\)

\(\displaystyle{ \int_{0}^{1} \sum_{i=0}^{n-1}(-1)^{i} {n \choose i+1}x^{i}dx=}\)

\(\displaystyle{ \int_{0}^{1}- \frac{1}{x} \sum_{i=0}^{n-1}(-1)^{i+1} {n \choose i+1}x^{i+1}dx=}\)

\(\displaystyle{ \int_{0}^{1}- \frac{1}{x} \sum_{i=1}^{n}(-1)^{i} {n \choose i}x^{i}dx =}\)

\(\displaystyle{ -\int_{0}^{1} \frac{1}{x}[ \sum_{i=0}^{n}(-1)^{i} {n \choose i}x^{i}-1]dx=}\)

\(\displaystyle{ - \int_{0}^{1} \frac{1}{x}[(1-x)^{n}-1]dx}\)

teraz czas na podstawienia:

1-x=t
x=1-t
dx=-dt, x=0, t=0 i x=1 t=0 czyli mamy:

\(\displaystyle{ - \int_{0}^{1} \frac{1}{1-t}(t^{n}-1)dt=}\)

\(\displaystyle{ \int_{0}^{1} \frac{t^{n}-1}{t-1}dt=}\)

\(\displaystyle{ \int_{0}^{1} \frac{(t-1)[1+t+t^{2}+...+t^{n-1}]}{t-1}dt=}\)

\(\displaystyle{ \int_{0}^{1}dt+ \int_{0}^{1}tdt+ \int_{0}^{1}t^{2}dt+...+ \int_{0}^{1}t^{n-1}dt=}\)

\(\displaystyle{ 1+ \frac{1}{2}+ \frac{1}{3}+...+ \frac{1}{n}}\)-- 13 lutego 2011, 02:09 --Chyba na dzisiaj wystarczy biorąc pod uwagę że to już jutro

[abc666]

arek1357, ale w tym temacie chodzi o rozwiązanie kombinatoryczne.

[mzs]

3.

Ukryta treść:    

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

\(\displaystyle{ a_i= \begin{cases} 1, \ gdy \ i \in I \\ 2, \ gdy \ i\not\in I \end{cases}.}\)

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:

\(\displaystyle{ F_{2n}= \sum_{k=1}^{n} {n \choose k} F_k.}\)

[arek1357]

Rozwiązanie kombinatoryczne a gdzie to pisało w treści zadania??

Ale mówię ci szczerze abc666 że aby rozwiązać to też kombinowałem trochę-- 13 lutego 2011, 14:43 --W tytule pisze że to bajkowy mix a może moje rozwiązanie to inna bajka??

[Swistak]

Wcześniej nie znałem rozwiązania zad. 4, ale dzisiaj je skminiłem, zatem pozwolę je sobie napisać ;p.

zad 4:    

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

I oczywiście zachęcam do alternatywnego rozwiązania zad. 6

[Dumel]

zad. 1.

Ukryta treść:    

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}}\)