ეს სტატია ყურადღებას გაამახვილებს მათემატიკის სპეციალურ განყოფილებაზე, რომელსაც ეწოდება კომბინატორიკა. ფორმულები, წესები, პრობლემის გადაჭრის მაგალითები - ეს ყველაფერი შეგიძლიათ ნახოთ აქ სტატიის ბოლომდე წაკითხვით.
მაშ, რა არის ეს განყოფილება? კომბინატორიკა ეხება ნებისმიერი ობიექტის დათვლის საკითხს. მაგრამ ამ შემთხვევაში საგნები არ არის ქლიავი, მსხალი ან ვაშლი, არამედ რაღაც სხვა. კომბინატორიკა გვეხმარება მოვლენის ალბათობის პოვნაში. მაგალითად, ბანქოს თამაშისას, რა არის იმის ალბათობა, რომ მოწინააღმდეგეს ჰქონდეს კოზირი? ან ასეთი მაგალითი - რა არის იმის ალბათობა, რომ ოცი ბურთისგან შემდგარი ჩანთიდან ზუსტად თეთრი მიიღებთ? სწორედ ამ ტიპის ამოცანებისთვის უნდა ვიცოდეთ მათემატიკის ამ განყოფილების საფუძვლები მაინც.
კომბინატორიული კონფიგურაციები
კომბინატორიკის ძირითადი ცნებებისა და ფორმულების საკითხის გათვალისწინებით, ჩვენ არ შეგვიძლია ყურადღება არ მივაქციოთ კომბინატორულ კონფიგურაციებს. ისინი გამოიყენება არა მხოლოდ ფორმულირებისთვის, არამედ სხვადასხვა კომბინატორული ამოცანების გადასაჭრელად. ასეთი მოდელების მაგალითებია:
- ადგილმდებარეობა;
- პერმუტაცია;
- კომბინაცია;
- ნომრის შემადგენლობა;
- გაყოფილი ნომერი.
პირველ სამზე უფრო დეტალურად მოგვიანებით ვისაუბრებთ, მაგრამ ამ განყოფილებაში ყურადღებას გავამახვილებთ კომპოზიციასა და გაყოფაზე. როდესაც ისინი საუბრობენ გარკვეული რიცხვის შედგენილობაზე (ვთქვათ, a), ისინი გულისხმობენ a რიცხვის წარმოდგენას, როგორც ზოგიერთი დადებითი რიცხვის მოწესრიგებულ ჯამს. და გაყოფა არის დაუგეგმავი თანხა.
სექციები
სანამ უშუალოდ კომბინატორიკის ფორმულებზე და ამოცანების განხილვაზე გადავალთ, ყურადღება უნდა მიაქციოთ იმას, რომ კომბინატორიკას, ისევე როგორც მათემატიკის სხვა განყოფილებებს, აქვს თავისი ქვეგანყოფილებები. ეს მოიცავს:
- აღრიცხვა;
- სტრუქტურული;
- ექსტრემალური;
- რემზის თეორია;
- ალბათური;
- ტოპოლოგიური;
- უსასრულო.
პირველ შემთხვევაში, საუბარია რიცხობრივ კომბინატორიკაზე, პრობლემები განიხილავს სხვადასხვა კონფიგურაციის ჩამოთვლას ან დათვლას, რომლებიც წარმოიქმნება სიმრავლეების ელემენტებით. როგორც წესი, ამ კომპლექტებზე დაწესებულია გარკვეული შეზღუდვები (განსხვავებულობა, განსხვავებულობა, გამეორების შესაძლებლობა და ა.შ.). და ამ კონფიგურაციების რაოდენობა გამოითვლება შეკრების ან გამრავლების წესის გამოყენებით, რაზეც ცოტა მოგვიანებით ვისაუბრებთ. სტრუქტურული კომბინატორიკა მოიცავს გრაფიკების და მატროიდების თეორიებს. ექსტრემალური კომბინატორიკის ამოცანის მაგალითია რა არის გრაფიკის უდიდესი განზომილება, რომელიც აკმაყოფილებს შემდეგ თვისებებს… მეოთხე აბზაცში აღვნიშნეთ რამსის თეორია, რომელიც სწავლობს რეგულარული სტრუქტურების არსებობას შემთხვევით კონფიგურაციებში. სავარაუდოკომბინატორიკას შეუძლია უპასუხოს კითხვას - რა არის ალბათობა იმისა, რომ მოცემულ სიმრავლეს ჰქონდეს გარკვეული თვისება. როგორც მიხვდით, ტოპოლოგიური კომბინატორიკა იყენებს მეთოდებს ტოპოლოგიაში. და ბოლოს, მეშვიდე პუნქტი - უსასრულო კომბინატორიკა სწავლობს კომბინატორიკის მეთოდების გამოყენებას უსასრულო სიმრავლეებზე.
დამატების წესი
კომბინატორიკის ფორმულებს შორის საკმაოდ მარტივია, რომლებსაც დიდი ხანია ვიცნობთ. ამის მაგალითია ჯამის წესი. დავუშვათ, რომ გვეძლევა ორი მოქმედება (C და E), თუ ისინი ურთიერთგამომრიცხავია, მოქმედება C შეიძლება შესრულდეს რამდენიმე გზით (მაგალითად, a), ხოლო მოქმედება E შეიძლება გაკეთდეს b-გზებით, მაშინ რომელიმე მათგანი (C) ან E) შეიძლება გაკეთდეს a + b გზებით.
თეორიულად ამის გაგება საკმაოდ რთულია, შევეცდებით მარტივი მაგალითით გადმოგცეთ მთელი აზრი. ავიღოთ მოსწავლეთა საშუალო რაოდენობა ერთ კლასში – ვთქვათ არის ოცდახუთი. მათ შორის თხუთმეტი გოგონა და ათი ბიჭია. კლასში ყოველდღიურად ინიშნება ერთი დამსწრე. რამდენი გზა არსებობს დღეს კლასის დამსწრის დანიშვნისთვის? პრობლემის გადაწყვეტა საკმაოდ მარტივია, ჩვენ მივმართავთ დამატების წესს. დავალების ტექსტში არ არის ნათქვამი, რომ მორიგეობა მხოლოდ ბიჭებს ან მხოლოდ გოგოებს შეუძლიათ. აქედან გამომდინარე, ეს შეიძლება იყოს თხუთმეტი გოგოდან რომელიმე ან ათი ბიჭიდან რომელიმე. ჯამის წესის გამოყენებით მივიღებთ საკმაოდ მარტივ მაგალითს, რომელსაც დაწყებითი სკოლის მოსწავლე ადვილად უმკლავდება: 15 + 10. გამოთვლის შემდეგ მივიღებთ პასუხს: ოცდახუთი. ანუ მხოლოდ ოცდახუთი გზა არსებობსდანიშნეთ მორიგე კლასი დღეს.
გამრავლების წესი
გამრავლების წესიც კომბინატორიკის ძირითად ფორმულებს მიეკუთვნება. დავიწყოთ თეორიით. დავუშვათ, რომ რამდენიმე მოქმედების შესრულება გვჭირდება (a): პირველი მოქმედება შესრულებულია 1 გზით, მეორე - 2 გზით, მესამე - 3 გზით და ასე გრძელდება ბოლო a-მოქმედების შესრულებამდე sa გზებით. მაშინ ყველა ეს მოქმედება (რომლებიც გვაქვს სულ) შეიძლება შესრულდეს N გზით. როგორ გამოვთვალოთ უცნობი N? ამაში დაგვეხმარება ფორმულა: N \u003d c1c2c3…ca.
კიდევ ერთხელ, თეორიულად არაფერია ნათელი, გადავიდეთ გამრავლების წესის გამოყენების მარტივ მაგალითზე. ავიღოთ იგივე ოცდახუთი კაციანი კლასი, რომელშიც თხუთმეტი გოგონა და ათი ბიჭი სწავლობს. მხოლოდ ამჯერად უნდა ავირჩიოთ ორი დამსწრე. ისინი შეიძლება იყვნენ მხოლოდ ბიჭები ან გოგოები, ან ბიჭი გოგოსთან ერთად. ჩვენ მივმართავთ პრობლემის ელემენტარულ გადაწყვეტას. ჩვენ ვირჩევთ პირველ დამსწრეს, როგორც ბოლო აბზაცში გადავწყვიტეთ, ვიღებთ ოცდახუთ შესაძლო ვარიანტს. მეორე მორიგე შეიძლება იყოს ნებისმიერი დარჩენილი პირი. ოცდახუთი სტუდენტი გვყავდა, ერთი ავარჩიეთ, რაც იმას ნიშნავს, რომ დარჩენილი ოცდაოთხი ადამიანიდან რომელიმე შეიძლება იყოს მეორე მორიგე. საბოლოოდ, ჩვენ ვიყენებთ გამრავლების წესს და აღმოვაჩენთ, რომ ორი დამსწრე შეიძლება აირჩიონ ექვსასი გზით. ეს რიცხვი მივიღეთ ოცდახუთზე და ოცდაოთხზე გამრავლებით.
გაცვლა
ახლა განვიხილავთ კომბინატორიკის კიდევ ერთ ფორმულას. სტატიის ამ ნაწილში ჩვენმოდით ვისაუბროთ პერმუტაციებზე. დაუყოვნებლივ განიხილეთ პრობლემა მაგალითით. ავიღოთ ბილიარდის ბურთები, გვაქვს მათი n-ე რიცხვი. უნდა გამოვთვალოთ: რამდენი ვარიანტია მათი ზედიზედ დასალაგებლად, ანუ შეკვეთილი ნაკრების შესაქმნელად.
დავიწყოთ, თუ ბურთები არ გვაქვს, მაშინ გვაქვს ნულოვანი განლაგების ვარიანტებიც. და თუ გვაქვს ერთი ბურთი, მაშინ განლაგებაც იგივეა (მათემატიკურად, ეს შეიძლება დაიწეროს შემდეგნაირად: Р1=1). ორი ბურთი შეიძლება განლაგდეს ორი განსხვავებული გზით: 1, 2 და 2, 1. მაშასადამე, Р2=2. სამი ბურთი შეიძლება განლაგდეს ექვსნაირად (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. და თუ არის არა სამი ასეთი ბურთი, არამედ ათი თუ თხუთმეტი? ყველა შესაძლო ვარიანტის ჩამოთვლა ძალიან გრძელია, მაშინ კომბინატორიკა გვეხმარება. პერმუტაციის ფორმულა დაგვეხმარება ვიპოვოთ პასუხი ჩვენს კითხვაზე. Pn=nP(n-1). თუ შევეცდებით ფორმულის გამარტივებას, მივიღებთ: Pn=n (n - 1) … 21. და ეს არის პირველი ნატურალური რიცხვების ნამრავლი. ასეთ რიცხვს ეწოდება ფაქტორიალი და აღინიშნება როგორც n!
მოდით განვიხილოთ პრობლემა. ლიდერი ყოველ დილით აყალიბებს თავის რაზმს რიგში (ოცი კაცი). რაზმში სამი საუკეთესო მეგობარია - კოსტია, საშა და ლეშა. რა არის იმის ალბათობა, რომ ისინი ერთმანეთის გვერდით იქნებიან? კითხვაზე პასუხის მოსაძებნად, თქვენ უნდა გაყოთ "კარგი" შედეგის ალბათობა შედეგების საერთო რაოდენობაზე. პერმუტაციების საერთო რაოდენობა არის 20!=2,5 კვინტილიონი. როგორ გამოვთვალოთ "კარგი" შედეგების რაოდენობა? დავუშვათ, რომ კოსტია, საშა და ლეშა ერთი სუპერმენია. Შემდეგ ჩვენჩვენ მხოლოდ თვრამეტი საგანი გვაქვს. პერმუტაციების რაოდენობა ამ შემთხვევაში არის 18=6,5 კვადრილონი. ამ ყველაფრით კოსტიას, საშას და ლეშას შეუძლიათ თვითნებურად გადაადგილდნენ ერთმანეთში თავიანთ განუყოფელ სამეულში და ეს კიდევ 3!=6 ვარიანტი. ასე რომ, სულ გვაქვს 18 "კარგი" თანავარსკვლავედი!3! ჩვენ უბრალოდ უნდა ვიპოვოთ სასურველი ალბათობა: (18!3!) / 20! რაც არის დაახლოებით 0,016. თუ გადაიყვანება პროცენტში, აღმოჩნდება მხოლოდ 1,6%.
განთავსება
ახლა განვიხილავთ კომბინატორიკის კიდევ ერთ ძალიან მნიშვნელოვან და აუცილებელ ფორმულას. განსახლება ჩვენი შემდეგი საკითხია, რომელიც გირჩევთ განიხილოთ სტატიის ამ ნაწილში. ჩვენ უფრო გავრთულდებით. დავუშვათ, რომ ჩვენ გვინდა განვიხილოთ შესაძლო პერმუტაციები, მხოლოდ არა მთელი სიმრავლიდან (n), არამედ უფრო მცირედან (m). ანუ განვიხილავთ n ელემენტის პერმუტაციას m-ით.
კომბინატორიკის ძირითადი ფორმულები არ უნდა იყოს მხოლოდ დამახსოვრება, არამედ გაგება. მიუხედავად იმისა, რომ ისინი უფრო რთულდებიან, რადგან ჩვენ გვაქვს არა ერთი პარამეტრი, არამედ ორი. დავუშვათ, რომ m \u003d 1, შემდეგ A \u003d 1, m \u003d 2, შემდეგ A \u003d n(n - 1). თუ კიდევ უფრო გავამარტივებთ ფორმულას და გადავიტანთ აღნიშვნაზე ფაქტორების გამოყენებით, მივიღებთ საკმაოდ ლაკონურ ფორმულას: A \u003d n! / (n - m)!
კომბინაცია
ჩვენ განვიხილეთ კომბინატორიკის თითქმის ყველა ძირითადი ფორმულა მაგალითებით. ახლა გადავიდეთ კომბინატორიკის ძირითადი კურსის განხილვის დასკვნით ეტაპზე - კომბინაციის გაცნობა. ახლა ჩვენ ავირჩევთ m ელემენტებს იმ n-დან, რაც გვაქვს, ხოლო ყველა მათგანს შევარჩევთ ყველა შესაძლო გზით. მაშინ რით განსხვავდება ეს განსახლებისგან? Ჩვენ არგანიხილეთ წესრიგი. ეს შეუკვეთავი ნაკრები იქნება კომბინაცია.
დაუყოვნებლივ შეიტანეთ აღნიშვნა: C. ვიღებთ m ბურთების განლაგებას n-დან. ჩვენ ვწყვეტთ წესრიგს და ვიღებთ განმეორებით კომბინაციებს. კომბინაციების რაოდენობის მისაღებად საჭიროა განლაგების რაოდენობა გავყოთ m-ზე! (მ ფაქტორული). ანუ C \u003d A / m! ამრიგად, n ბურთიდან ასარჩევად რამდენიმე გზა არსებობს, დაახლოებით ტოლია რამდენის ასარჩევად თითქმის ყველაფერი. ამის ლოგიკური გამოთქმა არსებობს: პატარას არჩევა იგივეა, რაც თითქმის ყველაფრის გადაყრა. ასევე მნიშვნელოვანია აღვნიშნოთ, რომ კომბინაციების მაქსიმალური რაოდენობა შეიძლება მიღწეული იქნას ნივთების ნახევრის არჩევისას.
როგორ ავირჩიოთ ფორმულა პრობლემის გადასაჭრელად?
ჩვენ დეტალურად განვიხილეთ კომბინატორიკის ძირითადი ფორმულები: განლაგება, პერმუტაცია და კომბინაცია. ახლა ჩვენი ამოცანაა ხელი შევუწყოთ კომბინატორიკაში პრობლემის გადასაჭრელად საჭირო ფორმულის არჩევას. შეგიძლიათ გამოიყენოთ შემდეგი საკმაოდ მარტივი სქემა:
- ჰკითხეთ საკუთარ თავს: არის თუ არა გათვალისწინებული ელემენტების თანმიმდევრობა პრობლემის ტექსტში?
- თუ პასუხი არის არა, გამოიყენეთ კომბინაციის ფორმულა (C=n! / (m!(n - m)!)).
- თუ პასუხი არის არა, მაშინ თქვენ უნდა უპასუხოთ კიდევ ერთ კითხვას: შედის თუ არა კომბინაციაში ყველა ელემენტი?
- თუ პასუხი არის დიახ, გამოიყენეთ პერმუტაციის ფორმულა (P=n!).
- თუ პასუხი არის არა, გამოიყენეთ განაწილების ფორმულა (A=n! / (n - m)!).
მაგალითი
ჩვენ განვიხილეთ კომბინატორიკის ელემენტები, ფორმულები და სხვა საკითხები. ახლა გადავიდეთრეალური პრობლემის გათვალისწინებით. წარმოიდგინეთ, რომ წინ გაქვთ კივი, ფორთოხალი და ბანანი.
კითხვა პირველი: რამდენი გზით შეიძლება მათი გადაწყობა? ამისათვის ჩვენ ვიყენებთ პერმუტაციის ფორმულას: P=3!=6 გზა.
კითხვა მეორე: რამდენი გზით შეიძლება ერთი ხილის არჩევა? ეს აშკარაა, ჩვენ გვაქვს მხოლოდ სამი ვარიანტი - აირჩიეთ კივი, ფორთოხალი ან ბანანი, მაგრამ ჩვენ ვიყენებთ კომბინაციის ფორმულას: C \u003d 3! / (2!1!)=3.
კითხვა მესამე: რამდენი გზით შეიძლება ორი ხილის არჩევა? რა ვარიანტები გვაქვს? კივი და ფორთოხალი; კივი და ბანანი; ფორთოხალი და ბანანი. ეს არის სამი ვარიანტი, მაგრამ ამის შემოწმება მარტივია კომბინაციის ფორმულის გამოყენებით: C \u003d 3! / (1!2!)=3
კითხვა მეოთხე: რამდენი გზით შეიძლება სამი ხილის არჩევა? როგორც ხედავთ, სამი ხილის არჩევის მხოლოდ ერთი გზა არსებობს: აიღეთ კივი, ფორთოხალი და ბანანი. C=3! / (0!3!)=1.
კითხვა მეხუთე: რამდენი გზით შეგიძლიათ აირჩიოთ მინიმუმ ერთი ხილი? ეს მდგომარეობა გულისხმობს, რომ შეგვიძლია მივიღოთ ერთი, ორი ან სამივე ხილი. მაშასადამე, ვამატებთ C1 + C2 + C3=3 + 3 + 1=7. ანუ გვაქვს შვიდი გზა, რომ ავიღოთ სუფრიდან მინიმუმ ერთი ნაჭერი ხილი.
