Dowody tożsamości kombinatorycznych.

[pumbosha]

Witam, mam problem z trzema zadaniami, byłbym wdzięczny jeśli ktoś zechciał mi podpowiedzieć:

\(\displaystyle{ {n+2\choose 3}=\sum_{i=1}^{n} i(n+1-1)}\)

\(\displaystyle{ {n+1\choose 2}^2=\sum_{i=1}^{n} i^3}\)

\(\displaystyle{ n^2{2n-2 \choose n-1}=\sum_{i=1}^{n} i^2{n\choose i}^2}\)

[bstq]

\(\displaystyle{ L=\binom{n+2}{3}=\frac{\left(n+2\right)!}{\left(n-1\right)!\cdot3!}=\frac{\left(n+2\right)\cdot\left(n+1\right)\cdot n}{2\cdot 3}}\)

\(\displaystyle{ P=\sum_{i=1}^{n}i\cdot\left(n+1-1\right)=\left(n+1-1\right)\sum_{i=1}^{n}i=n\cdot\sum_{i=1}^{n}i=n\cdot\frac{\left(n-1\right)\cdot n}{2}}\)
pierwsze nieprawda, chyba źle przepisane...
w drugim korzystamy z:
(te wzory dowodzi się indukcyjnie)

\(\displaystyle{ \left(\frac{1}{\left(1-1\right)!\left(n-1-\left(1-1\right)\right)!}\right)^{2}}\)
\(\displaystyle{ L=\binom{n+1}{2}^{2}=\frac{\left(n+1\right)!\cdot\left(n+1\right)!}{2!\cdot2!\cdot\left(n-1\right)!\cdot\left(n-1\right)!}=\frac{n^{2}\left(n+1\right)^{2}}{4}}\)

\(\displaystyle{ P=\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}}\)
czyli \(\displaystyle{ L=P}\)


co do trzeciego to musisz dalej sam pomyśleć... albo spróbować przez indukcję:

\(\displaystyle{ L=\binom{n+1}{2}^{2}=\frac{\left(n+1\right)!\cdot\left(n+1\right)!}{2!\cdot2!\cdot\left(n-1\right)!\cdot\left(n-1\right)!}=\frac{n^{2}\left(n+1\right)^{2}}{4}}\)

\(\displaystyle{ P=\sum_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}}\)

\(\displaystyle{ \sum_{i=1}^{n}i^{2}\binom{n}{i}\binom{n}{i}=\sum_{i=1}^{n}i^{2}\frac{n!n!}{i!i!\left(n-i\right)!\left(n-i\right)!}=\sum_{i=1}^{n}i^{2}\frac{n!n!}{i!i!\left(n-i\right)!\left(n-i\right)!}=}\)

\(\displaystyle{ =n^{2}\sum_{i=1}^{n}\frac{\left(n-1\right)!}{\left(i-1\right)!\left(n-1-\left(i-1\right)\right)!}\frac{\left(n-1\right)!}{\left(i-1\right)!\left(n-1-\left(i-1\right)\right)!}=n^{2}\sum_{i=1}^{n}\binom{n-1}{i-1}\binom{n-1}{i-1}}\)

wystarczy teraz udowodnić, że \(\displaystyle{ \sum_{i=1}^{n}\binom{n-1}{i-1}\cdot \binom{n-1}{i-1}=\binom{2n-2}{n-1}}\)

\(\displaystyle{ L=\left(\left(n-1\right)!\right)^{2n}(\frac{1}{\left(1-1\right)!\left(n-1-\left(1-1\right)\right)!}\cdot\frac{1}{\left(1-1\right)!\left(n-1-\left(1-1\right)\right)!}+\frac{1}{\left(2-1\right)!\left(n-1-\left(2-1\right)\right)!}\cdot\frac{1}{\left(2-1\right)!\left(n-1-\left(2-1\right)\right)!}+\ldots+\frac{1}{\left(n-1\right)!\left(n-1-\left(n-1\right)\right)!}\cdot\frac{1}{\left(n-1\right)!\left(n-1-\left(n-1\right)\right)!})}\)

\(\displaystyle{ =\left(\left(n-1\right)!\right)^{2n}(\left(\frac{1}{0!\left(n-1\right)!}\right)^{2}+\left(\frac{1}{1!\left(n-2\right)!}\right)^{2}+\left(\frac{1}{2!\left(n-1-\left(3-1\right)\right)!}\right)^{2}+\ldots+\left(\frac{1}{\left(n-2\right)!1!}\right)^{2}+\left(\frac{1}{\left(n-1\right)!0!}\right)^{2})=}\)

\(\displaystyle{ n}\)-parzyste:

