9. 1B комбинаторика және жиындар теориясының элементтері: Жиын ұғымы



бет8/29
Дата05.04.2023
өлшемі1,18 Mb.
#173799
1   ...   4   5   6   7   8   9   10   11   ...   29
Байланысты:
Комбинаторика

10. Қайталанбалы алмастырулар.

1-мысал. а) Т, Ә, У, Л, І, К; б) С, А, Х, А, Р, А. әріптерінен қанша сөз (мағынасыз) құрастыруға болады.
Шешуі: а) мұнда әріптер әр түрлі болғандықтан Р6=6! Сонымен
Т, Ә, У, Л, І, К әріптерінен Р6 = 6! = 720 әр түрлі сөз құрастыруға болады.
б) Мұнда қайталанбайтын алмастыруды қолдануға болмайды, себебі
С, А, Х, А, Р, А әріптерінің ішінде А әрпі қайталанады. Бұл әріптерді нөмірлеп кояйық



1
С

2
А

3
Х

4
А

5
Р

6
А


1, 3, 6 нөмірлі С, Х, Р әріптерді қалдырып 2, 4, 6. нөмірлі А әріптерін алмастырайық, сонда:



1
С

2
А

3
Х

4
А

5
Р

6
А

1
С

2 А

3
Х

6
А

5
Р

4
А

1
С

4
А

3
Х

2
А

5
Р

6
А

1
С

4
А

3
Х

6
А

5
Р

2
А

1
С

6
А

3
Х

2
А

5
Р

4
А

1
С

6
А

3
Х

4
А

5
Р

2
А



2, 4, 6 нөмірлі А әрпін 3!=6 әдіспен алуға болады. Бірақ бұл әріптерді алмастырғаннан жаңа сөз шықпайтынын көру қиын емес, яғни
С А Х А Р А 6 рет кездестіріледі. Кез келген жаңа сөз 6 рет қездеседі (3!=6). Қайталанатын сөздерді алып тастағанда САХАРА әріптерінен алмастырылған сөздер ТӘУЛІК әріптерінен 3!=6 есе кем болады, яғни =4·5·6=120
Бұл сан 6 элементтен құрастырылған алмастыру болып табылады.
k элемент берілсін. Бірінші элемент n1 рет қайталансын, екінші элемент n2, …, к-шы – nк рет қайталансын n1+n2+…+nk= n.
Егер берілген элементтер әр түрлі болса, онда алмастыру саны n!-ға тең болар еді. n элементтердің ішінде қайталанатын элементтері бар алмастырудың саны n! –дан n1! n2! …nк! есе кем болады. Сонда қайталанатын алмастырудың саны мына формула бойынша есептеледі
= (4)

2-мысал. М, Е, К, Е, М, Е. әріптерінен алмастыру санын тап.
Шешуі: Мұнда М әрпі 2 рет қайталанады, яғни n1=2, Е әрпі 3 рет қайталанады, яғни n2=3 және К элементі үшін n3=1. n=n1+n2 +n3=2+3+1=6. Сонымен (4) формула бойынша қайталанатын алмастыру Р3,2,1= .

Жіктеуге арналған есеп. Әр түрлі n затты неше әдіспен n1, n2, …, nк элементтен тұратын 1, 2, …, к топтарға бөлуге болады деген мазмұндағы комбинаторикалық есептерді мына формула арқылы шығаруға болады.


(5)

3-мысал. №1, №2, №3, №4 нөмірлі 4 өнеркәсіп бөлімшесіне 10 маманды сәйкесінше 1, 2, 3, 4 мамандар баратындай неше әдіспен бөлуге болады?
Шешуі. Мұнда n= 10, n1 =1, n2 =2, n3 =3, n4 =4, онда (5) формула бойынша әдіспен 10 маманды 4 өнеркәсіп бөлімшесіне бөлуге болатынын есептейміз.

IV-тақырып. Терулер


  1. Қайталанбайтын терулер. Ньютон Биномы

Егер комбинациядағы элементтердің реті емес, тек оның құрамы қарастырылса, онда сөз теру жайлы болады.


