Կոմբինատորիկա

Կոմբինատորիկա կամ կոմբինատորային անալիզ, մաթեմատիկայի բաժին է, որն ուսումնասիրում է օբյեկտների դիսկրետությունը, բազմությունների (էլեմենտների ընտրույթներ, վերադասավորումներ, վարիացիաներ, տարբեր կոնֆիգուրացիաների վերահաշվարկներ) կառուցվածքների հատկությունները, դրանց հետ կապված քանակական մեծությունները։ Կոմբինատորիական կապված է մաթեմատիկայի այլ բաժինների հետ, ինճպիսիք են` հանրահաշիվը, երկրաչափությունը, հավանականությունների տեսությունը, և կիրառվում է գիտության տարբեր ոլորտներում (օրինակ, գենետիկայում, ինֆորմատիկայում, վիճակագրական ֆիզիկայում)։

«Կոմբինատորիկա» տերմինը գործածության մեջ է դրվել Գոթֆրիդ Լայբնիցի կողմից 1666 թվականին հրատարակած «Դատողություններ կոմբինատորային արվեստի մասին» ()աշխատությունում։

Երբեմն կոմբինատորիկա հասկացությունը ընդգրկում է դիսկրետ մաթեմատիկայի ավելի ընդարձակ բաժին, որը ներառում է գրաֆների տեսությունը։

Պատմություն 
Կոմբինատորիկայի հիմնական հասկացությունները ի հայտ են եկել անտիկ աշխարհում։ Քրիստոսից առաջ 6-րդ դարում անտիկ հնդիկ բժիշկ Սուշրուտան պնդեց իր աշխատությունում, որ 6 տարբեր համերից կարող է լինել 63 հնարավոր կոմբինացիա՝ վերցնելով միայն մեկ համը, վերցնելով միայն երկուսը և այդպես շարունակ, սա հաշվում է բոլոր 26 − 1 հնարավոր դեպքերը։ Հույն պատմաբան Պլուտարքոսը քննարկեց Խրիսիպոսի և Հիպարքոսի բանավեճը կապված բավական նուրբ թվային խնդրի հետ, որը հետագայում պարզվեց, որ կապված է Շրոդեր-Հիպարքոսի թվերի հետ։ Օստորմախիոնում Արքիմեդը ընդունում էր դա որպես ծածկող գլուխկոտրուկ։

Միջին դարերում, կոմբինատորիկան շարունակվում էր լայնորեն ուսուցանվեր եվրոպական քաղաքակրթությունից դուրս։ Հնդիկ մաթեմատիկոս Մահավիրան ապահովել է բանաձև զուգորդությունների և կարգավորությունների համար, և այս բանաձևերը կարող է ծանոթ լինեին հնդիկ մաթեմատիկոսներին նույնիսկ 6-րդ դարում։ Փիլիսոփա և աստաղագետ Ռաբի Աբրահամ իբն Եզրան հիմնել է բինոմական գործակիցների համաչափությունը, մինչ դեռ համապարփակ բանաձևը ստացվել է ավելի ուշ թալմուդիստների և մաթեմատիկոս Լեվի բեն Գերշոնի կողմից 1321 թվականին։ Թվաբանական եռանկյունին՝ գրաֆիկական աղյուսակը, որը ցույց է տալիս բինոմական գործակիցների կապը իրար հետ, ցուցադրվել է մաթեմատիկոսների կողմից 10-րդ դարում գիտական հանդիպման ժամանակ, և վերջապես հայտնի է դարձել, որպես Պասկալի եռանկյուն։ Ավելի ուշ միջնադարյան Անգլիայում, կամպանոլոգիան ապահովեց մի օրինակ, որը այժմ հայտնի է, որպես կարգավորությունների վրա Համիլտոնյան ցիկլ որևէ Քելիի գրաֆում։

Վերածնունդի ժամանակաշրջանում, մաթեմատիկայի և բնագիտության հետ մեկտեղ, կոմբինատորիկան ևս վերածնվեց։ Պասկալը, Նյուտոնը, Բեռնուլլը և Էյլերը դարձան ի հայտ եկող ճյուղի հիմնադիրները։ Նորագույն ժամանակներում Սիլվեստերի (ուշ 19-րդ դար) և Պերսի Մակմահոնի (վաղ 20-րդ դար) օգնեց հիմք դնել թվաբանական և հանրահաշվական կոմբինատորիկային։ Նույն ժամանակաշրջանում, Գրաֆների տեսությունը նույնպես ներառվեց ճյուղի ընդլայմանը հիմնական պատճառը դարձավ Չորս գույների խնդրի կապը միմիանց հետ։

20-րդ դարի երկրորդ կեսին, կոմբիանտորիկան մեծ աճ արձանագրեց, որը հիմք հանդիսացավ ստեղծելու թեմատիկ տասնյակ նոր ամսագրեր և կոնֆերանսներ։ Այս առարկայի զարգացմանը խթանեց այլ առարկաների հետ նոր կապերն ու կիրառութությունները՝ հանրահաշվից մինչև հավանականություն, ֆունկցիոնալ անալիզից մինչև թվերի տեսություն և այլն։ Այս կապերը հետագայում քանդեցին կոմբինատորիկայի և համակարգչային գիտության միջև եղած սահմանները, բայց նույն ժամանակ բերեցին ճյուղի մասնակի բաժանմանը։

Ենթաբաժինները

Հաշվողական կոմբինատորիկա 
Հաշվողական (կամ թվարկիչ) կոմբինատորիկան զբաղվում է վերջավոր բազմությունների տարրերի տարբեր դասավորությունների կամ զուգակցումների նկարագրությամբ կամ դրանց քանակի հաշվումով։ Օրինակ՝ N–տարրանի A={a1, a2, ..., aN} բազմության ենթաբազմությունների քանակը 2N է։ Ուսումնասիրության առարկա հանդիսացող վերջավոր բազմությունների տարրերի վրա կարող են դրվել տարբեր բնույթի սահմանափակումներ, օրինակ՝ բազմության տարրերի՝ միմյանցից տարբեր լինելը կամ չլինելը, զուգակցման մեջ տարրերի կրկնողության թուլատրելի լինելը կամ չլինելը։

Հիմնական հասկացությունները 
Հաշվողական կոմբինատորիկայի հիմնական հասկացություններից են.
 Ընտրույթները
 Տեղադրությունները
 Զուգորդությունները
Կարևոր նշանակություն ունի կցման և արտաքսման սկզբունքը։

Կառուցվածքային կոմբինատորիկա

Էքստրեմալ կոմբինատորիկա

Հավանականային կոմբինատորիկա

Երկրաչափական կոմբինատորիկա

Տոպոլոգիական կոմբինատորիկա

Ծանոթագրություններ

Արտաքին հղումներ 
 Կոմբինատորային ալգորիթմներ և ալգորիթմների վերլուծություն

Կոմբինատորիկա