kombinatorika

$ 1. gadanacvleba da misi raodenobis gamosaTvleli

formula

vTqvaT, n raime naturaluri ricxvia. n _elementiani gadanacvlebebi

(anu n _gadanacvlebebi) ewodeba n gansxvavebuli elementisagan
Sedgenil kombinaciebs, romlebic mxolod elementebis dalagebiT
gansxvavdeba.

gansxvavebul n _gadanacvlebaTa Pn raodenoba tolia 1 -dan n -is

CaTvliT TanmimdevrobiT aRebuli yvela naturaluri ricxvis namravlis

Pn  1  2  3  n

am namravls ewodeba n ricxvis faqtoriali da igi n ! simboloTi

aRiniSneba. MmaSasadame

Pn  n !

SeTanxmebiT, carieli simravlis dalageba SesaZlebelia erTaderTi

gziT. amitom iTvleba, rom 0 !  1 .
adgili aqvs tolobas

Pn  n  Pn 1 .

magaliTi. davadginoT, ramden elements unda Seicavdes simravle,

rom am simravlis elementebisagan Sedgenili yvela gadanacvlebaTa
ricxvi iyos:
a) ara umetes 1000 -isa;
b) ara nakleb 500 -isa.
amoxsna.
a) amocanis pirobiT Pn  1000 anu n ! 1000 saidanac n  6 . marTlac,
6 !  720  1000 da 7 !  5040  1000 .
b) amocanis pirobiT, Pn  500 anu n ! 500 saidanac n  6 . marTlac,
5 !  120  500 da 6 !  720  500 .

1
 $ 2. wyoba da misi raodenobis gamosaTvleli formula

vTqvaT, mocemulia n -elementiani sasruli A simravle:

A  {a1 , a 2 , a3 , , a n } .
am simravlis elementebidan nebismierad amovarCioT erTmaneTisagan
gansxvavebuli m elementi (cxadia m  n ) da am elementebisagan
SevadginoT yvela SesaZlo dalagebuli m elementiani simravle.

n -elementiani A simravlis elementebisagan Sedgenil yovel m

gansxvavebul elementian dalagebul qvesimravles ewodeba wyoba n -
elementisa m elementad. n -elementis m elementad yvela wyobaTa
ricxvi aRiniSneba simboloTi. adgili aqvs Semdeg tolobas:
.

wyobaTa Tvisebebi.

Tviseba. .
Tviseba. .
Tviseba.

magaliTi. davadginoT, ramdeni sxvadasxva xerxiT SeiZleba 5 kacis

arCeva xuT sxvadasxva Tanamdebobaze, Tu am Tanamdebobaze kandidatTa
ricxvia 11 .
amoxsna. amorCevaTa yvela SesaZlo raodenoba toli iqneba
11 ! 11 !
ricxvis. amitom,    7  8  9  10  11  55 440 .
(11  5) ! 6 !

$ 3. jufTeba da misi raodenobis gamosaTvleli formula

vTqvaT, mocemulia n -elementiani raime A simravle. ganvixiloT misi

nebismierad Sedgenili m gansxvavebul elementian qvesimravle
(dalagebis gareSe). n -elementiani A simravlis elementebisagan Sedgenil
yovel aseT m gansxvavebul elementian qvesimravles ewodeba jufTeba n -
elementisa m elementad. n -elementis m elementad yvela jufTebaTa
n 
ricxvi aRiniSneba simboloTi: C nm (zogjer gamoiyeneba   saxis
 m
Canaweri). adgili aqvs tolobas:

2
 n!
C nm  .
m! (n  m)!

jufTebaTa Tvisebebi:

Tviseba. C n0  1 .
Tviseba. C n1  n .
Tviseba. C nm  C nn  m .

magaliTi. davadginoT, saWadrako turnirSi monawileTa raodenoba,

Tu TiToeulma monawilem TiToeul danarCenTan TiTo partia iTamaSa da
sul 55 partia Sedga?

amoxsna. Tu turnirSi monawileTa raodenobas n -iT avRniSnavT, maSin

turnirSi sul gaTamaSebul partiaTa raodenoba toli iqneba C n2 .
amocanis pirobiT
C n2  55 .
gveqneba
n! n  (n  1)
  55 anu n  ( n  1)  110 , saidanac n  11 .