Анықтама. Егер п элементті жиыннан m элементтен алынған таңдамалар бір бірінен ең болмағанда бір элементпен өзгешеленетін болса, онда мұндай таңдаманы п элементтен m бойынша алынған қайталанбайтын теру деп атайды.
Бұл символымен белгіленіп, төмендегі формула бойынша есептелінеді: = (6)
1-мысал. А, В, С, D төрт элементтен 2 элементті қайталанбайтын орналастырулар және терулер санын табу керек.
Шешуі. Орналастыру формуласы бойынша n=4, m=2, = = , яғни
АВ АС А D ВС ВD СD
ВА СА DА СВ DВ DС
мұнда элементтердің орналасу реті маңызды.
Ал дәл осы элементтер үшін, яғни n=4, m=2 жағдайда, (6) формула бойынша терудің санын табуға болады
= = = =6, яғни
АВ АС АD ВС ВD СD

мұнда элементтердің орналасу реті маңызды емес.


Теру санын есептеуде төмендегі қасиеттерді пайдалануға болады: 1. =1
2. = 1
3. = n
4. =
5.
Соңғы қасиет «рекурренттік формулалар» санына жатады. Егер n=6 деп алсақ, онда . Бұл қасиетті Паскаль үшбұрышы деп аталатын сандық таблица түрінде жазуға да болады. Оның төбесі және бүйір қабырғалары 1 санынан тұрады. Ал басқа кез-келген жолдың элементтері алдыңғы жолдың сол және оң жағында тұрған сандардың қосындысына тең болып, олардың арасына жазылады.

1
1 2 1


1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Сонымен n=6 үшін (6 жол) және m=3 , яғни 15=5+10.


Паскаль үшбұрышындағы сандар биномдық коэффиценттер деп аталады. Бұл коэффициенттер Ньютон биномының коэффи-центтеріне тең.
(а+в)n = an b0 + an-1 b1 + an-2 b2 +…+ a1 bn-1 + a0 bn
2-мысал. (а+в)9 өрнегін Ньютон биномының формуласын пайдаланып жаз.
Шешуі: (а+в)9 = а9 в0 + а8 в1 + а7 в2 + а6 в3 + а5 в4 +
а4 в5 + а3 в6 + а2 в7 + а1 в8 + а0 в9
Мұнда Паскаль үшбұрышындағы 9-шы жолдың коэффиценттері қолданылады.
Сонымен (а+в)9 9 + 9а8в1 +36 а7в2 + 84 а6в3 + 126 а5в4 + 126 а4в5 +
84 а3в6 + 36 а2в7 + 9 а1в8 + в9.

  1. Статистикалық бақылау


Статистикалық бақылауға арналған есеп. Әдетте қандай да бір бұйымның сапасын бақылау осы бұйымның белгілі бір бөлігін тексеру арқылы жүзеге асады. Егер тексерілген бөліктің көпшілігі жарамсыз болса, онда барлық бұйымды жарамсыз деп санайды. Ал егер тексерілген бөліктің көбі жарамды болса, онда барлық бұйым жарамды. Кей кезде бұйымдарды тексеру үшін бір бірден бұйымдар алынып тексеріледі де қайта қайтарылады, мұндай жағдайда бір бұйымның бірнеше рет тексерілуі мүмкін. n әртүрлі бұйымдардан m бұйым таңдау nm әдісімен таңдалады. Ал егер тексерілген бұйым қайта қайтарылмайтын болса, онда n әртүрлі бұйымдардан m бұйым таңдап алу саны
формуласымен есептеледі.
Бұйымның сапасын тексеру үшін оның қандай да бір бөлігін алғанда мұнда олардың орналасу реті маңызды емес. Мұндай жағдайда қайталанбайтын теру формуласын пайдаланамыз.
1-мысал. Жәшікте 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 цифрлары арқылы нөмірленген 10 бұйым бар. Кез келген үш бұйымды неше тәсілмен алуға болады?
Шешуі. Мұнда алынған бұйымдардың орналасу реті маңызды болмағандықтан теру формуласы бойынша
= тәсіл бар екенін көру қиын емес.
2-мысал. Жәшікте 10 деталь бар. Оның алтауы стандартты деталь. Жәшіктен құрамында екі стандартты деталь болатындай бес детальды неше әдіспен алуға болады?
Шешуі. Есептің шартынан N=10, n=6, к=2, m=5. n=6 стандарттық детальдан к=2 стандарттық детальды әдіспен алуға болады, ал қалған үш деталь стандартты болмау керек. N-n=10-6=4 стандартты емес детальдан m-k=3 стандартты емес детальды әдіспен алуға болады. Сонымен, жәшіктен 5 детальды алу және оның ішінде 3 стандартты емес деталь болатынын көбейту ережесі бойынша табамыз. = әдіс болады.



  1. Достарыңызбен бөлісу:
1   ...   4   5   6   7   8   9   10   11   ...   29




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет