DiM 2203 дискретті математика

 
Бұл кластар жүйесінің мынадай қасиеттері бар:Олар бөлімдер құрайды, 
яғни  кластар  өзара  қиылыспайды;  Бір  кластағы  кез-келген  2  элемент 
эквивалентті;Әр кластан алынған кез-келген 2 элемент эквивалентті емес.Бұл 
қасиеттер R қатынасының рефлексивтілік, симметриялық және транзитивтік 
қасиеттерінен шығады.М жиынынан осылай бөлшектеу, яғни кластар жүйесі 
R қатысты эквивалентті кластар жүйесі деп аталады. Бұл жүйенің қуаты бөлу 
индексі деп аталады.  
Реттің қатынасы 
Егер  қатынас  рефлексивті  ,антисимметриялы  және  транзитивті  болса, 
қатаң  емес  ретті  қатынас  деп  аталады.Егер  қатынас  антирефлексивті, 
антисимметриялы  және  транзитивті,  қатаң  ретті  қатынас  деп  аталады. 
Қатынастардың  бұл  екі  түрі  реттің  қатынастары    деп  аталады.Мысал      ,     
қатынастары қатаң емес,    ,   қатынастары қатаң. Бұл екі қатынастар N, R 
жиындарын реттейді. 
Негізгі әдебиет: 1[15-18];  2[31-37]  
Қосымша әдебиет: 7[9-34]  
Бақылау сұрақтары: 
1. Жиындағы қатынас дегеніміз не? 
2. Бинарлы қатынасқа мысал келтіріп оның матрицасын құрыңыз. 
3. Қандай бинарлы қатынас рефлексивті,симметриялы,транзитивті? 
4. Қандай қатынастар эквиваленттілік,реттік деп аталады? 
5.  Бинарлы  қатынасқа  қолданылатын  амалдар  қандай?  Рефлексивті, 
транзитивті тұйықтық дегендер не? 
 
3-дәріс. Комбинаторика элементтері. Орналастыру және теру. 
 
Комбинаториканың  негізгі  есебі–қайта  санау  және  ақырлы  жиын 
элементтерін тізбектеу. 
Егер  берілген  ақырлы  жиын  элементтерінің  қаншасының  берілген  бір 
қасиетке ие екендігін анықтау қажет болса бұл қайта санау есебі, ал берілген 
қасиетке  ие  барлық  элементтерді  анықтау  керек  болса,  бұл  тізімдеу  есебі 
Комбиторика есебін дәлелдеуде екі ереже жиі қолданылады. Олар: қосу және 
көбейту ережелері. 
Егер Х  n элементтерден тұратын ақырлы жиын болса,  Х объектісін Х 
тен n тәсілмен алуға болады дейді және  Х =n болып белгіленеді. 
Егер  Х
1
,…,Х
n
–қос  қостан  қиылыспайтын  жиындар  болса,  яғни 
Х
i

Х
j
=  (i j), онда 
k
1
i
i
k
1
i
i
Х
Х

-қосу ережесі. (1) 
Бұл  ережені  k=2  үшін  былай  жазуға  болады:  Егер  х  объектісі  m 
тәсілмен  таңдалса, ал  у  басқа  n  тәсілмен  таңдалса, онда  "не  х,  не  у"  таңдау 
m+n  тәсілмен  іске  асырылады  (х  және  у  элементтерін  бір  уақытта  таңдау 
болмайды).  

Көбейту  ережесі.  Егер  х  объектісін  m  тәсілмен  таңдауға  болса,  және 
осындай таңдаудан кейін у объектісін өз кезегінде n тәсілмен таңдауға болса, 
онда  реттелген  (х,  у)  жұбын  m n  тәсілмен  таңдауға  болады.(х,  у  – 
таңдаулары тәуелсіз). 
Жалпы жағдайда, егер х
1
  объектілері  n
