კომბინატორიკა

კომბინატორიკა, კომბინატორული მათემატიკა,კომბინატორული ანალიზი, მათემატიკის დარგი, რომელიც შეისწავლის ძირითადი (საბაზისო) სიმრავლის ელემენტების ამორჩევისა და განსაზღვრული წესის მიხედვით განლაგების ამოცანებს, ანუ კომბინატორული კონფიგურაციების არსებობას, მათი აგების ალგორითმებს, ასეთი ალგორითმების ოპტიმიზაციას, აგრეთვე მოცემული კლასის კომბინატორული კონფიგურაციების აღწერას, კერძოდ, მათი რაოდენობის განსაზღვრის ამოცანებს. ტერმინი „კ.“ დაამკვიდრა გ.ლაიბნიცმა (კომბინატორული ხელოვნება, 1666). ხშირად კ-ის ნაწილად მოიხსენიებენ გრაფების თეორიასაც. კ-ის უმარტივესი ამოცანებია, განისაზღვროს:

1. წყობათა რაოდენობა n ელემენტიდან m ელემენტად – რამდენი ხერხით შეიძლება ამოვარჩიოთ m ელემენტი n-ელემენტიანი სიმრავლიდან, ამორჩეული ელემენტების მიმდევრობის (განლაგების) გათვალისწინებით; წყობათა რაოდენობა გამოითვლება ფორმულით:

An^m=n(n-1)(n-2)...(n-m+1)==n!/(n-m)!

2. გადანაცვლებათა რაოდენობა – რამდენი ხერხით შეიძლება დალაგდეს ერთმანეთისგან განსხვავებული n ელემენტი; გადანაცვლებათა რაოდენობა გამოითვლება ფორმულით:

Pn=n(n-1)(n-2)...3·2·1= n!

(იკითხება „n ფაქტორიალი“).

3. ჯუფთებათა რაოდენობა n ელემენტიდან m ელემენტად – რამდენი ხერხით შეიძლება ამოვარჩიოთ m ელემენტი n-ელემენტიანი სიმრავლიდან, ამორჩეული ელემენტების მიმდევრობის (განლაგების) გაუთვალისწინებლად (ანუ m-ელემენტიანი ქვესიმრავლე n-ელემენტიანი სიმრავლიდან); ჯუფთებათა რაოდენობა გამოითვლება ფორმულით

             С_n^m=$C_n^m=\frac{n!}{m!(n-m)!}=\frac{n(n-1)...(n-m+1)}{(m-1)...3\times 2\times 1}$                 

        

ზოგჯერ იყენებენ აღნიშვნას

  $C_n^m=\frac{n}{m}$

 

ამ ძირითად კომბინატორულ სიდიდეთა შორის არსებობს შემდეგი კავშირი:

An^m=Pn Сn^m 

მართებულია ასევე ფორმულა

(1+ x)ⁿ =Σⁿ_m=0 Сn^m x^m

რ-საც ხშირად ნიუტონის ბინომს უწოდებენ (ეს ფორმულა ნატურალური მაჩვენებლის შემთხვევაში ცნობილი იყო ჯერ კიდევ ძვ. აღმოსავლეთის მათემატიკოსთათვის). თანამედროვე კ-ის ჩასახვასა და განვითარებაში დიდი წვლილი მიუძღვის ბ. პასკალს, პ. ფერმას (1601–65, საფრ.), ი. ბერნულის (1655–1705, გერმ.), ლ. ეილერს. XX ს-ში ინტერესი კ-ის მიმართ მკვეთრად გაიზარდა თანამედროვე გამოთვლითი ტექნიკის შექმნასთან დაკავშირებით.

კ. ხშირად განიხილება როგორც დისკრეტული მათემატიკის ნაწილი. კ-ის მეთოდები ფართოდ გამოიყენება ალბათობის თეორიაში, ალგებრაში, კომბინატორულ გეომეტრიასა და მათ. სხვა დარგებში, ინფორმატიკაში, სტატისტიკურ ფიზიკაში, ქიმიაში, გენეტიკაში, ევოლუციის თეორიაში, ეკონომეტრიკაში და ა. შ. არსებობს კომბინატორული სიდიდეებისა და კ-ის მეთოდების განზოგადებები უწყვეტი და მრავალგანზომილებიანი სიმრავლეებისთვის და სხვ.

საქართველოში კ-ს იკვლევენ თსუ-ის ი. ვეკუას სახ. გამოყენებითი მათემატიკის ინსტიტუტსა და სტუ-ის კიბერნეტიკის ინსტიტუტში. აღსანიშნავია კვლევები კომბინატორულ გეომეტრიაში სასრულგანზომილებიანი ევკლიდური სივრცის ამოზნექილი სხეულებისა და დისკრეტული წერტილოვანი სისტემების შესახებ (ა. ხარაზიშვილი, გ. ნიჟარაძე, თ. საჟენიუკი, ე. ბალაძე, ტ. ჭაბუკიანი), სიმრავლეთა უსასრულო კ-ში (ა. ხარაზიშვილი, ა. ყიფიანი). საქართველოში კ-ის საფუძვლებს შეისწავლიან საბაზო განათლების ეტაპზე, ასევე უნ-ტებში, მ. შ. ქართველი ავტორების მიერ შედგენილი სახელმძღვანელოებით.

ლიტ.: გოგიშვილი გ., ვეფხვაძე თ., მებონია ი., ქურჩიშვილი ლ., გავიმეოროთ მათემატიკა, ნაწ. I, თბ., 2008; Виленкин Н. Я., Популярная комбинаторика, М., 1975; Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; Харазишвили А. Б., Элементы комбинаторной теории бесконечных множеств, Тб., 1981; მისივე, Введение в комбинаторную геометрию, Тб., 1983; Riordan J., An Introduction to Combinatorial Analysis, N.Y, 1958.

ა. ხარაზიშვილი