І Комбинаторика
1.1 Комбинаторика ұғымы
Көптеген машықтану есептерін шешкенде қандай да бір элементтер жиынтығынан көрсетілген қасиеттерге ие болатын элементтерді таңдауға және оларды белгілі бір ретпен орналастыруға және т.т. орындауға әкеледі. Осындай есептерде элементтердің қандай да бір комбинациялары туралы сөз болғандықтан оларды комбинаторикалық есептер деп атайды. Комбинаторика – берілген элементтерден қандай да бір шарттарға бағынатын қанша әртүрлі комбинацияларды құруға болатын сұрақтарды оқытатын математика бөлімі. «комбинаторика» атауы латын сөзі «combina» дан шығады, аударғанда - «теру», «біріктіру».
Элементтердің таңдалған топтары комбинациялар деп аталады. Егер комбинацияның барлық элементтері әртүрлі болса, онда қайталанбайтын комбинация, ал бірдей элементтері болса, қайталанбалы комбинация аламыз. Комбинаторикалық сиапаттағы ой- пікірлер ықтималдық теориясы, алгебра тәрізді математикалық бөлімдерінде де өте кең таралған. Комбинаторикалық анализ есептері ерте кезден белгілі. Оның дамуына көптеген математиктер үлес қосқан. Алайда, комбинаторикалық анализ өз алдына пән ретінде ХХ ғасырда ғана қалыптаса бастады. Комбинаторикалық графтар теориясы, шектеулі автоматтар теориясы секілді математиканың салаларымен тығыз байланысты. Графтар теориясы (ағылшын тілінде graph teory)- түйіндері нүктелер жиыны, ал түйіндердің жалғасуы (қабырға деп аталатын) парлы екі нүкте болып келетін тор түрінде бейнеленеді. Егер, түйіндердің жалғасу реті маңызды орында болса- бағытталған граф, әйтпесе бағытталған граф болады. Оның тәжірибиелері ғылыми тәжірбиелерді жоспарлауды және оларға талдау жасауда, сызықтық және динамикалық бағдарламауда, математикалық экономикада тағы басқа ғылым мен техниеалық көп деген салаларында қолданылады.
Комбинаторикалық есептердің ішінде, қалыпты емес ойлауды талап ететін ережелер жиі кездеседі. Ондай есептердің оқушылардың логикалық ойлау қабілетін дамытуға үлкен әсері бары сөзсіз. Төменгі сынып оқушылары іріктеу тәсілімен және мүмкін нұсқалар ағашы тәсілімен есептерді шығарады. Көптеген есептерді шешуде қолданылатын комбинаторика формулаларын жоғары сынып оқушылары қолданғаны тиімді.
Комбинаторикалық есептерді шығарғанда екі ереже – қосу және көбейту жиі қолданылады:
Қосу ережесі. Еген а және b элементтерін сәйкес m және n тәсілмен таңдап алуға болатын болса, онда олардың кез келген біреуін m+n тәсілмен алуға болады.
Көбейту ережесі. Егер бірінші топта m әртүрлі элемент, ал екінші топта n элемент бар болса, онда осы екі тортан алынып құрылған қосақтар саны m*n арқылы анықталады.
Расында бірінші топтың бір элементі екінші топтың әрбір элементімен қосақталады және керісінше, сондықтан қосақтардың жалпы саны m* n көбейтіндісімен анықталады.
Жалпы жағдайда A1 жиынында n1 элемент, A2 де n2 элемент.... Ak жиынында nk элемент болсын. Онда A1 х A2 х ....хАк жиынында n1*n2….*nk әртүрлі элемент бар. Ереже басқаша да айтылады. Бірінші әрекет әртүрлі n1 , екінші әрекет әртүрлі n2 тәсілмен, ... к-шы әрекетті әртүрлі nk тәсілмен орындауға болады. Сонда барлық к әрекетті әртүрлі n1*n2….*nk тәсілмен жасауға болады.
Комбинаторика бұл дискретті объектілерді, жиындарды және олардың арасындағы қатынастарды зерттейтін математиканың бір бөлімі болып табылады. Комбинаторика математиканың көп салаларымен, геометрия және ықтималдықтар теориясымен тығыз байланысты, информатика мен статистикалық физика салаларында кеңінен қолданады. «Комбинаторика» терминін 1666 жылы Лейбниц енгізген. Комбинаторика (латын тілінде combino- жалғастырамын) комбинаторикалық анализ деп те аталады. Комбинаторикалық анализ ол комбинаторикалық математика, комбинаторика- математиканың кезкелген шектеулі жиын бөліктерінің орналастыруымен өзара орналасуына байланысты мәселелерін зерттейтін бөлімі.
Комбинаторикалық анализ проблемасының үш түрі бар. Яғни санап шығу, салу, таңдап алу. Санап шығу есептерінде объектілердің шектеулі жиында кездесетін шарттарды қанағаттандыратын орналастырулар саны қарастырамыз. Іс жүзінде мұндай есептер жасаушы функциялар әдісі мен Д. Пойаның (1887- 1985) санап шығу әдісінің көмегімен шешеміз. Салу есептерінде кейбір қасиеттері сақталатын шектеулі жиын бөліктері конфигурациясының болуы мүмкін, егер бар болса оның салынатындығы туралы мәселелер қарастырамыз. Таңдап алу есептерінде ішкі жиын бөліктерінің кейбір құрамын таңдап алу шарттарын зерттейміз, мұндай есептерді шешкенде комбинаторикалық ойлармен қатар, алгебралық тәсілдерде қолдамамыз.
Есеп 1. Кітап сөресінде 12 математика және 6 физика кітаптары бар. Бір пәнненекі кітапты сөреден алудың неше әртүрлі тәсілі бар?
Шешуі: Көбейту ережесі бойынша екі математиканы  , екі физиканы  тәсілмен таңдаймыз. Бір пәннен екі кітапты алуымыз керек: не 2 математика, немесе 2 физика. Қосу ережесін қолданамыз:  .
Есеп 2. «Барлығы шәй үшін» дүкенінде 10 әртүрлі кесе және 6 әртүрлі тәрелке бер. Бір кесе мен бір тәрелкенің парын неше нұсқамен сатып алуға болады?
Шешуі: Кесені 10 түрлі тәсілмен, ал тәрелкені 6 түрлі тәсілмен таңдауға болады. Бізге бір кесе мен бір тәрелкенің парын алу керек, онда оны  тәсілімен орындауға болады. Яғни көбейту тәсілі.
Теорема: Егер екі арқылы а және В жиындарының қиылысуы бос жиын болса, онда олардың бірігуінің элементтерінің саны А және В жиындарының элементтерінің санының қосындысына тең:
 .
Бірнеше жиындар қиылыспаса да, осы ұйғарым дұрыс.
Екі жиынның қиылысуы бос болмаса, онда
Жиындар саны 3- ке тең болса, онда 
Мысалы: Алғашқы 100 натурал санның арасында неше сан 2- ге де, 3- ке де, 5- ен де бөлінбейді?
Шешуі: Жиындарды белгілейік: А- 2- ге бөлінетін сандаржиыны; В- 3- ке бөлінетін сандар жиыны; С- 5- ке бөлінетін сандар жиыны. А және В- ның қиылысуы- 6- ға бөлінетін сандар жиыны және т.т. Сонда жиынға сәйкес элементтер саны:
Мұндағы  санының бүтін бөлігі.
Сонымен үш жиынның бірігуінің элементтер саны
2- ге де, 3- ке де, 5- ке де бөлінбейтін сандар: 
Мысалы: 20 әріпті және 10 цифрды қолданып, 2 әріптен және 2 цифрдан тұратын неше нөмір құруға болады?
Шешуі: А- 20 әріптен тұратынжиын, В- 10 цифрдан тұратын жиын болсын. Әрбір нөмір АхАхВхВх декарттық көбейтіндісі, онда
Комбинаторика элементтері
Мүмкін нұсқаларды іріктеу
Қарапайым есептер әртүрлі кестелер және схемалар құрмай мүмкін нұсқалардың толық іріктеумен шешеміз.
Есеп 1.  цифрлар жиыны берілген. Осы цифрлардан неше әртүрлі екі таңбалы сан құрауға болады?
Шешуі: Іріктеу әдісі: екі таңбалы сандар-12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43. Барлығы 12 сан.
Есеп 2. Теннисшілер тобындағы Ардақ,Бақыт,Шолпан және Тамараны пармен жарысқа қатысуға екі-екіден жаттықтырушы таңдайды. Осындай парларды таңдаудың қанша тәсілі бар?
Шешуі: Спортшылардың аттарын бірінші әріптерімен белгілейміз: А, Б, Ш, Т. Ардақ кіретін барлық парларды құрамыз: АБ, АШ, АТ. Енді Бақыт кіретін, бірақ Ардақ кірмейтін парларды жазайық: БШ, БТ. Енді Шолпан кіретін, бірақ Ардақ пен Бақыт кірмейтін парлар: ШТ. Сонымен 6 пар алдық: АБ, АШ, АТ, БШ, БТ, ШТ. Жауабы: 6 пар.
Есеп 3. 1, 2, 3, 4, 5 цифрларынан қандай екі таңбалы сандарды құрауға болады? (Цифрлар қайталанады.)
Шешуі: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
Есеп 4. 100 м-лік ақтық жүгіруге Бауыржан, Батыржан және Айжан қатысады. Жүлделі орындарды бөлудің мүмкін нұсқаларын айтыңыз.
Шешуі: Нұсқа1: 1) Бауыржан, 2) Батыржан, 3) Айжан.
Нұсқа2: 1) Бауыржан, 2) Айжан, 3) Батыржан.
Нұсқа3: 1) Айжан, 2) Бауыржан, 3) Батыржан.
Нұсқа4: 1) Айжан, 2) Батыржан, 3) Бауыржан.
Нұсқа5: 1)Батыржан, 2) Айжан, 3) Бауыржан.
Нұсқа6: 1) Батыржан, 2) Бауыржан, 3) Айжан.
6 нұсқа немесе бірінші орында 3 тәсілмен, екінші орынды 2, үшінші орынды 1 тәсілмен таңдаймыз, онда 3*2*1=6 тәсіл.
Есеп 5. Би үйірмесіне Айдос, Елдос, Жандос және Балым, Айым, Балнұр қатысады. Қыздар жәні ұлдардан билеуге қандай парлар жасауға болады?
Шешуі:1) Балым- Айдос, 2) Балым- Елдос, 3) Балым- Жандос, 4) Айым-Айдос, 5) Айым- Елдос, 6) Айым- Жандос, 7) Балнұр- Айдос, 8) Балнұр-Елдос, 9) Балнұр- Жандос. Барлығы 9 пар.
Мүмкін нұсқалар ағашы
Әртүрлі комбинаторикалық есептер арнайы схемалар көмегімен шешіледі. Сырттай мұндай схема ағашты еске түсіреді, сондықтан әдістің аты мүмкін нұсқалар ағашы.
Есеп 6.  сандар жиыны берілген. Төрт таңбалы сандарды құру керек.
Шешуі: «Нұсқалар ағашы»
  3 4 1234
   2 4 3 1243
    1 3 2 4 1324 6 сан.
4 2 1342
 4 2 3 1423
3 2 1432
1
    2 3
  4
1
 3 2
4
1
4 2
3
Барлық төрт таңбалы сандар:  «Нұсқалар ағашы»
Есеп 7. Туристер тау өзеніне саяхат жасағылары келді. Жолдың бірінші бөлігін пойызбен немесе мотоциклмен, ал екінші бөлігін қайықпен, велосипедпен немесе жаяу жүруге болады. Туристер саяхаттағанда жолды жүрудің қандай мүмкін нұсқалары бар?
Шешеуі: Мүмкін нұсқалар ағашын құрамыз. Белгілеулер енгізейік: П- пойыз, М- мотоцикл, Қ- қайық, В- велосипед, Ж- жаяу, А- ат.
А
Қ Ж
П В А
Ж
Ж А
Ж
А
 Қ Ж
  М В А
Ж
Ж А
Ж
Суретте саяхатқа жүрудің барлық 12 мүмкін нұсқалары көрсетілген.
Есеп 8. Сәрсенбі күніне математика, қазақ тілі, тарих, ағылшын тілі және денешынықтыру бес пәннен сабақ кестесін қанша тәсілмен құруға болады? Сабақ кестесінде математика екінші болу керек.
Шешуі: Мүмкін нұсқалар ағашын құрамыз. Белгілулер енгізейі: М- математика, Қ- қазақ тілі, Т- тарих, А- ағылшын тілі, Д- дене шынықтыру. Бірінші сабақ математикадан басқа пәннің кез келгені болады. Бірінші пән- қазақ тілі үшін жасайық, қалғандарына соған ұқсас: 6 нұсқа. Онда барлығы 24 нұсқа.
 А Д
 Т Д А
    Қ М А Т Д
  Д Д Т
А Т
Т А
Қ Қ Қ Қ Қ Қ Т Т Т Т Т Т А А А А А А Д Д Д Д Д Д
М М М М М М М М М М М М М М М М М М М
Т Т А А Д Д Қ Қ А А Д Д Қ Қ Т Т Д Д Қ Қ Т Т А А
А Д Т Д Т А А Д Қ Д Қ А Т Д Қ Д Қ Т Т А Қ А Қ Т
Д А Д Т А Т Д А Д Қ А Қ Д Т Д Қ Т Қ А Т А Қ Т Қ
Кесте құру
Комбинаторикалық есептерді кесте көмегімен де шешуге болады.
Есеп 1. 1, 3, 4, 6, 7, 8, 9 цифрларынан неше екі таңбалы тақ сандар құрастыруға болады?
Шешуі: кесте құрамыз: сол жақта бірінші баған- ізделінді сандардың бірінші цифры, жоғары жақта бірінші жол- екінші цифры.
|
1
|
3
|
7
|
9
|
1
|
11
|
13
|
17
|
19
|
3
|
31
|
33
|
37
|
39
|
4
|
41
|
43
|
47
|
49
|
6
|
61
|
63
|
67
|
69
|
7
|
71
|
73
|
77
|
79
|
8
|
81
|
83
|
87
|
89
|
9
|
91
|
93
|
97
|
99
| |
Скачать 2.38 Mb.