1
  тәсілмен  таңдалса,  одан  кейін 
х
2
 n
2
 тәсілмен таңдалса және кез келген 2 i m-1 үшін х
1
, х
2
,…,х
i
 объектілерін 
таңдағаннан кейін х
i+1
 объектісін n
i+1
 тәсілмен таңдауға боллатын болса, онда 
m  объектіден  құралған  (х
1
,  х
2
,  …,  х
m
)  реттелген  тізбегі  n
1
    n
2
  …   n
m
 
тәсілмен таңдалады. 
Х={х
1
, …, х
n
} жиынынан алынған х
i1
, …, х
ir
 элементтерінің жиынтығы 
n элементтен алынған r көлемді таңдама деп аталады. 
Егер  элементтердің  орналасу  тәртібі  берілген  болса,  таңдама  реттеген 
деп, ал орналасу тәртібіне белгілі бір шарт қойылмаса, таңдама реттелмеген 
деп аталады. 
Таңдамаларда элементтердің қайталануы да, қайталанбауы да мүмкін. 
Элементтері  қайталануы  мүмкін  (n,  r)  -  таңдамасы  (n,  r)-қайталама 
таңдамасы деп аталады. Ал егер реттелген (n, r) таңдаманың элементтері қос 
қостап әр түрлі болса, (n, r) қайталанбайтын таңдама немесе жай ғана (n, r)-
орналасу деп аталады. 
(n, n)-қайталанбайтын орналасу Х жиынын алмастыру деп аталады. 
Элементтері қайталануы мүмкін реттелмеген (n, r)-таңдама, қайталанба 
(n,  r)-теру  деп  аталады.  Егер  реттелмеген  (n,  r)  таңдаманың  элементтері  қос 
қостан әр түрлі болса, онда ол қайталанбайтын (n, r)-теруі немесе жай ғана (n, 
r)  теруі  деп  аталады.  Кез  келген  (n,  r)-теруін  n-элементті  жиынның  r-
элементті ішкі жиыны деп қарауға болады. 
Мысал, айталық Х={1, 2, 3} болсын. 
1)  (1,  1),  (1,  2),  (1,  3),  (2,  1),  (2,  2),  (2,  3),  (3,  1),  (3,  2),  (3,  3)  -  (3,  2)-
қайталама орналастырулар. 
2) (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2) - (3, 2)-қайталама орналасу; 
3)  (1,  2,  3),  (1,  3,  2),  (3,  2,  1),  (2,  1,  3),  (3,  1,  2),  (2,  3,  1)  –  Х  жиынын 
алмастыру; 
4) {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} - (3, 2)-қайталама теру; 
5)  {1,  2},  {1,  3},  {2,  3}  -  (3,  2)-қайталанбайтын  теру.  Қайталама  теру 
саны  (n,  r)-ді 
r
n
A
,  қайталанбайтын  теру-
r
n
A
.  n-элементті  теру  саны  P
n
  (яғни 
P
n
=
n
n
А
) болып белгіленеді. Қайталама теру (n, r)-саны 
r
n
C ,ал қайталанбайтын 
теру-
r
n
C . 
1-тұжырым. 
r
n
A
=nr. 
Шынында  әрбір  (n,  r)-қайталама  теру  ұзхындығы  r-ға  тең  реттелген 
тізбек,  ал  оның  әр  мүшесі  n  тәсілдің  бірімен  таңдалады,  бұдан  көбейту 
ережесінен 
r
n
A =n n … n=nr. 
(Дербес  жағдайда  бұл  өрнек  негізі  n  санау  жүйесінде  r  позицияда 
жазылған әр түрлі сандардың нешеу екендігін анықтайды.). 

