Kombinatorikos taisyklės

Skaičiavimo principai

Sudėties taisyklė

Jei veiksmą galima atlikti vienu iš kelių būdų, tai bendras būdų skaičius yra jų suma.

$|A \cup B| = |A| + |B| \quad \text{(kai A ir B nepersidengia)}$

Pavyzdys 1: Bibliotekoje yra 5 lietuviškos ir 3 angliškos knygos. Keliais būdais galima pasirinkti vieną knygą? Atsakymas: $5 + 3 = 8$ būdais.

Daugybos taisyklė

Jei veiksmas susideda iš kelių etapų, tai bendras būdų skaičius yra atskirų etapų būdų sandauga.

$|A \times B| = |A| \cdot |B|$

Pavyzdys 2: Moksleivis renka pietų komplektą: 4 sriubos rūšys ir 6 antrieji patiekalai. Keliais būdais galima sudaryti komplektą? Atsakymas: $4 \cdot 6 = 24$ būdais.

Pavyzdys 3: Automobilio numeris susideda iš 3 raidžių (iš 26) ir 3 skaitmenų (iš 10). Kiek skirtingų numerių galima sudaryti?

$26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 26^3 \cdot 10^3 = 17\,576\,000$

Faktorialas

Faktorialas $n!$ – tai visų natūraliųjų skaičių nuo 1 iki $n$ sandauga.

$n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$

Susitarimas: $0! = 1$ .

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
10	3 628 800

Savybė: $n! = n \cdot (n-1)!$

Pavyzdys 4: $\frac{8!}{6!} = \frac{8 \cdot 7 \cdot 6!}{6!} = 8 \cdot 7 = 56$

Perstatiniai (permutacijos)

Perstatiniai $P_n$ – tai būdų skaičius, kuriais galima surikiuoti visus n elementus tam tikra tvarka.

$P_n = n!$

Pavyzdys 5: Keliais būdais galima surikiuoti 5 mokinius į eilę?

$P_5 = 5! = 120$

Pavyzdys 6: Kiek skirtingų „žodžių" galima sudaryti iš raidžių A, B, C, D (kiekvieną naudojant tik kartą)?

$P_4 = 4! = 24$

Gretiniai (tvarkos, išdėstymai)

Gretiniai $A_n^k$ – tai būdų skaičius, kuriais galima iš $n$ elementų pasirinkti $k$ elementų, kai tvarka svarbi.

$A_n^k = \frac{n!}{(n-k)!}$

Pavyzdys 7: Kiek skirtingų triženklio kodo variantų galima sudaryti iš skaitmenų 1–9, jei skaitmenys nesikartoja?

$A_9^3 = \frac{9!}{6!} = 9 \cdot 8 \cdot 7 = 504$

Pavyzdys 8: Varžybose dalyvauja 10 bėgikų. Keliais būdais galima išdalinti aukso, sidabro ir bronzos medalius?

$A_{10}^3 = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720$

Pastaba: Kai $k = n$ , tai $A_n^n = n! = P_n$ (perstatiniai).

Deriniai (kombinacijos)

Deriniai $C_n^k$ – tai būdų skaičius, kuriais galima iš $n$ elementų pasirinkti $k$ elementų, kai tvarka nesvarbi.

$C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}$

Ryšys su gretiniais: $C_n^k = \frac{A_n^k}{k!}$ (pašaliname k elementų perstatinių pasikartojimą).

Pavyzdys 9: Klasėje 25 mokiniai. Keliais būdais galima išrinkti 3 mokinių delegaciją?

$C_{25}^3 = \frac{25!}{3! \cdot 22!} = \frac{25 \cdot 24 \cdot 23}{3 \cdot 2 \cdot 1} = \frac{13\,800}{6} = 2300$

Pavyzdys 10: Kortelių kaladėje 52 kortos. Keliais būdais galima ištraukti 5 kortas?

