Trafiłam na ciekawą tożsamość do udowodnienia:
\(\displaystyle{ {n \choose m} ^{2} = \sum_{k=o}^{m} {n \choose m+k} {m+k \choose m} {m \choose k}}\)
Nie udało mi się zmęczyć jej indukcją, wprost, ani ułożyć bajki.
Może ktoś potrafi?
Pozdrawiam,
Askor-- 17 kwi 2012, o 09:19 --OK!
Chyba udało mi się odpowiedzieć sobie samej na ten post.
Zamieszczam dowód.
Najpierw, zauważmy, że
\(\displaystyle{ {n \choose p} {p \choose k} = {n \choose k} {n-k \choose p-k}}\).
Zastosujmy to do dwu pierwszych czynników w wyrazie ogólnym, a następnie wyłączmy stałą przed sumę:
\(\displaystyle{ \sum_{k=0}^{m} {n \choose m+k} {m+k \choose m} {m \choose k} =
\sum_{k=0}^{m} {n \choose m} {n - m \choose m+k-m} {m \choose k} =
{n \choose m} \sum_{k=0}^{m} {n - m \choose k} {m \choose k}}\).
Teraz wystarczy udowodnić, że
\(\displaystyle{ \sum_{k=0}^{m} {n - m \choose k} {m \choose k} = {n \choose m}}\),
to jest jednak jasne, bo biorąc pod uwagę, że
\(\displaystyle{ {a \choose b} = {a \choose a-b}}\)
można zapisać tę równość jako
\(\displaystyle{ \sum_{k=0}^{m} {n - m \choose k} {m \choose m-k} = {n \choose m}}\),
a ona wyjaśnia się przez ułożenie bajeczki:
"Weźmy stado n czworonogów - psów i kotów. Chcemy wybrać z niego m zwierząt. Można zrobić to na dwa sposoby: albo wybrać jak leci, otrzymując n po m możliwości, albo podzielić sobie, że wśród tych wybieranych m chcemy mieć k psów, a kotów m-k. Wtedy, suma po wszystkich k = 0, ..., m również da nam ilość wszystkich możliwych wyborów."
c.n.d.
Tożsamość z dwumianem - ciekawa.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Tożsamość z dwumianem - ciekawa.
Można od razu interpretacją kombinatoryczną.
Mamy \(\displaystyle{ n}\) żyraf, spośród których chcemy \(\displaystyle{ m}\) nauczyć baletu i \(\displaystyle{ m}\) nauczyć gry na mandolinie (być może niektóre będą nauczone obu czynności). Z jednej strony wyborów nauczanych czynności jest oczywiście \(\displaystyle{ \binom nm \binom nm}\).
Z drugiej strony możemy zliczać z uwagi na ilość żyraf, które będą uczyć się wyłącznie baletu. Może być ich oczywiście \(\displaystyle{ 0\le k \le m}\), przy czym jeśli jest ich \(\displaystyle{ k}\), to obu czynności uczy się w sumie \(\displaystyle{ m+k}\) żyraf. Tak więc najpierw na \(\displaystyle{ \binom{n}{m+k}}\) sposobów wybieramy te żyrafy. Następnie spośród nich na \(\displaystyle{ \binom{m+k}{m}}\) wybieramy te, które uczą się baletu, a spośród tych \(\displaystyle{ m}\) wybieramy jeszcze na \(\displaystyle{ \binom mk}\) sposobów te które uczą się wyłącznie baletu.
Natomiast w Twoim rozwiązaniu jeśli chcemy zachować jednolitość metody, to w końcówce zamiast bajki można użyć tożsamości Cauchy'ego:
\(\displaystyle{ \sum_k\binom{r}{m+k}\binom{s}{n-k}=\binom{r+s}{m+n}}\)
(choć jeden z jej dowodów jest właśnie też kombinatoryczny)
Q.
Mamy \(\displaystyle{ n}\) żyraf, spośród których chcemy \(\displaystyle{ m}\) nauczyć baletu i \(\displaystyle{ m}\) nauczyć gry na mandolinie (być może niektóre będą nauczone obu czynności). Z jednej strony wyborów nauczanych czynności jest oczywiście \(\displaystyle{ \binom nm \binom nm}\).
Z drugiej strony możemy zliczać z uwagi na ilość żyraf, które będą uczyć się wyłącznie baletu. Może być ich oczywiście \(\displaystyle{ 0\le k \le m}\), przy czym jeśli jest ich \(\displaystyle{ k}\), to obu czynności uczy się w sumie \(\displaystyle{ m+k}\) żyraf. Tak więc najpierw na \(\displaystyle{ \binom{n}{m+k}}\) sposobów wybieramy te żyrafy. Następnie spośród nich na \(\displaystyle{ \binom{m+k}{m}}\) wybieramy te, które uczą się baletu, a spośród tych \(\displaystyle{ m}\) wybieramy jeszcze na \(\displaystyle{ \binom mk}\) sposobów te które uczą się wyłącznie baletu.
Natomiast w Twoim rozwiązaniu jeśli chcemy zachować jednolitość metody, to w końcówce zamiast bajki można użyć tożsamości Cauchy'ego:
\(\displaystyle{ \sum_k\binom{r}{m+k}\binom{s}{n-k}=\binom{r+s}{m+n}}\)
(choć jeden z jej dowodów jest właśnie też kombinatoryczny)
Q.