2 ! (n  2)! 2

$ 4. niutonis binomi. binomialuri koeficientebis

gamosaTvleli formula da maTi Tvisebebi

ganvixiloT ori ricxvis jamis naturaluri xarisxi (a  b) n . რicxvis

naturaluri xarisxis ganmartebis gamoyenebiT, Zneli ara ris imis
gamoTvla, rom
(a  b)1  a  b
(a  b) 2  a 2  2ab  b 2
(a  b)3  a 3  3a 2b  3ab 2  b3
(a  b) 4  a 4  4a 3 b  6a 2 b 2  4ab 3  b 4 .
(a  b) 5  a 5  5a 4 b  10a 3b 2  10a 2 b 3  5ab 4  b 5 .
aRmoCnda, rom nebismieri naturaluri n ricxvisaTvis marTebulia
formula:

3
 ( a  b) n  C n0  a 5  C n1  a n 1b  C n2  a n  2 b 2    C nm  a n  m b m    C nn  b n .
miRebul formulas niutonis formula (anu binomi) ewodeba.
niutonis binomis C nm koeficientebs binomuri koeficientebi ewodebaT.

niutonis binomis Tvisebebi.

Tviseba. binomuri koeficientebis raodenoba (Sesabamisad, niutonis

binomis formulaSi SesakrebTa ricxvi) tolia (n  1)  is;

Tviseba. niutonis binomis formulaSi pirveli Sesakrebis xarisxi

klebulobs n -dan 0 -mde, xolo meore Sesakrebis xarisxi izrdeba 0 -dan
n -mde;

Tviseba. niutonis binomis formulaSi boloebidan Tanabrad

daSorebuli wevrebis koeficientebi tolia C nm  C nn  m ;

Tviseba. binomuri koeficientebi jer izrdeba, Semdeg ki klebulobs.

Tu binomis xarisxis maCvenebeli luwia, maSin daSlis Sua wevris
binomuri koeficienti udidesia, xolo Tu binomuri xarisxis maCvenebeli
kentia, maSin ori Sua binomuri koeficienti erTmaneTis tolia da,
amasTan, udidesia;

Tviseba. binomuri xarisxis daSlis k  1 -e Sesakrebi Tk tolia

Tk  C nk  a n  k b k .

SeniSvna. ori sididis sxvaobis naturaluri xarisxisaTvis

marTebulia formula:
(a  b) n  C n0  a 5  C n1  a n 1b  C n2  a n  2 b 2    ( 1) m  C nm  a n  m b m    ( 1) n  C nn  b n .

12
 12 2

magaliTi. vipovoT  x  x 3  daSlis mexuTe wevri.

 
amoxsna. visargebloT zemoT ganxiluli formuliT, gveqneba:
8 4
 12   23  20

T4  C   x 
4
12
 
  x   495  x 3 .
   

$ 5. paskalis samkuTxedi

ganvalagoT binomialuri koeficientebi aseTi samkuTxedis saxiT

C 00  1
4
 C10  1 C11  1
C 20  1 C 21  2 C 22  1
C 30  1 C 31  3 C 32  3 C 33  1
C 40  1 C 41  4 C 42  6 C 43  4 C 44  1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
mas paskalis samkuTxedi qvia. albaT SeamCnevdiT, rom aq yoveli
ricxvi misi ori zeda mezoblis jamia. sazogadod

Cnk  Cnk11  Cnk1 .

paskalis samkuTxedis Tvisebebi

n -ur striqonis wevrTa jami 2 n -is tolia (ratom ? gaSale niutonis

formuliT (1 + 1)n ).

paskalis yoveli striqoni simetriulia (ratom ? Seadare erTmaneTs

Cnk da Cnn  k ).

magaliTi. paskalis samkuTxedis gamoyenebiT, vipivoT (1  x) 5

gamosaxulebis mniSvneloba.

amoxsna. (1  x) 5 gamosaxulebis koeficientebi paskalis samkuTxedis

5 -e striqonis elementebia: 1, 5, 10, 10, 5, 1 , amitom
(1  x) 5  1  5 x  10 x 2  10 x 3  5 x 4  x 5 .

