Matematické Fórum

awm1 · 22. 03. 2010 00:07

Totálně jsem se zasekl u této úlohy:

Pomocí vhodné kombinatorické interpretace a použitím principu inkluze a exkluze spočítejte nasledující sumu pro n,m,j přirozené takové, že n ≤ j ≤ (m + n), t.j. vyjádřete tuto sumu jako nějaký výraz, který už bude bez sumy:

Ať na to koukám, jak chci, PIE tam nikde nevidím. Nevidíte ho tam někde vy?

Olin · 22. 03. 2010 11:42

Á, tato úložka mě ze všech v diskrétce bavila nejvíce. Dám jen tipy:

$(-1)^n$ poměrně jasně odkazuje na princip inkluze a exkluze - vždyť i v jeho vyjádření vzorcem se to nachází.

${n \choose i}$ je počet i-prvkových podmnožin n-prvkové množiny. Vzhledem k tomu, že se v PIE sčítá přes všechny možné počty množin v průniku, chtělo by to najít takový systém $n$ množin, ve kterém má průnik každých $i$ množin stejnou velikost pro $1 \leq i \leq n$ . A nejlépe by bylo, kdyby velikost toho průniku pak byla ${{m+n-i} \choose {j-i}}$ .

Stýv · 22. 03. 2010 12:17

přidám svou trošku do mlýna: mám $m$ jablek a $n$ hrušek.
$i=0$ ... vyberu si $0$ hrušek a k nim $j$ kusů libovolného ovoce
$i=1$ ... odečtu případy, kdy si vyberu $1$ hrušku a doplním do $j$ kusů libovolně
$i=2$ ... přičtu zpátky případy, kdy si vyberu $2$ hrušky a zbytek libovolně
...
teď se zamyslím, co takovýmhle způsobem můžu pomocí PIE spočítat;)

awm1 · 24. 03. 2010 21:54

↑ Stýv:

Právě to je to, co mi uniká. Zkoušel jsem si to nakreslit a poupravit zadanou sumu, ale vycházejí mi stále prazvláštní součiny kombinačních čísel. Wolfram Alpha – http://www.wolframalpha.com/input/?i=su … j%3D0+to+n – dává výsledek plný funkcí, se kterými jsem se doposud nesetkal. Dospěl jsem akorát k tomu, že v součinu uvnitř sumy je kromě n-tého kombinačního čísla i součin prvků na "diagonále" v Pascalově trojúhelníku. Pokoušel jsem se to vyjádřit jako součin prvků, ale stále mi to nevychází.

V čem dělám chybu? Nešlo by ten vnitřek sumy vyjádřit nějak jinak, aby se s tím lépe počítalo?

Stýv · 24. 03. 2010 23:06

není třeba nic počítat, stačí použít tu úvahu... napíšu jí ještě jinak:
1. spočítám si všechny možný výběry
2. odečtu ty, který obsahujou hrušku
3. protože jsem některý odečetl víckrát, tak je zase zpátky přičtu, zase sem jich přičetl moc, tak některý odečtu ... prostě standardní použití PIE

třetí bod jsou víceméně takový korekce, takže se zamysli, co dávají první dva body;)

ps: pokud píšu nějaký nesmysly, tak mě někdo zarazte:)

auditor · 04. 11. 2014 23:15

↑ Stýv:

Dobrý den,

řeším stejnou úlohu. Vzal jsem si jako příklad 2 hrušky (n), 2 jablka (m) a vybírám 3 kusy ovoce (j). Po dosazení do vzorce uvedeného v prvním příspěvku mi vychází počet výběrů 0, přitom má podle mě vyjít 2 (výběr 2 hrušek a 1 jablka nebo 1 hrušky a 2 jablek). Dále nerozumím, co znamenají všechny možné výběry v bodě 1.

Předem děkuji za Vaše názory.

jelena · 07. 11. 2014 17:31

Zdravím,

vzhledem k sestavě diskutujících přesunu do Pokročilých VŠ.

↑ auditor: já tomu rozumím tak, že kolega Stýv všemi výběry rozumí, že vybere potřebný počet ovoce, bez ohledu na to, co to je za ovoce. Potom to probírá a vyřazuje skladby, co se mu nehodí.

Stýv napsal(a):
ps: pokud píšu nějaký nesmysly, tak mě někdo zarazte:)

Kdo by si to dovolil, kolego Stýve? :-)

Matematické Fórum

#1 22. 03. 2010 00:07

Princip inkluze a exkluze v sumě kombinačních čísel

#2 22. 03. 2010 11:42

Re: Princip inkluze a exkluze v sumě kombinačních čísel

#3 22. 03. 2010 12:17

Re: Princip inkluze a exkluze v sumě kombinačních čísel

#4 24. 03. 2010 21:54

Re: Princip inkluze a exkluze v sumě kombinačních čísel

#5 24. 03. 2010 23:06

Re: Princip inkluze a exkluze v sumě kombinačních čísel

#6 04. 11. 2014 23:15

Re: Princip inkluze a exkluze v sumě kombinačních čísel

#7 07. 11. 2014 17:31

Re: Princip inkluze a exkluze v sumě kombinačních čísel

Stýv napsal(a):

Zápatí