\(\displaystyle{ =2*\left(\left(n-1\right)!\right)^{2n} ( \left(\frac{1}{0!\left(n-1\right)!}\right)^{2}+\left(\frac{1}{1!\left(n-2\right)!}\right)^{2}+\left(\frac{1}{2!\left(n-1-\left(3-1\right)\right)!}\right)^{2}+\ldots+\left(\frac{1}{\left(\frac{n}{2}\right)!\left(n-1-\left(\frac{n}{2}\right)\right)!}\right)^{2} ) =}\)
może znajdziesz to w książce "Matematyka konkretna", taka gruba

[pumbosza]

Dziękuję bardzo za pomoc. Jeśli chodzi o pierwsze to zamiast drugiej jedynki stoi i. Jeśli chodzi o te dowody ,to na ćwiczeniach robiliśmy podobne zadania w trochę inny sposób, tzn np. jedną stronę interpretowaliśmy jako jakieś zdarzenie (jakiś słowny opis) i udowadnialiśmy, że druga strona jest tym samym, tylko jest trochę inaczej zapisana. Wzory jakie podajesz to jakaś grubsza matma, jednak bardzo dziękuję za pomoc, twoje rozwiązania i tak pewnie mi się przydadzą..pzdr

[Dumel]

trzecie:
mamy sobie dwie n-osobowe grupy kiboli, którzy chcą się umówić na ustawkę. o dziwo są na tyle honorowi że ich reprezentacje mają być równoliczne. każda reprezentacja wybiera swojego kapitana - to jest właśnie prawa strona (wybieramy z kazdej grupy i osob i kapitana dla i=1,2,...)
z drugiej strony możemy najpierw wybrać kapitanów - to jest właśnie nasze \(\displaystyle{ n^2}\) po lewej stronie - a potem dobrać do nich i-1 osobowe grupy. prowadzi nas to do udowodnienia takiej tożsamości:
\(\displaystyle{ {n-1 \choose 0}^2 + {n-1 \choose 1}^2 +\ldots+ {n-1 \choose n-1}^2 = {2n-2 \choose n-1}}\)
dla wygody to zapisze sobie jako:
\(\displaystyle{ {n \choose 0}^2 + {n \choose 1}^2 +\ldots+ {n \choose n}^2 = {2n \choose n}}\)
to jest bardzo znana tożsamość pisałem o niej już parę razy na forum ale nie moge teraz znaleźć ale można to interpretować tak:
mamy szachownice n na n i chcemy przejść z lewego dolnego rogu do prawego gornego. jeden ruch to przesuniecie sie w prawo lub w gore (z perspektywy obserwatora) o jedno pole. na ile sposobow mozna to uczynić?
prawa strona jest dosyć jasna a druga opiera sie na spostrzeżeniu że na drodze dokładnie raz przetniemy przekątną . jakbyś miał dalej kłopoty to pisz-- 22 listopada 2009, 13:45 --pierwsze:
mamy n+1 osób posortowanych rosnąco wg wykształcenia. część (ci gorsi) pójdzie kopać rowy a pozostali zamiatać ulice. każda grupa musi mieć swojego przywódce (obojętnie kto nim będzie).
prawa strona: dokonujemy podziału na i gorszych i n-i lepszych osób i wybieramy przywódców.
lewa: dodajemy jedną osobę do grupy (zaraz się okaże po co).
wybierzmy trzy osoby z n+2 osób które mamy. środkową osobę interpretujmy jako ten "element podziału" - gorsi od niej idą kopać a lepsi idą zamiatać. skrajne osoby są przywódcami swoich grup.
zrobiliśmy to samo na dwa sposoby czyli ok.

[pumbosza]

Wielkie dzięki. Jeśli chodzi o o trzeci przykład do bardziej przemawia do mnie przykład z kibolami:) Z tą szachownicą chyba robiliśmy na zajęciach ale nie pamiętam tego, jakbyś miał jakiś link do tego jak to jest zrobione to proszę o pomoc. Pierwszego przykładu też nie bardzo rozumiem...pzdr

[Dumel]

no to to z szachownicą:
każdy sposób przejścia reprezentujemy przez ciąg w stylu \(\displaystyle{ (\rightarrow, \uparrow, \uparrow, ...)}\) gdzie mamy po n strzałek \(\displaystyle{ \uparrow}\) i \(\displaystyle{ \rightarrow}\). jednoznacznie wyznaczamy ciąg przez ustalenie miejsc dla strzałek pionowych co możemy zrobić na \(\displaystyle{ {2n \choose 2}}\) sposobów.
w czasie poruszania się po szachownicy dokładnie raz przetniemy przekątną. musieliśmy wykonać do tego czasu n ruchów w tym w zależności od przekątnej 0,1,2,...,n ruchów \(\displaystyle{ \uparrow}\). jak już jesteśmy na przekątnej to do celu możemy dojść na tyle samo sposobów na ile do niej doszliśmy (mamy symetrie) stąd tożsamość \(\displaystyle{ {2n \choose n}= \sum_{k=0}^{n} {n \choose k}^2}\)

