Matematické Fórum

Ondrik_B · 28. 05. 2017 18:18

Ahoj, řeším tento příklad.

Najděte hodnotu součtu

$\sum_{k=0}^{n} k {n \choose k}^2$

V autorskym reseni je krok jemuz nerozumim:
$n\sum_{k=1}^{n} {n-1 \choose k-1}{n \choose n-k} = n {2n-1 \choose n-1}$

Myslel jsem ze byla pouzita tato identita, ale nejak mi tam nesedi:
$\sum_{k=0}^{n} {p \choose k}{q \choose n-k} = {p+q \choose n}$

Napada vas neco?

Rumburak · 29. 05. 2017 13:44

↑ Ondrik_B:
Ahoj.

Rovnost

$n\sum_{k=1}^{n} {n-1 \choose k-1}{n \choose n-k} = n {2n-1 \choose n-1}$

je zřejmě ekvivalentní s

$\sum_{k=1}^{n} {n-1 \choose k-1}{n \choose n-k} = {2n-1 \choose n-1}$ .

Ondrik_B · 30. 05. 2017 07:50

↑ Rumburak:

A z čeho to plyne?

Rumburak · 30. 05. 2017 12:28

První rovnost dostaneme vynásobením druhé rovniosti číslem $n$ , o němž se v úloze
patrně předpokládá, že je nenulové, nemá-li jít o úlohu triviální.

Ondrik_B · 31. 05. 2017 08:14

↑ Rumburak:

Patrně jsem se špatně vyjádřil. To vynásobení je mi jasný. Není mi jasný proč se ta suma rovná tomu kombinančímu číslu.

jarrro · 31. 05. 2017 09:14 — Editoval jarrro (31. 05. 2017 09:18)

Rovnosť $\sum_{k=0}^{m} {p \choose k}{q \choose m-k} = {p+q \choose m}$
platí, pretože ak uvažujeme dve disjunktné množiny s počtom prvkov p resp. q, tak m-prvkovú podmnožinu ich zjednotenia dostaneme tak, že vyberieme niekoľko prvkov z p-prvkovej množiny a zvyšok z q- prvkovej množiny.
Rovnosť
$\sum_{k=1}^{n} {n-1 \choose k-1}{n \choose n-k} = {2n-1 \choose n-1}$
Je špeciálny prípad vyššie uvedenej rovnosti pre
$p=n-1, q=n, m=n-1$
Lepšie to vidno ak sa uváži, že $n-k=$n-1$-$k-1$$
A tiež $$1\leq k\leq n$\Leftrightarrow$0\leq k-1\leq n-1$$