Matematické Fórum

Marty151 · 28. 10. 2014 15:52

Ahoj, prosím o radu s příklady:

Sečtěte, čemu se výrazy rovnají a vysvětlete kombinatorickou interpretací.
1)
$\sum_{k=0}^{n}k{n \choose k}$
2)
$\sum_{k=0}^{n}k^{2}{n \choose k}$

1) První výraz jsem sečetl na $\frac{n}{2}2^{n}$ , ale nevím kombinatorickou interpretaci.
2) U druhého jsem výraz nedokázal ani sečíst.

Díky!

zdenek1 · 28. 10. 2014 19:46

↑ Marty151:
1) je jednoduchá
máš n-prvkovou množinu. Vytvoříš všechny podmnožiny, spočítáš jejich prvky a počty sečteš.
Jsou dvě možnosti, jak to udělat.
a) je ${n\choose1}$ jednoprvkových podmnožin a každá přispívá jedním prvkem, ${n\choose2}$ dvouprvkových podmnožina a každá příspívá dvěma prvky atd. Tj. celkem
$1{n\choose1}+2{n\choose2}+\ldots +(n-1){n\choose n-1}+n{n\choose n}$
(vždy můžeš na začátek přidat nulu jako $0{n\choose0}$
b) druhá možnost: ke každé podmnožině přidám její doplněk. Tím získám $n$ prvků a podmnožin je $2^n$ . Jenže tímto způsobem počítám každou podmnožinu dvakrát, tak to vydělím dvěma. Tj. celkem
$n\cdot 2^{n-1}$

Oba způsoby výpočtu musí dávat stejný výsledek

Marty151 · 28. 10. 2014 19:56

To, že ke každé podmnožině přidám její doplněk znamená, že používám ${n \choose k}={n \choose n-k}$ a tedy dostanu $n{n\choose0}+n{n\choose1}+n{n\choose2}+\ldots$ ?

zdenek1 · 28. 10. 2014 20:06

↑ Marty151:
Já psal o podmnožinách
Tj. např. mám množinu $\{a,b,c,d,e\}$ , vyberu podmnožinu $\{a,e\}$ , přidám doplněk $\{b,c,d\}$ a mám celou množinu.
Samozřejmě, když pak počítáš ty počty, tak to můžeš rozepsat jak navrhuješ, ale připadá mi to zbytečné (teda pokud víš, že počet všech podmnožin n-prvkové množiny je $2^n$ ).

Marty151 · 28. 10. 2014 20:12

↑ zdenek1:
To že počet všech podmnožin n-prvkové množiny je $2^n$ vím, jen mi nebylo jasné odůvodnění dělení 2 kvůli počítání každé množiny dvakrát.