1. Комбинаторика есептері

Комбинаторика ақырлы жиындар үшін төмендегідей түрдегі есептерді шешеді:

а) берілген қасиетті қанағаттандыратын қанша элемент бар екенін анықтау;

б) берілген қасиетті қанағаттандыратын барлық элементтерді тізіп шығатын алгоритмді құру;

в) Кейбір белгісі бойынша көрсетілген элементтердің ішінен ең жақсыларын таңдап алу.

Біз тек бірінші типті есептермен айналысатын боламыз. Сонымен қатар n элементтен тұратын Х ақырсыз жиынның берілген қасиетті қанағаттандыратын r элементті таңдап алу жайлы есепті қарастырамыз.Осындай таңдаудың нәтижесін іріктеме деп атаймыз.

Іріктеме типтері

Іріктемелер екі белгісі бойынша типтерге бөлінеді: а) элементтер таңдау реті маңызды ма; б) таңдап алынған элементтердің арасында бірдейлері бар ма. Соңғы X жиынындағы элементтердің санын n деп, іріктемедегі элементтердің санын r деп белгілейік.

Арасында қайталанатындары жоқ элементтердің реттелген жиынтығын r бойынша n элементтің орналасуы деп атайды. Орналастыру санын деп белгілейді (1.6 кесте).

1.6 кесте

Іріктеме типтері

	Элементтер қайталанбайды	Элементтер қайталанады
Реті маңызды	орналастыру	Қайталамалы орналастырулар
Реті маңызды емес	теру	Қайталамалы терулер

Мысалы. 20 олимпиадаға қатысушылардың арасынан үш жеңімпазды анықтау үшін біз 20 элементтен 3 бойынша орналастыруын құрамыз, себебі мұнда тізімнің реті маңызды. (бірінші, екінші, үшінші орын), және бірде бір фамилия екі рет кездеспеуі керек.

Арасында бірдейлері бар элементтердің реттелген жиынтығын қайталамалы орналастыру деп атайды. Мұндай іріктемелердің санын деп атайды.

Мысалы. Он цифрдың көмегімен барлық мүмкін төрторынды телефон нөмірін құрғанда, біз 10-нан 4 бойынша қайталамалы орналастыру аламыз, себебі телефон нөмірінде бірдей цифрлар кездесуі мүмкін, цифрлардың жазылу реті маңызды.

Арасында қайталанатын элементтері жоқ реттелмеген элементтердің жиынтығын n элементтен r бойынша теру деп атайды. Оны деп белгілейді.

Мысалы. Сегіз адамның ішінен қар тазалау үшін күрек беруге үшеуін таңдап алу керек. Мұнда таңдама реті маңызды емес, және бір адамға екі күрек беруге келмейді – сонымен сегізден үш бойынша теруді аламыз.

Арасында бірдейлері бар реттелмеген элементтердіңАрасында бірдейлері бар реттелмеген элементтердің жиынын қайталамалы теру деп атаймыз. Оны деп белгілейміз.

Мысал. Үш әр түрлі негативтен бес фотосуретті басып шығарғымыз келсін. Бұл жерде басып шығару реті маңызды емес, ал алынған жиынтықта бірдей суреттер болады, бұл үш элементтен бес бойынша алынған теру болып табылады.

Комбинаториканың негізгі ережелері

Қосынды ережесі. Егер a элементі m әдіспен таңдап алынса, ал b элементі басқа бір k әдіспен таңдап алынса, онда a немесе b элементтерінің біреуін m+k әдіспен таңдап алуға болады.

Мысал. Ат қорада төрт ат және екі пони бар. Өзіне скакун таңдап алудың неше мүмкіндігі бар? Бұл жерде біз қосу ережесін қолданамыз: екі жиыннан бір элементті (ат немесе пони) әдіспен таңдап аламыз.

Көбейту ережесі. Егер а элементін m әдіспен таңдап алуға болса, ал бұдан кейін b элементін k әдіспен алынады, онда элементтер жұбын әдіспен таңдап алуға болады.

Мысал. Шағылар жұбын алты әдіспен таңдап алуға, ал бәтінкелер жұбын үш әдіспен таңдап алуға болады. Неше тәсілмен шаңғыны бәтінкемен таңдап алуға болады? Бұл жерде элементтер жұбын қолданамыз (шаңғы, бәтінке) – барлығы 6*3=18 әдіспен таңдаймыз.

Енгізу-шығару ережесі. Егер S қасиетін m элемент қанағаттандырса, ал P қасиетін k элемент қанағаттандырса , онда S немесе P қасиеттерін элемент қанағаттандырады, мұндағы l – бір уақытта S және P қасиетттерін қанағаттандыратын элементтер саны.

Мысал. Сөреде алма және алмұрттан жасалған компоттар тұр. 10 банкіде алма, алтауында алмұрт, үшеуінде алма да алмұрт та бар. Сөреде барлығы қанша банкі бар? Мұнда , яғни сөреде барлығы банкі бар.