Matematické Fórum

nordec · 05. 02. 2009 19:59

Pro každé "k" a "n" přirozené najděte vzorec, pro počet uspořádaných k-tic $(a_1, a_2, .., a_k)$ přirozených čísel takových, že $a_i > 0$ pro všechny $i$ a $a_1 + a_2 + a_3 + ... + a_k = n$ .

Tady ani nevím, jak mám začít.

musixx · 06. 02. 2009 09:13 — Editoval musixx (06. 02. 2009 09:15)

↑ nordec: Ja bych zacal tak, ze bych neuvazoval podminku $a_i>0$ . Pak je to takova ta klasicka predstava kolecek a carek: Mame n kolecek nakreslenych vedle sebe a (k-1) svislych carek, ktere strkame mezi tato kolecka. Pocet kolecek mezi carkama (a i pred prvni a za posledni carkou) jsou ona a_i. Priklad:

ooo|oo|oo|ooo|||o|o

znamena
a1 = 3, a2 = 2, a3 = 2, a4 = 3, a5 = 0, ...

Mam tedy celkem n+k-1 objektu a vybiram mista treba pro onech n kolecek --> celkem $n+k-1\choose n$ moznosti.

A ted bych principem inkluze a exkluze vyrazoval moznosti, kde je nektere a_i nula. Chci-li mit jedno a_i nulove, pak mam stale n kolecek, ale uz jen k-2 carek, tedy $n+k-2\choose n$ . A $k\choose1$ zpusoby jsem vybral to a_i, ktere bude nula. Celkem tedy musim odecist ${k\choose1}\cdot{n+k-2\choose n}$ . Ted jsem ale zase odecetl dvakrat ty pripady, kdy jsou dve ruzna a_i a a_j nulova --> zase jednou takove pripady prictu. Proste klasicka inkluze a exkluze.

Celkem mi to dava: ${n+k-1\choose n}-\sum_{i=1}^{k-1}(-1)^{i+1}{k\choose i}{n+k-1-i\choose n}$ (suma je jen do k-1, protoze samozrejme nema smysl chtit, aby vsechna a_i byly nuly). Alespon jako mala kontrola spravnosti se da pouzit to, ze velice casto je to cislo pred sumou vlastne nulty scitanec (to alespon castecne muze verifikovat vypocet), tedy hledany vzorec by mel byt
$\sum_{i=0}^{k-1}(-1)^i{k\choose i}{n+k-1-i\choose n}$ .

Poznamka: Je docela mozne, ze kdyz se na situaci podivame nejak jinak, tak dostaneme primo neco bez sumy. Uvidime, jestli se to pokusi spocitat jeste nekdo nejak jinak.

Kondr · 06. 02. 2009 12:33

Řešilo se to tu už mockrát a včera jsem nenašel odkaz, tak jsem doufal, že ho najde někdo jiný. Trik je v tom přeformulovat tu úlohu takto: jak rozdělit n kuliček do k přihrádek, aby v každé byla alespoň jedna? No tak, že do každé dáme jednu kuličku a zbylých n-k kuliček rozdělíme do přihrádek pomocí k-1 oddělovačů. Každé takové rozdělení je kódované posloupností, která obsahuje k-1 oddělovačů a n-k kuliček. Takových posloupností je ${n-1\choose k-1}$ .

EDIT: Koukám že musixx začal podobně :) akorát je tam ta finta s "předplněním" přihrádek.

Matematické Fórum

#1 05. 02. 2009 19:59

kombinatorika - nalezení vzorce

#2 06. 02. 2009 09:13 — Editoval musixx (06. 02. 2009 09:15)

Re: kombinatorika - nalezení vzorce

#3 06. 02. 2009 12:33

Re: kombinatorika - nalezení vzorce

Zápatí