Kombinační čísla
Binomická věta
Při řešení různých algebraických úloh potřebujeme občas umocnit dvojčlen
a + b na přirozené číslo n,
tj. vypočítat (a + b)n.
Nejspíš už znáte vzorce pro
n = 1,
n = 2
a n = 3:
(a + b)1 = a + b
(a + b)2 =
a2 + 2ab + b2
(a + b)3 =
a3 + 3a2b + 3ab2 + b3
Vypočítáme ještě (a + b)4:
(a + b)4 = (a + b)3 · (a + b) =
= (a3 + 3a2b + 3ab2 + b3)
· (a + b) =
= a4
+ 3a3b
+ 3a2b2
+ ab3
+ a3b
+ 3a2b2
+ 3ab3
+ b4 =
= a4
+ 4a3b
+ 6a2b2
+ 4ab3 + b4
Porovnáme koeficienty u jednotlivých členů s hodnotami v Pascalově trojúhelníku:
| (a + b)1 |
a + b
|
1 1 |
| (a + b)2 |
a2 + 2ab + b2
|
1 2 1 |
| (a + b)3 |
a3 + 3a2b + 3ab2 + b3
|
1 3 3 1 |
| (a + b)4 |
a4 + 4a3b + 6a2b2
+ 4ab3 + b4
|
1 4 6 4 1 |
Je vidět, že koeficienty v mnohočlenech odpovídají hodnotám v Pascalově trojúhelníku;
každému mnohočlenu takto odpovídá právě jeden řádek Pascalova trojúhelníku.
Tato vlastnost platí nejen pro n = 1, 2, 3 a 4,
ale platí pro libovolné n z množiny přirozených čísel:
Pro všechna čísla
a,
b a každé přirozené číslo
n platí
| (a + b)n = |
( | n
0 | ) | an + |
( | n
1 | ) | an − 1 b + |
( | n
2 | ) | an − 2 b2 |
+ … + |
( | n
k | ) |
an − k bk |
+ … + |
( | n
n − 1 | ) | a bn − 1 + |
( | n
n | ) | bn |
Kombinatorický důkaz
Důkaz matematickou indukcí
Kombinatorický důkaz
Nejprve si ukážeme, proč platí binomická věta pro
n = 3:
Víme, že platí
(
a +
b)
3
= (
a +
b)(
a +
b)(
a +
b).
Při roznásobování necháme prvky v takovém pořadí, v jakém jsou v původním zápisu:
(
a +
b)(
a +
b)(
a +
b)
=
aaa +
aab +
aba +
baa +
abb
+
bab +
bba +
bbb.
Každý ze sčítanců je uspořádaná trojice z prvků
a
a
b. Sečít lze právě takové sčítance, které mají stejný počet prvků
a
a stejný počet prvků
b, tedy např.
aab + aba + baa.
Počet trojic se dvěma prvky
a a jedním prvkem
b je
| P'(2, 1) = |
3! 2! 1! |
= |
( | 3
1 | ) |
, |
podobně počet trojic s jedním prvkem
a a dvěma prvky
b je
| P'(1, 2) = |
3! 1! 2! |
= |
( | 3
2 | ) |
. |
Trojice obsahující tři prvky
a je jen jedna, stejně tak trojice obsahující
tři prvky
b. Platí tedy
| (a + b)3 = a3 + |
( | 3
1 | ) |
a2b + |
( | 3
2 | ) |
ab2 + b3 |
= |
( | 3
0 | ) |
a3 + |
( | 3
1 | ) |
a2b + |
( | 3
2 | ) |
ab2 + |
( | 3
3 | ) |
b3 |
. |
V obecném případě umocnění výrazu (
a +
b)
n
postupujeme stejně.
(
a +
b)
n
= (
a +
b)(
a +
b) … (
a +
b);
vynásobením těchto
n dvojčlenů dostaneme podobně jako v předchozím případě
součet několika různých
n-tic prvků
a a
b:
| n-tice složená jen z prvků a je jen jedna, |
| n-tic složených z (n − 1) prvků a
a jednoho prvku b je P'(n − 1, 1) = |
( | n
1 | ) |
, |
| n-tic složených z (n − 2) prvků a
a dvou prvků b je P'(n − 2, 2) = |
( | n
2 | ) |
, |
| a tak dál, obecně n-tic složených
z (n − k)
prvků a a k prvků b je
P'(n − k, k) = |
( | n
k | ) |
. |
Po sečtení všech odpovídajích
n-tic dostáváme:
| (a + b)n = |
an + |
( | n
1 | ) | an − 1 b + |
( | n
2 | ) | an − 2 b2 |
+ … + |
( | n
k | ) |
an − k bk |
+ … + |
( | n
n − 1 | ) | a bn − 1 + |
bn. |
| Protože platí 1 = |
( | n
0 | ) |
a také 1 = |
( | n
n | ) |
, dostáváme |
| (a + b)n = |
( | n
0 | ) | an + |
( | n
1 | ) | an − 1 b + |
( | n
2 | ) | an − 2 b2 |
+ … + |
( | n
k | ) |
an − k bk |
+ … + |
( | n
n − 1 | ) | a bn − 1 + |
( | n
n | ) | bn. |
Tím je binomická věta dokázána.
Důkaz matematickou indukcí
1. Pro
n = 1 platí
| (a + b)1 = |
( | 1
0 | ) | a + |
( | 1
1 | ) | b |
= a + b. |
2. Předpokládejme, že věta platí pro nějaké
n =
k,
platí tedy
| (a + b)k = |
( | k
0 | ) | ak + |
( | k
1 | ) | ak − 1 b + |
( | k
2 | ) | ak − 2 b2 |
+ … + |
( | k
k − 1 | ) | a bk − 1 + |
( | k
k | ) | bk |
Za tohoto předpokladu dokážeme, že věta platí také pro
n =
k + 1.
Víme, že (
a +
b)
k + 1 =
(
a +
b) · (
a +
b)
k.
Podle indukčního předpokladu můžeme výraz (
a +
b)
k
rozvinout podle binomické věty:
| (a + b)k + 1 =
(a + b) · |
[ |
( | k
0 | ) | ak + |
( | k
1 | ) | ak − 1 b + |
( | k
2 | ) | ak − 2 b2 |
+ … + |
( | k
k − 1 | ) | a bk − 1 + |
( | k
k | ) | bk |
] |
Po roznásobení dostáváme:
| (a + b)k + 1 = |
( | k
0 | ) | ak + 1 + |
( | k
1 | ) | ak b + |
( | k
2 | ) | ak − 1 b2 |
+ … + |
( | k
k − 1 | ) | a2 bk − 1 + |
( | k
k | ) | a bk + |
| | + |
( | k
0 | ) | ak b + |
( | k
1 | ) | ak − 1 b2 + |
( | k
2 | ) | ak − 2 b3 |
+ … + |
( | k
k − 1 | ) | a bk + |
( | k
k | ) | bk + 1 |
Odpovídající členy sečteme:
| (a + b)k + 1 = |
( | k
0 | ) | ak + 1 + |
[ |
( | k
1 | ) |
+ |
( | k
0 | ) |
] |
ak b + |
[ |
( | k
2 | ) |
+ |
( | k
1 | ) |
] |
ak − 1 b2 |
+ … + |
[ |
( | k
k | ) |
+ |
( | k
k − 1 | ) |
] |
a bk + |
( | k
k | ) | bk + 1 |
Pro sečtení čísel v hranatých závorkách využijeme vlastnost kombinačních čísel
| ( | n
k | ) |
+ | ( | n
k + 1 | ) |
= | ( | n + 1
k + 1 | ) |
| (a + b)k + 1 = |
( | k
0 | ) | ak + 1 + |
( | k + 1
1 | ) |
ak b + |
( | k + 1
2 | ) |
ak − 1 b2 |
+ … + |
( | k + 1
k | ) |
a bk + |
( | k
k | ) | bk + 1 |
| Protože platí |
|
( | k
0 | ) |
= 1 = |
( | k + 1
0 | ) |
|
a také |
|
( | k
k | ) |
= 1 = |
( | k + 1
k + 1 | ) |
, dostáváme binomickou větu pro n = k + 1: |
| (a + b)k + 1 = |
( | k + 1
0 | ) | ak + 1 + |
( | k + 1
1 | ) |
ak b + |
( | k + 1
2 | ) |
ak − 1 b2 |
+ … + |
( | k + 1
k | ) |
a bk + |
( | k + 1
k + 1 | ) | bk + 1 |
Tím je platnost binomické věty dokázána.
Vzorec si snadněji zapamatujeme, když si uvědomíme, podle jakých pravidel
se mění kombinační čísla a exponenty u jednotlivých členů binomického rozvoje.
Všimněte si, že
exponenty mocnin se základem
a klesají od
n k nule
a naopak exponenty mocnin se základem
b rostou od nuly k
n.
Součet exponentů je v každém členu stejný a roven
n.
Kombinační čísla, která jsou obsažena v každém sčítanci, začínají
a končí
.
Protože kombinační čísla v tomto vzorci vystupují v roli koeficientů
mnohočlenu, který vznikne umocněním binomu (dvojčlenu),
nazýváme je také binomické koeficienty.
Vyjádříme-li výraz (a + b)n pomocí
binomické věty, říkáme, že jsme jej rozvinuli podle
binomické věty, nebo že jsme utvořili binomický rozvoj
výrazu (a + b)n.
Příklad
Pomocí binomické věty vypočtěte
(x − 1)5.
Řešení
| (x − 1)5 = [x + (−1)]5 = |
( | 5
0 | ) | x5 + |
( | 5
1 | ) | x4 · (−1) + |
( | 5
2 | ) | x3 · (−1)2 + |
( | 5
3 | ) | x2 · (−1)3 + |
( | 5
4 | ) | x · (−1)4 + |
( | 5
5 | ) | (−1)5 = |
= x5 +
5 · x4 · (−1) +
10 · x3 · 1 +
10 · x2 · (−1) +
5 · x · 1 + (−1) =
= x5 − 5 x4 + 10 x3
− 10 x2 + 5 x − 1
Příklad
Užitím binomické věty vypočítejte 1,016.
Řešení
1,01
6 = (1 + 10
−2)
6 =
| | = |
( | 6
0 | ) | + |
( | 6
1 | ) | 10−2 + |
( | 6
2 | ) | (10−2)2 + |
( | 6
3 | ) | (10−2)3 + |
( | 6
4 | ) | (10−2)4 + |
( | 6
5 | ) | (10−2)5 + |
( | 6
6 | ) | (10−2)6 |
= |
| | = |
1 + |
6 · 10−2 + |
15 · 10−4 + |
20 · 10−6 + |
15 · 10−8 + |
6 · 10−10 + |
10−12 |
= |
Příklad
Určete součet
| ( | n
0 | ) | + |
( | n
1 | ) | + |
( | n
2 | ) |
+ … + |
( | n
n − 1 | ) | + |
( | n
n | ) |
, |
kde
n je nezáporné celé číslo.
Řešení
Jestliže rozvineme podle binomické věty výraz (1 + 1)
n,
dostaneme:
| (1 + 1)n = |
( | n
0 | ) | 1n + |
( | n
1 | ) | 1n − 1 · 1 + |
( | n
2 | ) | 1n − 2 · 12 |
+ … + |
( | n
k | ) |
1n − k · 1k |
+ … + |
( | n
n − 1 | ) | 1 · 1n − 1 + |
( | n
n | ) | 1n |
= |
| = |
( | n
0 | ) | + |
( | n
1 | ) | + |
( | n
2 | ) |
+ … + |
( | n
k | ) |
+ … + |
( | n
n − 1 | ) | + |
( | n
n | ) |
. |
Protože (1 + 1)
n = 2
n, máme výsledek:
| ( | n
0 | ) | + |
( | n
1 | ) | + |
( | n
2 | ) |
+ … + |
( | n
n − 1 | ) | + |
( | n
n | ) |
= 2n |
Příklad
Pomocí binomické věty dokažte, že pro libovolné přirozené číslo
n je číslo
8n − 1 dělitelné sedmi.
Řešení
8
n − 1 = (7 + 1)
n − 1 =
| | = |
[ |
( | n
0 | ) | · 7n + |
( | n
1 | ) | · 7n − 1 |
+ … + |
( | n
n − 2 | ) | · 72 + |
( | n
n − 1 | ) | · 7 + |
( | n
n | ) |
] |
− 1 = |
| | = |
[ |
( | n
0 | ) | · 7n + |
( | n
1 | ) | · 7n − 1 |
+ … + |
( | n
n − 2 | ) | · 72 + |
( | n
n − 1 | ) | · 7 + |
1 |
] |
− 1 = |
| | = |
( | n
0 | ) | · 7n + |
( | n
1 | ) | · 7n − 1 |
+ … + |
( | n
n − 2 | ) | · 72 + |
( | n
n − 1 | ) | · 7 |
= |
| | = 7 · |
[ |
( | n
0 | ) | · 7n − 1 + |
( | n
1 | ) | · 7n − 2 |
+ … + |
( | n
n − 2 | ) | · 7 + |
( | n
n − 1 | ) |
] |
| |
= 7k, kde k je přirozené číslo. |
Číslo 8
n − 1 je tedy pro každé přirozené číslo
n
dělitelné sedmi.
V některých případech nepotřebujeme znát celý binomický rozvoj, ale stačí nám
jen určitý člen. V binomickém rozvoji výrazu
(a + b)n
je koeficient u prvního členu
,
u druhého členu
,
u třetího členu
,
a tak dál,
u k-tého členu je tedy koeficient
.
Z koeficientu můžeme odvodit celý
k-tý člen binomického rozvoje:
Pro všechna reálná čísla
a,
b, každé přirozené číslo
n
a přirozené číslo
k,
k ≤ n + 1 platí, že
k-tý člen binomického rozvoje výrazu
(a + b)n má tvar
| ( | n
k − 1 | ) |
an − (k − 1) bk − 1 |
. |
Příklad
Určete desátý člen binomického rozvoje výrazu
Řešení
Do vzorce pro
k-tý člen dosadíme
a = 2
x3,
b = −√2/
x,
n = 12,
k = 10:
| ( | 12
10 − 1 | ) |
(2x3)12 − (10 − 1) · |
( |
− | √2 x |
)10 − 1 |
= |
( | 12
9 | ) |
(2x3)3 · |
( |
− | √2 x |
)9 |
= |
| = − |
12! 9! 3! |
23 x9 · |
√29 x9 |
= −220 · 23 · (24 √2) |
= −28 160 √2 |
Příklad
Určete, kolikátý člen binomického rozvoje výrazu
(2x3 + 3x2)10
obsahuje x23.
Řešení
k-tý člen binomického rozvoje výrazu
(2x3 + 3x2)10
má tvar
| ( | 10
k − 1 | ) |
(2x3)10 − (k − 1)
· (3x2)k − 1 |
. |
Číselné koeficienty hodnotu exponentu mocniny
x neovlivní, můžeme tedy
dále počítat bez nich:
x3 · [10 − (k − 1)]
·
x2 · (k − 1)
=
x33 − 3k ·
x2k − 2
=
x31 − k
Hledáme takový člen, který obsahuje
x23:
x31 − k =
x23
31 −
k = 23
k = 8.
V binomickém rozvoji daného výrazu je
x23
v osmém členu.
Vyjádření binomické věty pomocí sumy
Pro všechna čísla
a,
b a každé přirozené číslo
n platí
| (a + b)n = |
n
∑
k = 0 |
( | n
k | ) |
an − k
bk |