Výrazy s faktoriálem a kombinačními čísly
Rozhodovačka
Výrazy s faktoriálem a kombinačními čísly
Pojem faktoriál používáme nejčastěji při řešení kombinatorických úloh. Faktoriál čísla n je součin všech celých kladných čísel od jedné do n. Platí tedy: n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n
Speciálně: 0!=1
Častou úpravou výrazů s faktoriály je částečný rozklad faktoriálu na součin několika hodnot a faktoriál menšího čísla.
Příklad – úprava výrazu \dfrac{(x+1)!}{(x-1)!}
- Faktoriál v čitateli rozložíme tak, aby obsahoval faktoriál ze jmenovatele: \dfrac{(x+1)!}{(x-1)!}=\dfrac{(x+1)x(x-1)!}{(x-1)!}
- Výraz s faktoriálem můžeme vykrátit a dostaneme: (x+1)x=x^2+x
Faktoriál také používáme pro definici kombinačního čísla. Pro n\geq k\geq 0 platí: \dbinom nk=\dfrac{n!}{k!(n−k)!}
Při úpravách výrazů s kombinačními čísly můžeme kromě faktoriálů použít některý z následujících vztahů:
- Je n možností, jak vybrat jeden z n prvků: \dbinom n1=n
- Je jedna možnost, jak vybrat 0 z n prvků, a také je jedna možnost, jak vybrat všech n z n prvků (pro n=0 to jsou dokonce stejná kombinační čísla): \dbinom nn=\dbinom n0=1 \dbinom 00=1
- Máme stejný počet možností, jak vybrat skupinku k prvků z n prvků, jako je počet možností, jak vybrat n-k prvků, které do skupinky nezařadíme: \dbinom nk=\dbinom n{n-k}
- Vybíráme-li k prvků z n+1, máme tolik možností, jako když sečteme počet možností výběru k a k-1 prvků z n prvků: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Zdůvodnění vztahu \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Uvažme n prvků, ke kterým přidáme ještě (n+1). prvek (označme ho X), takže celkem máme n+1 prvků. Vybíráme k prvků z našich n+1 prvků. Kolik máme možností? (Aneb čemu se rovná \dbinom {n+1}k?)
- Takové výběry se dají rozdělit do dvou skupin, podle toho, jestli je
nebo není vybrán prvek X.
- Máme \dbinom nk možností, jak vybrat k prvků z původních n prvků, mezi kterými není X.
- Dále máme \dbinom n{k-1} možností, jak vybrat k-1 prvků z původních n prvků, mezi kterými není X, a přidat k nim do výběru X.
- Celkem tedy podle pravidla součtu platí: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
Příklad – úprava výrazu \dbinom {r+1}r
- Binomické číslo rozložíme na podíl faktoriálů: \dbinom {r+1}r=\dfrac{(r+1)!}{r!((r+1)-r)!}
- Upravíme: \dfrac{(r+1)!}{r!(r+1-r)!}=\dfrac{(r+1)!}{r!1!}
- Víme, že 1!=1. Faktoriál v čitateli dále rozložíme: \dfrac{(r+1)!}{r!1!}=\dfrac{(r+1)r!}{r!\cdot1}
- Nakonec vykrátíme výraz s faktoriálem: \dfrac{(r+1)r!}{r!}=r+1
Příklad – úprava výrazu \dbinom l4+\dbinom l5
- Použijeme vztah pro úpravu dvou binomických čísel: \dbinom {n+1}k=\dbinom nk+\dbinom n{k-1}
- Pro n=l a k=5 dostaneme: \dbinom l4+\dbinom l5=\dbinom {l+1}5
Úpravy výrazů s faktoriálem (těžké)
Nyní se mohou opakovat už vyřešená zadání.
