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 элемент
бойынша (
) терулер саны
арқылы белгіленеді
және
.