damatebiTi amocanebi.

1. SeadgineT A simravlisagan yvela SesaZlo gadanacvleba, Tu:

a) A  {m, n, p, q} ;
b) A  {1, 2, p, q, a} .

2. SeasruleT moqmedebebi da gamoTvaleT:

6 !5 ! (n  1)! 1 1 1 1
a) ; b) ; g)  ; d)  .
12 (n  3)! n! ( n  1)! (k  1)! k!

3. klasSi 32 moswavlea. gamosaSveb saRamoze maT erTmaneTs

samaxsovro fotosuraTebi gaucvales. ramdeni fotosuraTi gaicvala
sul?

4. ramdeni gansxvavebuli sagnisagan SeiZleba 2 -elementiani 210

wyobis Sedgena?

5
 5. klasis 27 moswavlidan konferenciisaTvis unda airCion 3
delegati. ramdeni xerxiT SeiZleba amis gakeTeba?

6. klasSi 28 moswavlea. gamosaSveb saRamoze maT erTmaneTs

samaxsovro fotosuraTebi gaucvales. ramdeni fotosuraTi gaicvala
sul?

7. aCveneT Semdegi tolobis samarTlianoba:

a) C 74  C 73  C 84 ; b) C105  C106  C116 .

8. amoxseniT gantoleba:
15 An2
a) Ax  6C x  x  x ; b)
3 2 2
Cn4  ;
4
4
g) An  2  224 n( n  2) ; d) Cn3  Cn2  15(n 2 -1)

9. amoxseniT utoloba An21  72

10. niutonis binomis gamoyenebiT, gamoTvaleT:

4 3 5 4
1. 99 ; 2. 999 ; 3. 98 ; 4. 998

11. gamoTvaleT:

1. ( x  1) 4 ; 2. (2 x 2  y ) 5 ; 3. ( a  b ) 4 ;
4. ( x  y ) ; 5. ( 2a  b / 3) ; 6. ( x / 2  1 / x ) .
6 2 7 7

12. ipoveT binomialuri gaSlis m -uri wevri (Sua wevri):

1. (a 3  2b 2 )12 , m  7 ; 2. (2 x  1 / 2 y )19 , m  8 ;
3. (a
1/ 2
 1 / 2b 1 / 3 )18 , m  4 ; 4. ( x  y ) 25 , m  20 ;
5. (3 x  y / 3) , m  11
15

13. 
ipoveT x  x  2 
12
daSlis im wevris nomeri, romelic ar Seicavs x -
s.

14. ipoveT 1  0,011000 daSlis udidesi wevris nomeri.

15. paskalis samkuTxedis gamoyenebiT, warmoadgineT mravalwevris

saxiT Semdegi gamosaxuleba:
a) (a  b) 7 ;
b) (1  x)10 .
16. SeadgineT 12 striqoniani paskalis samkuTxedi.
6
 Combinatorics

Factorial

The product of a given integer and all smaller positive integers. The factorial of n is written n!
and is read aloud "n factorial".

Note: By definition, 0! = 1.

Formula: n! = n·(n – 1)·(n – 2) · · · 3·2·1

Example: 6! = 6·5·4·3·2·1 = 720

Permutation Formula

A formula for the number of possible permutations of k objects from a set of n. This is usually
written nPk .

Formula:

Example: How many ways can 4 students from a group of 15 be

lined up for a photograph?

Answer: There are 15P4 possible permutations of 4 students from a

group of 15.

different lineups

Binomial Coefficients

Numbers written in any of the ways shown below. Each notation is read aloud "n choose r."

7
A binomial coefficient equals the number of combinations of r items that can be selected from a
set of n items. It also represents an entry in Pascal's triangle. These numbers are called binomial
coefficients because they are coefficients in the binomial theorem.

Formula:

Note: , where nPr is the formula for permutations of n

objects taken r at a time.

Examples:

Pascal's Triangle

The figure below, extended infinitely. A particular entry is found by adding the two numbers that
are above and on either side of the element. Note: The numbers which make up Pascal's triangle
are called binomial coefficients.

Pascal's Triangle

Note that the sum of any two

adjacent elements in a row
can be found between them
on the next row. Each row
begins and ends with 1.
etc.