ՀՍՀ/ԿՈՄԲԻՆԱՏՈՐԻԿԱ

ԿՈՄԲԻՆԱՏՈՐԻԿԱ, կոմբինատ որային մաթեմատիկա, կոմբինատորային անալիզ, մաթեմատիկայի բաժին, որի կենտրոնական խնդիրն է վերջավոր թվով օբյեկտների զուգակցությունների (կոմբինացիաների), երկրաչափական պատկերների դասավորությունների և այլնի ուսումնասիրությունը: Կ-ի ակունքները հասնում են մինչև անտիկ աշխարհ, սակայն այն որպես գիտություն սկսել է կազմավորվել XX դարում: Զարգացման սկզբնական փուլում Կ-ի խնդիրները գլխավորապես մաթ. զվարճալիքներ էին: Արդի Կ-ի մեթոդները կիրառվում են մաթեմատիկայի բազմաթիվ բնագավառներում (հանրահաշիվ, երկրաչափություն, հավանականությունների տեսություն ևն): Կ-ի խնդիրները դասակարգվում են երկու հիմնական տիպերի, ա. գոյության խնդիրներ ու մ դիտարկվում է հետաքրքրություն ներկայացնող զուգակցությունների հարցը, բ. թվարկման խնդիրներ ու մ հիշյալ զուգակցությունների գոյությունը հայտնի է և պահանջվու մ է գտնել դրանց թիվը: Օրինակ, հնարավոր է արդյոք մատիտը թղթից չկտրելով և նույն գիծը երկու անգամ չանցնելով գծել նկ.1 և նկ.2 պատկերները, գտնել նշված պայմաններին բավարարող լուծումների k թիվը: Օգտվենք հետևյալ ընդհանուր սկզբունքից, գագաթը անվանենք զույգ (կենտ), եթե գագաթից ելնող հատվածների թիվը զույգ (կենտ) է: Գոյության խնդիրը լուծվում է դրականորեն միմիայն այն դեպքում, երբ կենտ գագաթների թիվը երկու, մեկ կամ զրո է: Նկ. 2-ի դեպքում k=0, այսինքն՝ խնդիրը լուծում չունի: Նկ. 1-ի դեպքում k=10, այսինքն՝ խնդիրն ունի միմյանցից տարբեր 10 լուծում: Կ-ի հիմնական սկզբունքներից է այսպես կոչված արտադրյալի կանոնը, որի պարզագույն դեպքը հետևյալն է. եթե որևէ Տ բազմության m 1 տարրերը օժտված են P1 հատկությամբ, m2 տարրերը՝ P1 հատկությամբ, ապա Տ բազմության տարրերից կազմված այն զույգերի թիվը, որոնց առաջին տարրն ունի (P_1), իսկ երկրորդը՝ (P_2) հատկությունը, հավասար է (m_1 \cdot m_2): Արտադրյալի կանոնը կիրառելով կարելի է գտնել ո տարր ունեցող S բազմության ոչ անպայման տարբեր տարրերից կազմված կարգավորված r-յակների թիվը՝ $A_n^r=n^r$: Նշված կանոնի միջոցով գտնվում է S բազմությունից r-վերցվածքների, այսինքն՝ S-ի տարբեր տարրերից կազմված կարգավորված r-յակների թիվը՝ $A_n^r=n(n-1)\cdot \cdot \cdot (n-r+1)$: n տարրերից ո-վերցվածքը կոչվում է տ ե ղ ա փ ո խ ու թ յ ու ն: S բազմության տարրերի տեղափոխությունների թիվը հավասար է $P_n=A_n^n=1\cdot 2\cdot \cdot \cdot n=n!$: S բազմության r տարր պարունակող տարբեր ենթաբազմությունների՝ r-գ ու ց ո ր-դ ու թ յ ու ն ն ե ր ի թիվը հավասար է $C_n^r=\frac{A_n^r}{A_r^r}=\frac{n(n-1)\cdot \cdot \cdot (n-r+1)}{r!}=\frac{n!}{r!(n-r)!}$ Թվարկման խնդիրներ լուծելու հզոր միջոց է ներառման և արտաքսման սկզբունքը: Դիցուք՝ n-ը S բազմության (P_i) (i=1,..., r) հատկություններով, իսկ (n_{i_1,...,i_s}) - (P_{i_1},...,P_{i_s}) հատկություններով օժտված տարրերի թիվն է: Ըստ այս սկզբունքի, S բազմության այն տարրերի թիվը, որոնք նշված հատկություններից ոչ մեկով օժտված չեն, որոշվում է $n_0=n-\sum _{i_1}{n}_{i_1}+\sum _{i_1<i_2}{n}_{i_1{i}_2}+\cdot \cdot \cdot +(-1{)}^s\sum _{i_1<\cdot \cdot \cdot <i_s}{n}_{i_1\cdot \cdot \cdot i_s}+(-1{)}^r{n}_{i_1\cdot \cdot \cdot i_r}$ բանաձևով:

Գրկ. Ռայզեր Դ. Ժ., Комбинаторная математика, пер. с англ., М., 1966; Виленкин Н. Я., Комбинаторика, М., 1969; Ежов И. И., Скороход А. В., Ядренко М. И., Элементы комбинаторики, М., 1977. Բ. Նահապետյան

Բ. Նահապետյան