Комбинаториканын элементтери -лк

Комбинаториканын элементтери

Комбинаторика – берилген обьекттерден тигил же бул шарттарга баш ийген түрдүү комбинацияларды түзүүгө болот деген маселелерди изилдеген дискреттик математиканын бөлүгү.

Аныктама. Терс эмес бүтүн маанилерде формулалары менен аныкталган f(n) функциясы n санынын факториалы деп аталат жана n! Деп белгиленет.

Аныктамадан үчүн алабыз п=0 болгондо 0!=1 болот.

Мисалдар. 1!=1, 2!=1∙2=2, 5!=1∙2∙3∙4∙5=120.

Практикада, көбүнчө берилген чектүү көптүктүн элементтеринен кандайдыр бир шартты канааттандырган элементтерди тандап алуу же аларды белгилүү тартипте жайгаштыруу талап кылынат.

Мисалдар.

1. 1, 2, 3, 4 цифраларынан канча түрдүү төрт орундуу цифралары кайталанбаган сандарды жазууга болот?

2. Театрдын кассасында турган 50 адам канча түрдүү жол менен кезекке турса болот?

3. Автомобилдин номери 4 цифрадан жана 2 тамгадан турса канча түрдүү номер чыгарууга болот?

4. 5 орундуу түрдүү цифралуу канча сан бар?

Эгерде көптүктүн бөлүкчө көптүктөрүнүн элементтеринин жайгашуу тартиби мааниге ээ болсо, анда аларды иреттелген көптүктөр деп айтабыз.

Эгерде көптүктүн бөлүкчө көптүктөрүнүн элементтеринин жайгашуу тартиби мааниге ээ болбосо, анда аларды иреттелбеген көптүктөр деп айтабыз.

Мисалы. a, b, c, d элементтеринен турган көптүктүн 3 элементүү 4 бөлүкчө бар

abc, abd, acd, bcd

жана 3 элементүү 24 иреттелген бөлүкчө көптүктөрү бар

,

acb, adb, adc, bdc,

bac,bad, cad, cbd,

bca,bda, cda, cbd,

cab, dab, dac,dbc,

cba, dba, dca, dcb,

Комбинаториканын элементтери негизинен үч бөлүктөн турат: орундаштыруу, орун алмаштыруу, топтоштуруу.

Орундаштыруу

Аныктама. п элементтен турган көптүк берилсин. п элементтүү көптүктүн ар бир элементтен түзүлгөн иреттелген бөлүкчө көптүгүн, п элементтен элементтүү орундаштыруу деп айтабыз.

Аныктоодон жана п элементтен элементүү орундаштыруу – бул бири биринен элементтеринин курамы жана алардын жайгашуу тартиби менен айырмаланган бардык элементтүү көптүктөрү экени көрүнүп турат.

п элементтен элементүү орундаштыруулардын саны

формуласы менен аныкталат.

Орундаштырууну белгилөө үчүн француз тилиндеги Arrangement (орундаштыруу, калыбына келтирүү) деген сөздүн биринчи тамгасы болгон тамгасы кабыл алынган.

Жогоруда биз мисал келтиргендей 4 элементтен түзүлгөн 3 элементүү орундаштыруу 24 барабар:

Мисал. Эсептегиле

Чыгаруу:

Мисал. Класстагы 20 орунга 4 окуучуну канча түрдүү жол менен жайгаштырууга болот?

Чыгаруу :

Демек, класстагы 20 орунга 4 окуучуну 116280 түрдүү жол менен жайгаштырууга болот.

Мисал. Автомобилдин номери 4 цифра жана 2 тамгадан турса канча түрдүү номер чыгарууга болот?

Чыгаруу: Кыргызстанда “Z 1899 Z”, “Z 1095 B” ж.б. сыяктуу номерлерди мамлекет чыгарат. Демек, тамгалары кайталанышы мүмкүн экен жана англис тилинин 26 тамгасы пайдаланылат деп эсептейли. Анда тамгаларга карата 26х26=676 серия бар, ал эми ар бир серияда 9999 момер чыгат. Анда 676х9999=6759324 номер чыгарууга болот.

Орун алмаштыруулар

Аныктама. п элементтен түзүлгөн п элементтүү орундаштыруу п элементтүү орун алмаштыруулар деп аталат.

Орун алмаштыруулар орундаштыруунун айрым бир учуру болот.

п элементтен түзүлгөн көптүктүн бардык п элемнеттүү орун алмаштыруулары да п элементтен турат, ошондуктан алар бири биринен элементтеринин тартиби менен гана айырмаланат.

п элементтүү орун алмаштыруулардын саны

формуласы аркылуу аныкталат.

Орун алмаштыруулардын белгилөө үчүн француз тилиндеги Permutation (орун алмаштыруу) деген сөздүн биринчи тамгасы болгон Р тамгасы кабыл алынган.

Мисал. Эсептегиле

Чыгаруу.

Мисал. Класста дежур болуу үчүн бир жумага 6 окуучу бөлүнгөн. Канча түрдүү жол менен кезекти уюштурууга болот?

Чыгаруу.

Топтоштуруулар

Аныктам. п элементтүү көптүк берилсин. п элементтүү көптүктүн ар бир элементтүү бөлүкчө көптүктөрү п элементтен түзүлгөн элементтүү топтоштуруу деп аталат.

Бул учурда п элементтүү көптүктүн элементтүү бөлүкчө көптүктөрү бири биринен элементтеринин курамы менен айырмаланат. Эгерде бөлүкчө көптүктөрүнүн арасында элементтеринин тартиби менен гана айырмаланган көптүктөр болсо, анда аларды окшош деп эсептейбиз.

п элементтүү көптүктүн бардык элементтүү топтоштурууларынын саны

формуласы аркылуу аныкталат.

Топтоштурууларды белгилөө үчүн француз тилиндеги Combinasion (топтоштуруу) деген сөздүн биринчи тамгасы болгон С тамгасы кабыл алынган.

Мисал. Жогрудагы мисалда көрсөтүлгөндөй 4 элементтен турган көптүгүнүн 3 элементүү 4 бөлүкчө көптүгү бар: abc, abd, acd, bcd

Мисал. Эсептегиле

Чыгаруу.

Орундаштыруулардын, орун алмаштыруулардын жана топтоштуруулардын санын эсептөө формулаларынын төмөнкүдөй касиеттери бар:

Текшерүүчү суроолор:

1. Ыктымалдык жөнүндө эмнени түшүнөсүң?

2. Ыктымалдыктар теориясын ким негизлеген?

3. Окуя деген эмне?

4. Окуянын кандай түрлөрү бар?

5. Ыктымалдыктын классикалык аныктамасын айтып бергиле.

6. Факториал деген эмне?

7. Комбинаториканын кандай элементтери бар?

8. Орундаштыруу деген эмне?

9. Орун алмаштыруу деген эмне?

10. Топтоштуруу деген эмне?