Tożsamość - Wykaż, że...

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
dosia
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 kwie 2020, o 15:36
Płeć: Kobieta
wiek: 22

Tożsamość - Wykaż, że...

Post autor: dosia » 30 kwie 2020, o 15:59

Witam,
posiłkuję się z tożsamością już któryś dzień z rzędu:
\(\displaystyle{ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}}\)

Doprowadziłam do takowej postaci (nie wykluczam błędów), nie wiem czy mój tok rozumowania jest poprawny.
[ciach]
Ostatnio zmieniony 30 kwie 2020, o 20:21 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nieregulaminowy zapis - obrazki zamiast zapisu w LaTeX-u.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 2764
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 71 razy
Pomógł: 897 razy

Re: Tożsamość - Wykaż, że...

Post autor: Janusz Tracz » 30 kwie 2020, o 16:06

A może historyjka kombinatoryczna wystarczy? Weź dwa zbiory o \(\displaystyle{ n}\) elementach (parami różnych). Na ile sposobów można wybrać z nich \(\displaystyle{ n}\) elementów?

\(\displaystyle{ 1)}\) Można połączyć te dwa zbiory w zbiór \(\displaystyle{ 2n}\) elementowy i wybrać \(\displaystyle{ n}\) na \(\displaystyle{ {2n \choose n} }\) sposobów.

\(\displaystyle{ 2)}\) można z pierwszego wybrać \(\displaystyle{ k}\) na \(\displaystyle{ {n \choose k} }\) i z drugiego \(\displaystyle{ n-k}\) na \(\displaystyle{ {n \choose n-k} }\) sposobów idąc po wszystkich \(\displaystyle{ k\in\left\{ 0,1,...,n\right\} }\) dostaniemy wszystkie możliwości. Stąd mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}}\)

Czyli mamy \(\displaystyle{ \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}= {2n \choose n} }\)

dosia
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 kwie 2020, o 15:36
Płeć: Kobieta
wiek: 22

Re: Tożsamość - Wykaż, że...

Post autor: dosia » 30 kwie 2020, o 19:58

Wiem, że
\(\displaystyle{ \binom{n}{n-k}=\binom{n}{k}}\)
Niestety nadal nie wiem jak przeprowadzić dowód.
Byłabym wdzięczna za wytłumaczenie krok po kroku.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14860
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 120 razy
Pomógł: 4921 razy

Re: Tożsamość - Wykaż, że...

Post autor: Premislav » 30 kwie 2020, o 20:14

dosia, Twoja próba jest niestety niepoprawna, a to dlatego, że \(\displaystyle{ (2n)!\neq 2\cdot n!}\), więc nie możesz tam sobie skrócić \(\displaystyle{ n!}\). Poza tym uważam, że wyjaśnienie, które przedstawił Janusz Tracz, jest dość dokładne.

Skoro wiesz, czego masz dowodzić, to można też przeprowadzić indukcję po \(\displaystyle{ n}\), choć jest to znacznie mniej eleganckie i nie polecam. Jeszcze inny pomysł to policzenie na dwa sposoby współczynnika przy \(\displaystyle{ x^{n}}\) w wielomianie \(\displaystyle{ P(x)=(1+x)^{2n}}\). Z jednej strony na mocy wzoru dwumianowego Newtona wynosi on oczywiście \(\displaystyle{ {2n\choose n}}\), z drugiej strony możemy zapisać
\(\displaystyle{ (1+x)^{2n}=(1+x)^{n}(1+x)^{n}}\), rozwinąć to ze wzoru dwumianowego Newtona w
\(\displaystyle{ \left(\sum_{k=0}^{n}{n\choose k}x^{k}\right)\left(\sum_{l=0}^{n}{n\choose l}x^{l}\right)}\)
i wymnożyć. Po wymnożeniu widzimy, że przy \(\displaystyle{ x^{n}}\) będzie stal współczynnik równy
\(\displaystyle{ \sum_{0\le k, l\le n, \ k+l=n}{n\choose k}{n\choose l}=\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)

ODPOWIEDZ