Комбинато́рика —дискретті объектілерді, жиындарды және олардың арасындағы қатынастарды зерттейтін математиканың бір бөлімі. Комбинаторика математиканың көп салаларымен –алгебрамен, геометриямен, ықтималдықтар теориясымен тығыз байланысты және генетика, информатика, статистикалық физика облыстарында кеңінен қолданылады. «Комбинаторика» терминін 1666 жылы Лейбниц енгізген. ▼{{жедел жою|Энц. мақала емес}}
▲ Комбинато́рика —дискретті объектілерді, жиындарды және олардың арасындағы қатынастарды зерттейтін математиканың бір бөлімі. Комбинаторика математиканың көп салаларымен –алгебрамен, геометриямен, ықтималдықтар теориясымен тығыз байланысты және генетика, информатика, статистикалық физика облыстарында кеңінен қолданылады. «Комбинаторика» терминін 1666 жылы Лейбниц енгізген.
Іс жүзінде адамдарға заттардың өзара орнласуының барлық мүмкін жағдайларын есептеуге немесе қандай да бір іс-әрекеттің барлық мүмкін тәсілдер санын есептеуге тура келеді. Мысалы,5 оқулықты екі оқушыға неше түрлі тәсілмен үлестіріп беруге болады? Немесе 5 ұл бала мен 5 қыз баладан тұратын үміткерлер арасынан мектепте өткізілетін «көктем балының» королі мен королевасын неше түрлі тәсілмен таңдап алуға болады. Мұндай есептерді комбинаторика есептері деп, ал оны оқытып үйрететін математика саласын комбинаторика деп атайды.
Қосынды ережесі. Егер А жиынының элементтерінің саны санаулы болса, онда элементтері санын n(A) арқылы белгілейік. Кез келген санаулы А және В жиындары үшін (1) теңдігі орындалады. (1) формула бірнеше жиындардың бірігуі үшін де орындалады. Мысалы, А, В, С жиындары үшін бұл формула былай жазылады:
n(ABC)=n(A)+n(B)+n(C)-n(A B)- n(A C)-n(BC) +n(A BC). (2)
2.Көбейтінді ережесі. Кез келген санаулы А және В жиындары мен барлық (а;в) түріндегі қос элементтер саны үшін m=n(A)n(B) теңдігі орындалады.
1-мысал. 2-ге не 3-ке, не 5-ке бөлінетін неше үш таңбалы сан бар?
Шешуі: А арқылы 2-ге бөлінетін барлық үш таңбалы сандар жиынын, В арқылы 3-ке бөлінетін үш таңбалы сандар жиынын, ал С арқылы 5-ке бөлінетін үш таңбалы сандар жиынын белгілейік. Онда n(ABC) өрнегінің мәнін табу керек. n(A) =[900/2]=450
n(B)= [900/3]=300, n(C)= [900/5]=180.
n(A B)= [900/6]=150, n(A C)= [900/10]=90
n(BC)= [900/15]=60, n(A BC=[900/235]=30 болғандықтан (2) формула бойынша
n(ABC)=450+300+180-150-90-60+30=660
Жауабы: 660
3.Қайталанбалы орналастырулар
Элементтерінің саны n-ге тең Х жиыны берілсін. Осы жиынның элементтерінен құрастырылған мынадай тізімді қарастырайық:
х1,х2.....,хк (4) мұндағы кейбір элементтер қайталанып орналасуы мүмкін.Мұндай түрдегі тізімді ұзындығы к-ға тең терудеп атайды.
Х жиынының элементтерінен түзілген ұзындығы к-ға тең әрбір теруді n-нен к бойынша алынған қайталанбалы орналастырулар деп атайды. Ал барлық n-нен к бойынша алынған қайталанбалы орналастырулар саны А_n^k=n^k (5) формуласы бойынша анықталады.
2-мысал. 7 оқулықты екі оқушыға неше түрлі тәсілмен үлестіріп беруге болады?
Есеп шартында екі түрлі сан бар. 7 және 2. Онда (5) формула бойынша есеп жауабы 72 немесе 27 –не тең болуы қажет. Қайсысын алу керек? Әдетте оқушылар есеп шартына үстіртін талдау жасау арқылы осы жауаптардың бірінші нұсқасын таңдайды. Мұндай қорытындыға келу жобасы қарапайым: «7 оқулықты 2 оқушыға үлестіріп беру қажет. » Олай болса, есептің жауабы А_7^2=49 болу керек сияқты. Шындығында, А_2^7=128. Жауабы: 128 тәсіл.
4.Қайталанбайтын орналастырулар. Егер (4) терудегі элементтер қайталанбайтын болса, онда әрбір осындай теруді n-нен к бойынша алынған қайталанбайтын орналастырулар саны А_n^k=n!/(n-k)! формуласымен анықталады.
3-мысал. Неше тәсілмен 3 оқушыны 5 орындыққа отырғызуға болады?
Шешуі: Мұнда Х жиыны 5 элементтен тұрады және олардан белгілі үш оқушы отыратынедай үш орындық таңдап алу қажет. Әрине, егер белгілі бір оқушының қай орындыққа отыратыны маңызды болса, онда бізге қажет сан 5 элементтен 3 бойынша алынған барлық қайталанбайтын орналастырулар санына тең:
А_5^3=543=60
Жауабы: 60 тәсіл.
5. Алмастырулар. Егер n-нен к бойынша алынған қайталанбайтын орналастыруда n=k деп алсақ, онда бұл қайталанбайтын орпналастыруды n элементтен алынған алмастырулар саны P_n=n! Формуласымен анықталады.
6. Қайталанбайтын терулер.
Ал барлық n-нен к бойынша алынған қайталанбайтын терулер саны C_n^k=n!/k!(n-k)! формуласымен анықталады.
Терулердің бірнеше қасиетері бар:
C_n^k=C_n^(n-k)
C_n^k=C_(n-1)^(k-1)+C_(n-1)^k
4-мысал. Мини футболдан бір айналымдық жүйе бойынша ұйымдастырылған турнирге 5 команда қатысты. Турнирде барлығы неше ойын ойнады?
Шешуі: Әрбір матчқа 2 команда қатысады. Сондықтан турнирде ойналған ойындар саны 5-тен 2 бойынша алынған теруге тең:
C_5^5=5!/2!3!=10.
Жауабы: 10 ойын ойналады.
| 