-- 22 listopada 2009, 17:45 --

w pierwszym zadaniu może z osobami troche wyszło pod koniec niezrozumiale. to może tak:
mamy w rzędzie n+1 słupków. chcemy ileś słupków od lewej pomalować na biało i jeden z nich oznaczyć czerwona kreską a jeden z nie-białych słupków pomalować na różowo (ciekawe po co coś takiego robić hehe). to tak jak poprzednio jest prawa strona.
załóżmy jednak że bardzo nam się nudzi i chcemy sobie to urozmaicić (?)
dostawiamy n+2 -gi słupek. to samo możemy zrobić przez wybranie trzech słupków w kolejności A B C. te na lewo od B malujemy na biało. A oznaczamy czerwoną kreską a C malujemy na różowo. teraz wywalamy B i robota zrobiona a tożsamość wykazana-- 22 listopada 2009, 17:47 --a Ty pumbosza nie podpinaj sie pod temat pumboshy

[pumbosza]

Dzięki bardzo ,rozjaśniłeś mi ten temat nieco, na kolokwium może zamiast kiboli użyje jakiegoś bardziej subtelnego przykładu, co do loginu to używam tego, nawet nie wiem skąd mi się wziął ten drugi..Pozdrawiam, jeszcze raz dziękuję

[rotka]

Niby coś mi świta ale nie mogę tego ogarnąć.
Mam podobny problem. Moje zadanie brzmi:

Pokaż, że \(\displaystyle{ \sum_{k=0}^{n} {n \choose k}^{2}= {2n \choose n}}\)
i wskazówkę z której mam skorzystać: \(\displaystyle{ {n \choose k} = {n \choose n-k}}\) gdy \(\displaystyle{ k \le n}\)

\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}^{2}=\sum_{k=0}^{n} {n \choose k}{n \choose k}=\sum_{k=0}^{n} {n \choose k}{n \choose n-k}= {2n \choose n}}\) i co dalej?

O to chodzi? Jak to pokazać w ten sposób?

Pozdrawiam

[patry93]

Podbiję.
\(\displaystyle{ {n+1\choose 2}^2=\sum_{i=1}^{n} i^3}\)
Z książki "Wykłady z kombinatoryki" Z. Palka, A. Ruciński wiem, że można to pokazać kombinatorycznie przez zliczenie na dwa sposoby wszystkich prostokątów na szachownicy \(\displaystyle{ n \times n}\).
Otóż prostokątów o wymiarach \(\displaystyle{ i\times j}\) jest \(\displaystyle{ (n-i+1)(n-j+1)}\), więc wszystkich jest:
\(\displaystyle{ \sum_{i=1}^{n} \sum_{j=1}^{n} (n-i+1)(n-j+1) = ( \sum_{i=1}^{n} i )^2 = {n+1 \choose 2} ^2}\)
Jednak nie jest w owej pozycji napisane, jak zinterpretować prawą stronę, tj. \(\displaystyle{ \sum_{i=1}^{n} i^3}\)
Intuicja podpowiada, że albo inaczej "słownie" policzyć prostokąty, albo pokazać prawdziwość równości
\(\displaystyle{ \sum_{i=1}^{n} \sum_{j=1}^{n} (n-i+1)(n-j+1) = \sum_{i=1}^{n} i^3}\)
Lecz nie wiem jak.

-- 22 grudnia 2010, 18:20 --

Mój post odnosi się do tematu - 156372.htm , zadanie drugie z pierwszego postu. Tak żeby było wiadomo o co chodzi

[jgarnek]

link do dowodu: (mam nadzieję, że angielski to nie problem )-

streszczając: \(\displaystyle{ i^3}\) to ilość prostokątów (o bokach równoległych do osi OX, OY i wierzchołkach w punktach o naturalnych współrzędnych) ze współrzędną górnego prawego wierzchołka (x,y) gdzie max(x,y)=i.

Skąd to wynika? Wybierzmy dowolne 3 liczby naturalne z przedziału \(\displaystyle{ <0,i-1>}\), np. a,b,c (możemy to zrobić na \(\displaystyle{ i^3}\) sposobów). Jeżeli \(\displaystyle{ b \le c}\), to niech \(\displaystyle{ P=(a,b)}\) będzie lewym dolnym wierzchołkiem prostokąta, zaś \(\displaystyle{ R=(i, c+1)}\) prawym górnym wierzchołkiem. Punkty P, R jednoznacznie wyznaczają nam prostokąt o bokach równoległych do osi OX, OY i max(x,y)=i. Analogicznie dla \(\displaystyle{ c<b}\).

Inny 2 dowody (może bardziej przyjazne, choć nie na prostokątach, troszeczkę bardziej abstrakcyjne? ):