$C_{52}^5 = \frac{52!}{5! \cdot 47!} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48}{120} = 2\,598\,960$

Derinių savybės

$C_n^0 = 1, \quad C_n^n = 1, \quad C_n^1 = n$

$C_n^k = C_n^{n-k} \quad \text{(simetrija)}$

Pavyzdys: $C_{10}^3 = C_{10}^7 = 120$

Kaip atskirti: tvarka svarbi ar ne?

Klausimas	Tvarka svarbi?	Formulė
Surikiuoti visus elementus	Taip	$P_n = n!$
Pasirinkti k iš n, tvarka svarbi	Taip	$A_n^k$
Pasirinkti k iš n, tvarka nesvarbi	Ne	$C_n^k$

Patarimas: Jei keičiant pasirinktų elementų tvarką gaunamas kitas rezultatas (pvz., kodas, eilė, vietos) – tvarka svarbi (gretiniai). Jei rezultatas tas pats (pvz., komanda, grupė) – tvarka nesvarbi (deriniai).

Paskalio trikampis

Paskalio trikampis – tai lentelė, kurioje kiekvienas skaičius yra virš jo esančių dviejų skaičių suma.

$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$

n=0:                1
n=1:              1   1
n=2:            1   2   1
n=3:          1   3   3   1
n=4:        1   4   6   4   1
n=5:      1   5  10  10   5   1
n=6:    1   6  15  20  15   6   1

Pavyzdys: $C_6^2 = 15$ (antras skaičius nuo krašto šeštoje eilutėje).

Binomo formulė (Niutono binomas)

$(a + b)^n = \sum_{k=0}^{n} C_n^k \cdot a^{n-k} \cdot b^k$

Išskleidimas:

$(a+b)^n = C_n^0 a^n + C_n^1 a^{n-1}b + C_n^2 a^{n-2}b^2 + \ldots + C_n^n b^n$

Pavyzdys 11: Išskleiskite $(x + 2)^4$ .

$C_4^0 x^4 + C_4^1 x^3 \cdot 2 + C_4^2 x^2 \cdot 4 + C_4^3 x \cdot 8 + C_4^4 \cdot 16$

$= x^4 + 8x^3 + 24x^2 + 32x + 16$

Pavyzdys 12: Raskite $(2x - 1)^5$ išskleidimo narį, kuriame $x^3$ .

Bendras narys: $C_5^k (2x)^{5-k}(-1)^k$ . Reikia $5 - k = 3$ , taigi $k = 2$ .

$C_5^2 \cdot (2x)^3 \cdot (-1)^2 = 10 \cdot 8x^3 \cdot 1 = 80x^3$

Savarankiško darbo užduotys

Apskaičiuokite: $6!$ , $\frac{10!}{8!}$ , $\frac{7!}{3! \cdot 4!}$ .
Restorane galima rinktis iš 3 užkandžių, 5 pagrindinių patiekalų ir 4 desertų. Keliais būdais galima sudaryti pietų komplektą (po vieną kiekvienos rūšies)?
Keliais būdais galima surikiuoti 7 knygas lentynoje?
Iš 8 spalvų reikia pasirinkti 3 spalvas vėliavai (svarbi spalvų tvarka juostose). Keliais būdais tai galima padaryti?
Komandai reikia išrinkti 4 žmones iš 12 kandidatų. Keliais būdais galima tai padaryti?
Apskaičiuokite: $C_{10}^4$ ir patikrinkite, kad $C_{10}^4 = C_{10}^6$ .
Keliais būdais galima sudaryti 5 raidžių kodą iš raidžių A, B, C, D, E, F, G, jei raidės nesikartoja?
Išskleiskite $(a + b)^5$ naudodami binomo formulę.
Raskite $(x - 3)^6$ išskleidimo laisvąjį narį (narį be $x$ ).
Klasėje 30 mokinių. Keliais būdais galima išrinkti seniūną ir jo pavaduotoją? O keliais būdais – dviejų mokinių komitetą?