dowody algebraiczne i kombinatoryczne

[zekori]

1) Pokaż używając argumentów algebraicznych i kombinatorycznych następującą nierówność:
\(\displaystyle{ \sum_{k=0}^{n} \frac{\left( 2n\right)! }{\left( k!\right) ^{2}\left[\left(n-k \right)! \right] ^{2} } }\)
Podpowiedź od profesora: Rozważ wybory dwóch grup n osobowych spośród n kobiet i n mężczyzn, gdzie osoby mogą powtarzać się w
grupach. Rozważ podział wyborów ze względu na liczebność kobiet w pierwszej z grup.
2a) Pokazać, że \(\displaystyle{ \sum_{k=m}^{n} {k \choose r} = {n+1 \choose r+1} - {m \choose r+1} }\)
podpowiedź Uzasadnij równość \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = {n+1 \choose k+1} }\)
2b) \(\displaystyle{ \sum_{k=1}^{n} {m+k-1 \choose k} =\sum_{k=1}^{m} {n+k-1 \choose k} }\)
podpowiedź Rozważ ciągi binarne o n zerach i m jedynkach dzieląc je ze względu długość maksymalnego ciągu jedynek
stojącego na początku i nie zależnie ze względu na długość maksymalnego ciągu zer stojącego na początku.

[Premislav]

Przecież w pierwszym nie napisałeś żadnej nierówności.
2a)
Wskazówka niepoprawna (pewnie indeksy zwalone), ja bym uzasadnił coś takiego:
\(\displaystyle{ \sum_{k=r}^{n}{k\choose r}={n+1\choose r+1}}\)
a to się robi albo indukcją po \(\displaystyle{ n}\) przy ustalonym \(\displaystyle{ r}\), albo kombinatorycznie.
Potem wystarczy zapisać (zakładam \(\displaystyle{ m>r}\)) \(\displaystyle{ \sum_{k=m}^{n}{k\choose r}=\sum_{k=r}^{n}{k\choose r}-\sum_{k=r}^{m-1}{k\choose r}}\) i skorzystać z mojej wskazówki.
A „niezależnie" pisze się łącznie.

[zekori]

Przecież w pierwszym nie napisałeś żadnej nierówności.

Chodziło oczywiście o równość

Wskazówka niepoprawna (pewnie indeksy zwalone)

Zapomniałem jeszcze dopisać "dzieląc wybory zbiorów k + 1 elementów spośród n+ 1 elementów
ze względu na największy element."

[Premislav]

No to w pierwszym równości też nie napisałeś, poza tym nie wiem, co to „podział wyborów". Zwartą formę wyrażenia z pierwszego ja bym znalazł, zapisując to w formie
\(\displaystyle{ {2n\choose n}\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)
a tę ostatnią sumę zwinąłbym kombinatorycznie: mamy \(\displaystyle{ n}\) kobiet i \(\displaystyle{ n}\) mężyczn, chcemy z nich zrobić drużynę \(\displaystyle{ n}\)-osobową, opcjonalnie mieszaną. Z jednej strony czynimy to na \(\displaystyle{ \sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\) sposobów
(wybieramy \(\displaystyle{ k}\) kobiet i \(\displaystyle{ n-k}\) mężczyzn dla pewnego \(\displaystyle{ k\in\left\{0,1\ldots n\right\}}\)),
z drugiej strony skoro nie jest dla nas ważne, jaka będzie płeć członków drużyny, to możemy to potraktować jako wybór \(\displaystyle{ n}\) spośród \(\displaystyle{ 2n}\) osób, co odbywa się na \(\displaystyle{ {2n\choose n}}\) sposobów. W ten sposób mamy
\(\displaystyle{ \sum_{k=0}^{n}{n\choose k}{n\choose n-k}={2n\choose n}\\{2n\choose n}\sum_{k=0}^{n}{n\choose k}{n\choose n-k}={2n \choose n}^{2}}\)

[zekori]

No to w pierwszym równości też nie napisałeś

Przepraszam, ale próbuję robić te zadania dość długo i nie zauważyłem tego błędu . MIało tam być

\(\displaystyle{ \sum_{k=0}^{n} \frac{\left( 2n\right)! }{\left( k!\right) ^{2}\left[\left(n-k \right)! \right] ^{2} } ={2n \choose n}^{2} }\)

No to w pierwszym równości też nie napisałeś, poza tym nie wiem, co to „podział wyborów". Zwartą formę wyrażenia z pierwszego ja bym znalazł, zapisując to w formie
\(\displaystyle{ {2n\choose n}\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)

Mógłbyś wyjaśnić dlaczego
\(\displaystyle{ {2n\choose n}\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\) =\(\displaystyle{ \sum_{k=0}^{n} \frac{\left( 2n\right)! }{\left( k!\right) ^{2}\left[\left(n-k \right)! \right] ^{2} } ?}\)

[Premislav]

Jasne:
\(\displaystyle{ \sum_{k=0}^{n}\frac{(2n)!}{(k!)^{2}[(n-k)!]^{2}}=\frac{(2n)!}{(n!)^{2}}\sum_{k=0}^{n}\frac{(n!)^{2}}{(k!)^{2}[(n-k)!]^{2}}\\={2n\choose n}\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\cdot \frac{n!}{(n-k)!k!}={2n\choose n}\sum_{k=0}^{n}{n\choose k}{n\choose n-k}}\)

[zekori]

Jasne:
\(\displaystyle{ \sum_{k=0}^{n}\frac{(2n)!}{(k!)^{2}[(n-k)!]^{2}}=\frac{(2n)!}{(n!)^{2}}\sum_{k=0}^{n}\frac{(n!)^{2}}{(k!)^{2}[(n-k)!]^{2}}\\}\)

Nie mam pojęcia co tu się stało, nigdy tak tego nie rozpisywaliśmy

[Jan Kraszewski]

Nie mam pojęcia co tu się stało, nigdy tak tego nie rozpisywaliśmy

To zwykłe przekształcenie algebraiczne: ułamek pod sumą domnażasz przez jedynkę w postaci \(\displaystyle{ \frac{(n!)^2}{(n!)^2}, }\) a następnie czynnik
\(\displaystyle{ \frac{(2n)!}{(n!)^2} }\) wyłączasz przez sumę (czyli wyłączasz przez nawias).

JK