2-тұжырым. 
r
n
A
=n(n-1)(n-2)…(n-r+1)=
!
)
r
n
(
!
n
,  r n  және 
r
n
A
=0,  r>n 
болғанда. 
Шынында, r элементтен тұратын реттелген тізбектің бірінші мүшесі n 
тәсілмен  таңдалады,  екіншісі-(n-1)  тәсілмен,  соңғысы-  (n–r+1)  тәсілмен. 
Жалпыланған көбейту ережесінен ізделінді формуланы аламыз. 
Салдар 
n
n
А =Pn=n(n-1) … (n–n+1)=n! 
!
r
)!
r
n
(
!
n
!
r
A
С
r
n
r
n
 
3-тұжырым., егер r n, 
r
n
C
=0 егер r>n. 
Шышында да, әр (n, r)-теруін r! әдіспен реттеуге болады, яғни 
r
n
C
-ді r! 
рет 
r
n
А
-ге қарағанда r! рет аз. Бұл формуладан 
r
n
C
=
r
n
n
C
. 
4-тұжырым. 
r
r
n
r
n
C
С
1
. 
Шынында  да  Х={x
1
,…,x
n
}  жиынының  элементтерінен  құрылған  әрбір 
қайталанба (n, r)- В теруі үшін, r нөл мен n-1 1-ден тұратын  (i-1)-ші және i 
бірлердің  (мұндағы  2   i    n-1)  арасындағы  нөлдердің  саны  В  теруіндегі  x
i
 
элементтерінің санына тең, ал бірінші бірдің алдындағы нөлдердің саны В-ға 
енетін  x
i
  элементтерінің  санына  тең  болатын  ұзындығы 
(В)    болатын 
векторды сәйкестендіруге болады. 
Мысалы Х={1, 2, 3, 4}, n=4, r=6 болса, Егер В={2, 2, 3, 3, 3, 4} - (4, 6)-
қайталанба теру болса онда  (В) = 100100010 болады. Екінші жағынан егер 
(В
1
)=110010000, онда В
1
 = {3, 3, 4, 4, 4, 4}. 
Бұл  қайталанба  (n,  r)-теруімен  n-1  бір  және  r  нөлден  тұратын  вектор 
арасындағы  сәйкестік.  n-1  бірден  және  r  нөлден  құралған  n+r-1  мөлшерлі 
векторлар саны
r
r
n
C
1
 тең. 
0
n
А
= 
0
n
0
n
C
A
= 
1
0
n
C
. 
Орналастыру және функционал бейнелеу. 
Комбинаторикалық  классикалық  есептерінің  бірі,  қандай  да  бір 
объектілердің  «жәшіктерде»  белгілі  бір  шектеулер  орындалатындай 
орналастыру  санын  анықтау  болып  табылады.  Бұл  есепті  төмендегідей 
тұжырымдауға болады: 
Айталық  Х   =  r,  Y   =  n.  Барлық  бейнелеулер  f  :  X 
  Y  санын  Y
Х
 
белгілейік.  Берілген  шектеулерді  қанағаттандыратын  қанша  f  :  X 
  Y 
функционал бейнелеулер бар? Егер бұл бейнелеулерге шектеулер жоқ болса 
төмендегідей тұжырым келтіруге болады. 
5-тұжырым.  YХ   = 
r
n
А
= nr =  Y X . 
Шынында,  Х={x
1
,…,x
r
}  болсын.  Олай  болса  кез  келген  бейнелеуді 
f:Х Y  реттелген  (f(x
1
),  f(x
2
),…,f(x
r
)),  мұндағы  f(x
i
) Y,  тізбегі  түрінде 
кескіндеуге  болады,  яғни  біз  функционал  бейнелеулер  мен  саны  n
r
-ге  тең, 
көлемі  n  болатын  Y  жиынынан  алынған  қайталанба  реттелген  таңдамалар 
жиынының арасында өзара бір мәнді сәйкестік орнаттық. 

(Егер Х - объектілер, Y- "жәшіктер" болса, онда f функция әрбір х Х 
объектісі үшін объект орналасқан f(x) Y жәшігін көрсетеді). 
Бірден  артық  емес  объект  орналасқан  жәшігі  бар  орналасудың  санын 
табу  қиын  емес,  ондай  теру  бір  мәнді  функцияларға  сәйкес  (инъективті 
бейнелеу). 
6-тұжырым. Иньективті бейнелеулердің f:X
Y(яғни f(x
1
)=f(x
2
)
х
1
=х
2
) 
саны 
r
n
А
. 
Шынында  да,  бұл  жағдайда  реттелген  тізбек  (f(x
1
),  f(x
2
),  …,  f(x
r
))  әр 
түрлі болуы керек, яғни бұл тізбек қайталанбайтын теру болып табылады. 
Салдар. Егер Sn - өзіне өзін бейнелейтін n-элементті барлық биективті 
бейнелеулердің жиыны болса олардың саны |Sn| 
!
n
P
А
n
n
n
 
Таңдамалар. 
    
 n-элементті  жиынның  k  -таңдамасы  деп           
X
X
k
i
i

1
,   
j
i
X
X 
,  i j  
Хi
,      i=
k
,
1
  орындалатын  {  X1,  X2,  …,  Xk  }  кез  келген  жиындар  үйірін 
түсінеміз.  Х-ті  к  блокқа  бөлетін  бөліктеулер  жиынын  Пк(х)  деп  белгілейік. 
|Пк(х)|. Бұдан әрине, S(n, k)=0 үшін k n; S(0, 0)=1 деп алынады. n-элементті 
жиынды К блокқа бөлетін бөліктеулер санын S(n, k) = |Пк(х)| белгілейміз. 
1-тұжырым.  S(n, k)= S(n-1, k-1)+k S(n-1, k)  егер 0 k n;   S(n, n)=1 егер 
n 0 ;    S(n, 0)=0 егер  n 0. S(n, k) саны II ретті Стирлинг саны деп аталады.   
Шынында  да  бірінші  және  үшінші  формулалар  түсінікті:  1  формуланы 
дәлелдеу үшін {1, 2, …, n} жиынын к блокқа бөлетін барлық бөліктеулердің 
жиынын қарастырамыз. Бұл жиын үлкен 2 класқа бөлінеді: бір элементті {n} 
блогы  бар  бөліктеулер  және  n-қуаты  1  деп  үлкен  блоктың  элементі  болып 
саналатын  бөліктеулер.  Бірінші  класта    S(n-1,  k-1)  блок  бар,  ал  екіншісінде 
S(n-1,  k).  Себебі  бұл  кластың  {1,  2,…,n-1}  жиынын  к  блокқа  бөлетін  әр 
бөліктеуінде  бұл  класта  әр  блокқа  кезекпен  n  элементін  қосудан  алынған  к 
бөліктеуі  сәйкес  келеді.  Мысалы,  S(4,  2)=S(3,  1)+2S(3,  2)=1+2(S(2,  1)+2S(2, 
2)) =1+2(1+2)=7. 
Егер  Х={1,  2,  3,  4}  онда  бұл  жиынды  2  блокқа  бөлетін  7  бөліктеу 
төменгідей:  
{{1, 2, 3}, {4}}; {{2, 3, 4}, {1}}; {{1, 2, 4}, {3}};{{1, 2}, {3, 4}}; 
{{1,  3,  4},  {2}};{{1,  4},  {2,  3}};  {{1,  3},  {2,  4}};  II  ретті  Стирлинг 
сандарын үшбұрышты кесте түрінде орналастыруға болады: 
k 
n 
1 
2 
3 
4 
5 
6 
7 
… 
1 
1 
 
 
 
 
 
  … 
2 
1 
1 
 
 
 
 
  … 
3 
1 
3 
1 
 
 
 
  … 
4 
1 
7 
6 
1 
 
 
  … 
5 
1 
15 
25 
10 
1 
 
  … 
6 
1 
31 
90 
65 
15 
1 
  … 

7 
1 
63  301  350  140  21 
1 
… 
…  …  …  …  …  …  …  …  … 
Кестенің  шеткі  бірлерден  басқа  әр  элементі  есептелетін  элементтен 
жоғарғы  жолда  орналасқан  санды  к-ға  көбейтіп,  оның  сол  жағындағы 
элементпен қосқаннан алынады. 
 Енді  ақырлы  Х  жиынын  Х
1
,  Х
2
,  …,  Х
k
  (k 1)  (мұндағы  әр  X
i
  n
i 
элементтен  тұрады)  ішкі  жиындарына  бөлетін  бөліктеулердің  санын 
анықтайық: 
X
X
i
k
i 1

,
j
i
X
X
  , i j   Х
i
=n
i
, 
k
i
,
1
 ; 
k
i
i
n
n
1
   екені белгілі. Кейбір 
i  нөмірі  үшін  Х
i
  =   болуы  мүмкін.  Тұрақатн  n
i
  үшін  бөліктеулер  санын 
k
n
n
n
n
C
...,
,
,
2
1
  деп  белгілейік  (Мұндағы  бөліктеулердегі  ішкі  жиындар  жиынтығы 
реттелген жиындар тізбегі болып табылады.  
2 - тұжырым.  
!
 
...
 !
!
1
...,
,
,
2
1
k
n
n
n
n
n
n
n
C
k
. 
Шынында да, әрбір Х
i
  ішкі  жиынын  қайталанбайтын  теру  деп  қарауға 
болады, олай болса, 
!
 
...
 !
!
 
...
 
1
 
...
 
...,
,
,
1
1
3
2
1
2
1
1
2
1
k
k
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
C
C
C
C
C
k
k
  
Мысал. 25 адамнан тұратын топқа староста сайланды. 12 адам келісті, 
10 қарсы болды, 3-і қалыс қалды. Мұндай сайлау қанша әдіспен жүргізіледі? 
1487285800
!
3
!
10
!
12
!
25
3
,
10
,
12
25
C
         
Енді i=1, 2, …, n үшін әрқайсысында i элементі бар mi ішкі жиыны бар 
болатын
n
i
i
n
i
m
1
)
(
 |X|=n, Х жиынын қанша ішкі жиынға бөлуге болатынын 
есептейік:  Мұнда  алдыңғы  жағдайға  қарағанда  ішкі  жиындарды  таңдау 
реттелмеген.  Мысалы,  Х  =  {1,  2,  3,  4,  5}жиыны  үшін  келесі  үш  бөліктеу 
бірдей.  
{1, 3}, {4}, {2, 5};  {4}, {2, 5}, {1, 3};  {2, 5}, {4}, {1, 3} 
Бұл бөліктеуде m
1
=1, m
2
=2, m
3
=m
4
=m
5
=0.Аталған бөліктеулердің санын 
N(m
1
, m
2
, …, m
n
) арқылы белгілейміз. 3 - тұжырым.  
n
m
m
m
n
n
n
m
m
n
m
m
m
N
)
!
(
...
 
)
!
2
(
)
!
1
(
!
...
 
!
!
)
,...,
,
(
2
1
1
2
1
 
Қарастырылып 
отырған 
реттелмеген 
бөліктеудің 
әрқайсысын 
m
1
! m
2
! … m
n
! тәсілмен төмендегі реттелген бөліктеуге түрлендіруге болады: 
n
1
1
n
1
2
1
1
1
m
...
m
1
m
...
m
m
m
1
m
m
1
X
,...,
X
,...,
X
,...,
X
,
X
,...,
X
 мұндағы, 
...
X
,...,
2
X
...
X
,
1
X
...
X
1
m
...
m
m
m
1
m
m
1
1
n
1
2
1
1
1
n
X
n
1
m
...
m
. 
Мұндай реттелген бөліктеудің саны: 
n
m
m
m
n
n
n
n
n
C
)
!
...(
)
!
2
(
)
!
1
(
!
2
1
,...,
,...,
2
,...,
2
,
1
,...,
1
 
Ал реттелмеген бөліктеудің саны бұдан m
1
! … m
n
!  есе аз. 

Мысал. 25 адамнан тұратын топты әрқайсысы 5 адамнан 5 коалацияға 
қанша  әдіспен  топтастыруға  болады?    |X|  =  25,  m
1
=…=m
4
=0,  m
5
=5, 
m
6
=…=m
25
=0; 
N(0, 0, 0, 0, 5, 0, …, 0) = 
6
5
)
!
5
(
!
25
)
!
5
(
!
5
!
25
=5194672859376. 
Ендіру  және  шығару  формуласы.  Жиындарды  бөліктеу  Айталық, 
Х
1
, Х
2
– ақырлы жиындар берілсін. Егер Х
1
Х
2
= , онда | Х
1
Х
2
| = | Х
1
|+|Х
2
|. 
Егер  Х
1
Х
2
,  онда  |Х
1
|+|Х2|  жиынында  Х
1
Х
2
  алынған  элемент  2-рет 
есепке алынады, демек |Х
1
Х
2
|=|Х
1
|+|Х
2
|-|Х
1
Х
2
|. 
Кез келген жиын үшін ендіру және шығару формуласын қорытайық:  
4-тжырым.  Х
i
;  i=1,…,n,  n 2  ақырлы  жиындары  берілсін.  Олай  болса 
|X
1
X
2
… X
n
|=(|X
1
|+…+|X
n
|)–(|X
1
X
2
|+|X
1
X
3
|+…+|X
n-
1
X
n
|)+(|X
1
X
2
X
3
|+ …+|X
n-2
X
n-1
X
n
|)-…+(-1)
n+1
|X
1
X
2
… X
n
|. 
Салдар.  Айталық  Х  –  ақырлы  жиын  болсын,  Х
1
,  …,  Х
n
  –  Х-тің  ішкі 
жиындары. Онда ішкі жиындардың ешбіріне тиісті емес х Х элементтердің 
саны мына 
|X\(X
1
X
2
… X
n
)|=|X|-(|X
1
|+…+|X
n
|)+(|X
1
X
2
|+… |X
n-1
X
n
|)-…- 
(-1)
n
|X
1
… X
n
| формула бойынша есептеуге болады. 
Ендіру  және  шығару  формуласын  жазудың  кең  тараған  формасы 
төмендегідей. Айталық, Х N элементтен тұратын ақырлы жиын, 
1
,…, 
n
 Х-
тің элементтерінде бар болуы да, болмауы да мүмкін қасиеттер. X
i
 арқылы 
i
 
қасиеттері бар элементтерден құралған жиынды белгілейміз. Яғни Х
i
 = {x X 
| 
i
(x)}, i=1…, n. 
N(
k
1
i
i
,...,
) арқылы
k
i
i
,...,
1
қасиеттерінің бәріне ие Х элементтерінің 
санын белгілейік:  
N(
k
1
i
i
,...,
)=|
k
2
1
i
i
i
X
...
X
X
|. 
1
,…,
n
  қасиеттердің  ешқайсысы 
жоқ элементтің санын N
0
=|X\(X
1
… X
n
)| деп белгілейік. 
Олай болса N0=N–S1+S2-…+(-1)nSn=N+
n
1
k
k
k
S
)
1
(
, 
мұндағы S
k
=
n
i
,...,
i
1
i
i
k
1
k
1
)
,...,
(
N
, k=1,…,n. 
Мысалы,  егер  n=3,онда  N
0
=N–N(
1
)–N(
2
)–N(
3
)+N(
1
,
2
)+N(
1
, 
3
)+N(
2
,
3
)–N(
1
, 
2
, 
3
). 
Мысал.  Айталық,  Х={1,2,…,10}, 
1
(x):"х–жұп", 
2
(х):"x>6", 
3
(x): 
"20
 есептейік. N
0 
= 10-5-4-5+2+2+1-0=1 (шынында, Х-ң ешқандай қасиеті жоқ элементі 1 
i
, i = 
1, 2, 3). 
Ендіру  және  шығару  формуласын  шығарып  пайдаланатын  тағы  бір 
есепті қарастырайық. 
Тәртіпсіздік туралы есеп. Әр түрлі а
1
, а
2
, …, a
n
 n зат және әр түрлі 

b
1
, b
2
,…, b
n
 жәшіктер бар. a
i
 заттарының ешқайсысы b
i
 жәшігіне түспейтіндей 
етіп,  a
i
  бұйымдары  қанша  әдәспен  жәшіктерге  салуға  болады?      Басқаша 
айтсақ, кез келген  i=1, 2, …, n үшін a
i
i болатындай 
 
1, 2, …, n сандарының қанша алмастырулары a
1
, a
2
, …, a
n
 бар? Яғни кез 
келген  элементтің  образы  өзінің  образына  тең  болмайтындай  қанша 
алмастыру бар? 
Берілген  Х  жиыны  ретінде  бұйымдардың  жәшіктерге  барлық  мүмкін 
орналасуларының жиынтығын аламыз.Олай болса N=| X |=n!  i қасиеттерін 
енгізейік:  "ai  bi  жәшігінде  бар",  i=1,…,n. 
)
,...,
(
1
k
i
i
N
)  саны  ij  бұйымы  b
ij
 
j=1,…,k жәшігінде бар болатын орналасулар (n-k)!-ға тең. 
Бірақ онда  k бұйымның өздерінің  S
k
  жәшіктеріне  түсетін  орналасулар 
саны:  
S
k 
=
!
k
!
n
)!
k
n
(
!
k
)!
k
n
(
!
n
)!
k
n
(
C
)
,...,
(
N
k
n
n
i
...
i
1
i
i
k
1
k
1
 
Енді  ендіру  және  шығару  формуласын  пайдаланып,  ешқандай  қасиет 
орындалмайтын (яғни ешқандай ai  бұйымы bi жәшігіне түспейді) орналасу 
саны: 
N
0
=N+
n
1
k
n
0
k
n
k
n
1
k
k
k
k
)
!
n
)
1
(
...
!
3
1
!
2
1
1
1
(
!
n
!
k
1
)
1
(
!
n
!
k
!
n
)
1
(
!
n
S
)
1
(
. 
Жақшадағы өрнек - е-1 шексіз қатар жіктеуінің 1-ші мүшелері, ендеше  
e
!
n
-n символдан тұратын тәртіпсіздіктер санына жақсы жуықтайды. 
Егер бізді тәртіпсіздіктің саны ғана емес, а
i
=i дәл k орында болатын, 
1, 2, …, n құралған а
1
,…,a
n
 алмастырулардың санын да анықтау керек болса, 
онда «кездесу» деп аталатын басқа есеп туады. Оның шешімі: n-нен k санды 
k
n
C  тәсілмен таңдауға болады, таңдағаннан кейін оны қалған n-k символдағы 
тәртіпсіздіктердің санына көбейту керек. Сонда 
)
)!
(
1
)
1
(
...
!
3
1
!
2
1
(
!
!
)!
(
1
)
1
(
...
!
3
1
!
2
1
1
1
(
)!
(
!
)!
(
!
)!
(
1
)
1
(
...
!
3
1
!
2
1
1
1
(
)!
(
k
n
k
n
k
n
k
n
k
k
n
n
k
n
k
n
C
N
k
n
k
n
k
n
k
n

жүктеу/скачать 3,62 Mb.

Достарыңызбен бөлісу: