Matematické Fórum

Aquabellla · 20. 05. 2011 15:48

Zdravím, potřebovala bych pomoc s odvozením vzorce pro kombinaci s opakováním.

Vím, že se to dělá přes přihrádkový systém, kde $P'(k, n-1) = K'(k, n)$
Vzorec pro permutaci s opakováním je: $P'(k_1, k_2, ... , k_n) = \frac{(k_1 + k_2 + ... + k_n)!}{(k_1! \cdot k_2! \cdot ... \cdot k_n!)}$
Ale jak se z toho dostane tento vzorec? $K'(k, n) = {n + k - 1\choose k}$

Předem děkuji

Kwítko

pokud se nemýlím, tak by to mělo být dopočítáno jako normální "en nad ká" pro kombinace, akorát "en=n+k-1"
takže (n+k-1)! /(n+k-1-k)!k! tzn (n+k-1)! / (n-1)!k!

Aquabellla · 20. 05. 2011 16:09

↑ Kwítko:

já vím, že se toto dá takhle přepsat: $K'(k, n) = {n + k - 1\choose k} = \frac{(n + k - 1)!}{(n - 1)! \cdot k!}$ ale mně jde o tom, jak se z té permutace konkrétně dostat ke kombinaci.

$P'(k, n-1) = K'(k, n)$
$P'(k_1, k_2, ... , k_{n-1}) = \frac{(k_1 + k_2 + ... + k_{n-1})!}{(k_1! \cdot k_2! \cdot ... \cdot k_{n-1}!)}$
$\frac{(k_1 + k_2 + ... + k_{n-1})!}{(k_1! \cdot k_2! \cdot ... \cdot k_{n-1}!)} = \frac{(n + k - 1)!}{(n - 1)! \cdot k!}$ - dokázat tento vztah

zdenek1 · 20. 05. 2011 16:40

↑ Aquabellla:
Pomůže?

Rumburak

↑ Aquabellla:
Je potřeba nejprve se na kombinace podívat srozumitelným způsobem. Označme $\mathbb N :=\{0, 1, 2, ... \}$ .
Předpokládejme, že je dána konečná množna $M$ o $m$ prvcích a číslo $k\in \mathbb N$ . Určit kombinaci s opakováním
$k$ -té třídy z prvků mnžiny $M$ (tj. z $m$ prvků) znamená určit funkci $f:M \to \mathbb N$ splňující podmínku

(1) $\sum_{x\in M}f(x) = k$ ,

kde číslo $f(x)$ znamená počet výskytů prvku $x$ v příslušné kombinaci. Množinu všech takových funkcí označme $K(m,k)$ .
Našim cílem tedy bude určit počet prvků množiny $K(m,k)$ .

Pro zjednodušení symboliky předpokládejme, že $M = \{1,2, ..., m\}, \,\,m > 0$ . Dále položme $M' := \{1,2, ..., m-1\}$ .
Všechny funkce z $K(m,k)$ rozdělíme do disjunktních skupin $A_0, A_1, ..., A_k$ tak, aby množina $A_i$ vždy obsahovala právě takové
funkce z $K(m,k)$ , pro které je $f(m) = i$ . Tedy $K(m,k) = A_0 \cup A_1 \cup ... \cup A_k$ . Vezměme $f \in A_i$ .
Když její definiční obor (jímž je $M$ ) zúžíme na množinu $M'$ , dostaneme funkci $g \in K(m-1,k-i)$ a naopak, každou funkci
$g \in K(m-1,k-i)$ můžeme v bodě $m$ dodefinovat hodnotou $i$ a tak dostaneme funkci patřící do $A_i$ a tím i do $K(m,k)$ .
To znamená, že množina $A_i$ má stejný počet prvků jako $K(m-1,k-i)$ .

Pro číslo $|K(m,k)|$ udávající počet prvků množiny $K(m,k)$ tak získáváme rekurentní vztah

(2) $|K(m,k)| = \sum_{i=0}^k |A_i| = \sum_{i=0}^k |K(m-1,k-i)| = \sum_{j=0}^k |K(m-1,j)|$ ,

z něhož odvodíme výsledek. (Poslední úprava v (2) spočívala jen v substituci sumačního indexu $j = k-i$ . )
Nyní musím přestat, dokončím snad zítra.

EDIT. I když je úloha již vyřešena, dokončím svůj postup, jak jsem slíbil. Snad se to bude hodit pro příští příležitost.

Rozeberme singulární případy:

(3) $|K(1,k)| = 1$ ,
neboť zde je jedinou možnou kombinací k-krát vybrat ten jediný prvek, který množina $M$ obsahuje. Tato kombinace je representována
funkcí $f$ , která na jednoprvkové množině $M$ nabývá hodnoty $k$ .

(4) $|K(m,0)| = 1$ ,
neboť zde počítáme "prázdné" kombinace, které z M nevybírají žádný prvek, a taková je pouze jedna - representovaná funkcí $f \equiv 0$ .

(5) $|K(0,0)| = 1$ ,

neboť tento případ znamená, že $M=\emptyset$ , a tudíž jedinou možnou kombinací je opět prázdná kombinace, které je v tomto případě
representována prázdnou funkcí (jejímž def. oborem a zároveň i oborem hodnot je $\emptyset$ , podmínka (1) je pak splněna na základě
definice "prázdného" součtu) .

(6) $|K(0,k)| = 0$ pro $k > 0$ ,

protože funkce $f$ , která by zajistila splnění podmínky (1), neexistuje.

Rekursi podle vzorce (2) můžeme provést celkem (m-1)-krát. Opakováním prvního kroku

$|K(m,k)| = \sum_{j_1=0}^k |K(m-1,j_1)|$
tak postupně dostáváme

(7) $|K(m,k)| = \sum_{j_1=0}^k |K(m-1,j_1)| = \sum_{j_1=0}^k\sum_{j_2=0}^{j_1} |K(m-2,j_2)|=...=\\=\sum_{j_1=0}^k\sum_{j_2=0}^{j_1}...\sum_{j_{m-1}=0}^{j_{m-2}} |K(1,j_{m-1})|\text{ }$ .

Vzhledem k (3), (4) dosadíme do výsledku v (7) $|K(1,j_{m-1})| = 1 ={j_{m-1} \choose 0}={0+j_{m-1} \choose 0}$ a obdržíme

(8) $|K(m,k)| = \sum_{j_1=0}^k\sum_{j_2=0}^{j_1}...\sum_{j_{m-1}=0}^{j_{m-2}}{0+j_{m-1} \choose 0}$ .

Pravou stranu pak postupně posčítáme podle známého vzorce $\sum_{i=0}^n {p+i \choose p} = {p+1+n \choose p+1}$ , tedy

$\sum_{j_{m-1}=0}^{j_{m-2}}{0+j_{m-1} \choose 0}= {1+j_{m-1} \choose 1}$ ,

a obdobně dále, celkem

$|K(m,k)| = \sum_{j_1=0}^k\sum_{j_2=0}^{j_1}...\sum_{j_{m-2}=0}^{j_{m-3}}{1+j_{m-2} \choose 1} = \sum_{j_1=0}^k\sum_{j_2=0}^{j_1}...\sum_{j_{m-3}=0}^{j_{m-4}}{2+j_{m-3} \choose 2} =\\= ... = \sum_{j_1=0}^k {m-2+j_1 \choose m-2} = {m-1+k \choose m-1}= {m + k - 1 \choose k}$ .

Aquabellla · 20. 05. 2011 17:11

↑ zdenek1:

Ha, už jsem tomu přišla na kloub, díky :-)

Ono je potřeba si uvědomit, že $8 = k_1 + k_2 + ... + k_n = k$ , kde $n = 3$ , a $2 = n - 1$ . Pak už stačí dosadit.

Ještě jednou díky všem!

Rumburak · 21. 05. 2011 14:11

↑ Aquabellla:
Dokončil jsem svůj příspěvek ze včerejška ↑ Rumburak:.
Výpočet sice ani zde není jednoduchý, ale za jeho přednost považuji to, že se nemusím zabývat žádnými nepřehlednými "příhrádkami".

Matematické Fórum

#1 20. 05. 2011 15:48

Vzorec pro kombinaci s opakováním

#2 20. 05. 2011 15:52 — Editoval Kwítko (20. 05. 2011 15:53)

Re: Vzorec pro kombinaci s opakováním

#3 20. 05. 2011 16:09

Re: Vzorec pro kombinaci s opakováním

#4 20. 05. 2011 16:40

Re: Vzorec pro kombinaci s opakováním

#5 20. 05. 2011 17:00 — Editoval Rumburak (23. 05. 2011 16:00)

Re: Vzorec pro kombinaci s opakováním

#6 20. 05. 2011 17:11

Re: Vzorec pro kombinaci s opakováním

#7 21. 05. 2011 14:11

Re: Vzorec pro kombinaci s opakováním

Zápatí