1. Комбинаторика пәні. Қайталанатын және қайталанбайтын таңдаулар. Комбинацияны құрайтын типтер
жүктеу/скачать 121,79 Kb.
|
1 2
- Бұл бет үшін навигация:
- 2. «Бұтақтар» әдісі. «Бұтақтар» көмегімен варианттарды есептеу.
|
Комбинаториканың негізгі ұғымдары 1. Комбинаторика пәні. Қайталанатын және қайталанбайтын таңдаулар. Комбинацияны құрайтын типтер Берілген жиындағы элементтерден қандай да бір шартқа бағынатын әртүрлі қанша комбинация құрастыруға болады деген сұрақты қарастыратын математика саласын комбинаторика деп атайды. Комбинаторика ұғымы XVI - ғасырда пайда болған. Ол кезде карта, сүйек ойыны, лотереялар сияқты құмарлық ойындар үлкен орын алған. Сондықтан алғашқыда комбинаторикалық есептер негізінен құмарлық ойындарға қатысты болған. Комбинаториканың дамуы Я.Бернулли, Лейбниц, Эйлер есімдерімен тығыз байланысты. Соңғы жылдары комбинаторика жедел даму үстінде. Комбинаторикалық әдістер транспорттық есептер шешуде, кестелер, өндірістік жоспарлар құрастыруда және өнімді өткізу мәселесінде қолданылады. Комбинаториканың негізгі ұғымдары көптеген ықтималдық есептерінің, сызықтық программалаудың, статистиканың негізі болып табылады. Сонымен қатар, комбинаторика автоматтар теориясында, экономикалық есептерде, биология және генетикада қолданылады. Берілген жиын n әртүрлі элементтерден тұрсын. Бұл жиыннан бір элементті аламыз, содан кейін жиыннан бұл элементтен басқа екінші элемент алынады т.с.с., яғни әрбір таңдауда алынған элементтерден басқа жаңа элементтер алып отырамыз. Бұл кайталанбайтын таңдау. Берілген жиын k типті элементтерден тұратын болсын, мұнда әрбір типтің ішіндегі элементтер бірдей. Кезекті таңдауда, алдыңғы алғаннан басқа, немесе алдында алғандағыдай жаңа элемент аламыз. Бұл қайталанатын таңдау деп аталады. Қайталанатын таңдауға өзгеше сипат беруге болады. Берілген жиын әртүрлі п элементтен тұрсын. Бірінші элементті жазып алып, оны жиынға қайта қайтарамыз. Екінші элементті аламыз. Бұл жаңа немесе алдыңғы қайтарылған элемент болуы мүмкін. Мұндай таңдау қайталанатын таңдау. Жиыннан алынған элементтер таңдауларды құрайды. 2. «Бұтақтар» әдісі. «Бұтақтар» көмегімен варианттарды есептеу. Есеп шығаруда қолданылатын комбинаторикалық әдістің бірі - жалпы бір схемаға негізделген «бұтақтар» әдісі. Мүмкін таңдау саны әр қадам сайын алғашқыда қандай элемент алынғанына байланысты болатын комбинацияны құру процесін «бұтақтар» түрінде қарастырған ыңғайлы. Алдымен бір нүктеден әр түрлі неше таңдау алуға болатын бағыт көрсетіледі, яғни әрбір тармақ бір элементке сәйкес келеді. Алынған бағыттардан, екінші қадамда қанша таңдау жасауға болса, бір нүктеден сонша тармақтар (стрелка) жүргізіледі. 1-мысал. а) Теңге екі рет, б) үш рет лақтырғандағы мүмкін нәтижелердің «бұтақтарын» салып көрсет. Шешуі: а) теңгені бір рет лақтырғанда елтаңба (Е) немесе сан (С) жағымен түсетін екі жағдай болады. Сондықтан бірінші қадамда бір нүктеден шығатын 2 тармақ болады. Е С 1-қадам Е С Е С 2-қадам Теңгені екінші рет лақтырғанда да екі жағдай болады. Сонда екінші қадамда төрт нүкте аламыз, яғни теңгені екі рет лақтырғанда төрт жағдай болуы мүмкін, ЕЕ, ЕС, СЕ, СС. б) Дәл осылайша теңгені үш рет лақтырғанда ЕЕЕ, ЕЕС, ЕСЕ, ЕСС, СЕЕ, СЕС, ССЕ, ССС жағдайлар болады. Оның бұтақтары төмендегі суреттегідей. Е С 1- қадам Е С Е С 2 – қадам Е С Е С Е С Е С 3 - қадам 2-мысал. а) 2,3,4 цифрларын бір рет қана қолдану арқылы неше әдіспен үш таңбалы сан жазуға болады? б) 2 және 0 цифрларынан неше әдіспен төрттаңбалы сан жазуға болады? Шешуі: а) бұл есептің шешімін «бұтақтар» әдісі арқылы көрсетейік. Сан үштаңбалы болғандықтан, үш қадам болады. Бірінші цифр үш әдіспен таңдалады, сондықтан бірінші қадамда үш бағыт болады. Екінші цифр (цифрлар қайталанбайтын болғандықтан) қалған екеуінен таңдалады. Сонда бірінші қадамның әрбір нүктесінен екі тармақ шығады. Үшінші цифр қалған біреуінен таңдалатындықтан екінші қадамның әрбір нүктесінен бір тармақ шығады. Соңғы қадамда алты нүкте пайда болады, яғни алты үштаңбалы сан алуға болады, 234, 243, 324, 342, 423, 432. 2 3 4 1- қадам 3 4 2 4 2 3 2- қадам 4 3 4 2 3 2 3 - қадам б) 2 және 0 цифрларынан тұратын төрт таңбалы санның шығу «бұтақтарын» салайық. Суретте төрт деңгей болады. Бірінші цифр екі ғана болады, өйткені 0 цифрынан басталатын төрт таңбалы сан болмайды. Екінші, үшінші, төртінші цифрларды да екі әдіспен алуға болады. Төртінші деңгейде сегіз нүкте пайда болады, яғни сегіз төрт таңбалы сан алынды: 2000, 2002, 2020, 2022, 2200, 2202, 2220, 2222. 2 1-қадам 0 2 2- қадам 0 2 0 2 3-қадам 4-қадам 0 2 0 2 0 2 0 2 3-мысал. А, Б, В үш әрпінен дауыссыз дыбыстар қатар келмейтін барлық үш әріпті сөзді құрастыру керек. Шешуі: Шығу «бұтақтарын» көрсетейік. Бұл «бұтақтардан» 11 сөз пайда болатынын көреміз, атап айтқанда ААА, ААБ, ААВ, АБА, АВА, БАА, БАБ, БАВ, ВАА, ВАБ, ВАВ. А Б В 1-қадам А Б В А А 2-қадам А Б В А А А Б В А Б В 3 - қадам жүктеу/скачать 121,79 Kb. Достарыңызбен бөлісу:
|
1 2