2.1 Негізгі комбинаторлық ұғымдар

 

 

Комбинаторика бұл ақырлы жиындардағы элементтер санын есептейтін әдістерді зерттейтін математиканың саласы.

Е = {а1, а2, …, аn} – ақырлы жиын болсын.

Е элементтерінен k элемент бойынша орналастыру бұл Е жиынының k-элементті реттелген ішкі жиыны.

Масал 1  Е = {а1, а2, а3} және k=2 болсын. Бұл жиынның 2 элемент бойынша орналастырулар

{а1, а2}, {а1, а3 }, {а2, а1 }, {а3, а1}, {а2, а3}, {а3, а2}

ішкі жиындар болады.

n элементтен k бойынша орналастырулар санын  арқылы белгілейік. Кейбір орналастыруды құруда 1-ші орынға n элементтің кез келгенін, 2-ші орынға – қалған n-1 элементтің кез келгенін қоюға болады және т. с. с. Сондықтан

 ,  .

  болғанда  және  деп санаймыз.

n элементтен алмастырулар дегеніміз бұл Е жиынының n-элементті реттелген ішкі жиындары.

Мысал 2  Е = {а1, а2, а3}. Е жиынының алмастырулары {а1, а2, а3}, {а1, а3, а2}, {а2, а1, а3}, {а2, а3, а1}, {а3, а1, а2}, {а3, а2, а1} болады.

n элементтен алмастырулар санын  арқылы белгілейік. Алмастырулар орналастырулардың k=n болғандағы дербес жағдайы екендігі айқын. Сондықтан

.

Ескерту. 0!=1.

Е элементтерінен k элемент бойынша терулер бұл Е жиынының k-элементті реттелмеген ішкі жиындары.

Мысал 3  Е = {а1, а2, а3} және k=2 болсын. Е элементтерінен 2 элемент бойынша терулер {а1, а2}, {а1, а3}, {а2,  а3} болады.

n элементтен  k элемент бойынша () терулер саны  арқылы белгіленеді және

.