შესაძლო კომბინაციები. კომბინატორიკის ელემენტები
კომბინაცია არის სასრული სიმრავლის ელემენტების შეურიგებელი შერჩევა ფიქსირებული რიცხვით და ელემენტების გამეორების გარეშე. სხვადასხვა კომბინაციები უნდა განსხვავდებოდეს მინიმუმ ერთ ელემენტში და ელემენტების თანმიმდევრობას არ აქვს მნიშვნელობა. მაგალითად, ლათინური ასოების ყველა ხმოვანთა სიმრავლიდან (AEIOU), შეგიძლიათ გააკეთოთ 3 ასოს 10 განსხვავებული კომბინაცია, რომლებიც ჩამოაყალიბებენ შემდეგ უწესრიგო სამეულებს:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
საინტერესოა აღინიშნოს, რომ იგივე ხუთი ასოდან ასევე შეგიძლიათ მიიღოთ 10 განსხვავებული კომბინაცია, თუ მათ ერთდროულად 2 ასოს დააკავშირებთ და შემდეგ შეუკვეთებელ წყვილებს შექმნით:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
თუმცა, თუ ერთსა და იმავე ხმოვან ლათინურ ასოებს 4-ით დააკავშირებთ, მიიღებთ მხოლოდ შემდეგ 5 სხვადასხვა კომბინაციას:
AEIO, AEIU, AIOU, EIOU, AEOU.
ზოგადად, m ელემენტების n სხვადასხვა ელემენტის კომბინაციების რაოდენობის აღსანიშნავად გამოიყენება შემდეგი ფუნქციონალური, ინდექსის ან ვექტორული (Appel) სიმბოლიზმი:
მიუხედავად აღნიშვნის ფორმისა, m ელემენტებით n ელემენტის კომბინაციების რაოდენობა შეიძლება განისაზღვროს შემდეგი მრავლობითი და ფაქტორიალური ფორმულების გამოყენებით:
ადვილია იმის შემოწმება, რომ ამ ფორმულების გამოყენებით გამოთვლების შედეგი ემთხვევა ზემოთ განხილული მაგალითის შედეგებს ლათინური ასოებით ხმოვანთა კომბინაციით. კერძოდ, n=5 და m=3 შემთხვევაში, გამოთვლები ამ ფორმულების გამოყენებით მისცემს შემდეგ შედეგს:
ზოგად შემთხვევაში, კომბინაციების რაოდენობის ფორმულებს აქვთ კომბინაციური მნიშვნელობა და მოქმედებს n-ისა და m-ის ნებისმიერი მთელი რიცხვისთვის, ისეთი, რომ n > m > 0. თუ m > n და m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
გარდა ამისა, სასარგებლოა დაიმახსოვროთ კომბინაციების შემდეგი შემზღუდველი რიცხვები, რომელთა შემოწმებაც მარტივად შეიძლება მულტიპლიკაციურ და ფაქტორულ ფორმულებში პირდაპირი ჩანაცვლებით:
ასევე უნდა აღინიშნოს, რომ გამრავლების ფორმულა ძალაში რჩება მაშინაც კი, როდესაც n არის რეალური რიცხვი, სანამ m მაინც მთელი მნიშვნელობაა. თუმცა, მაშინ მისი გამოყენებით გაანგარიშების შედეგი, ფორმალური მოქმედების შენარჩუნებისას, კარგავს თავის კომბინატორულ მნიშვნელობას.
კომბინაციების იდენტიფიკაცია
მრავლობითი და ფაქტორული ფორმულების პრაქტიკული გამოყენება n და m თვითნებური მნიშვნელობების კომბინაციების რაოდენობის დასადგენად, მცირე პროდუქტიულობაა მათი მრიცხველისა და მნიშვნელის ფაქტორული პროდუქტების ექსპონენციალური ზრდის გამო. n და m-ის შედარებით მცირე მნიშვნელობებისთვისაც კი, ეს პროდუქტები ხშირად აღემატება მთელი რიცხვების წარმოდგენის შესაძლებლობებს თანამედროვე გამოთვლით და პროგრამულ სისტემებში. უფრო მეტიც, მათი მნიშვნელობები მნიშვნელოვნად აღემატება კომბინაციების რაოდენობის მიღებულ მნიშვნელობას, რომელიც შეიძლება იყოს შედარებით მცირე. მაგალითად, n=10 მ=8 ელემენტის კომბინაციების რაოდენობა არის მხოლოდ 45. თუმცა, ამ მნიშვნელობის ფაქტორული ფორმულის გამოყენებით, ჯერ უნდა გამოთვალოთ 10-ის გაცილებით დიდი მნიშვნელობები! მრიცხველში და 8! მნიშვნელში:
დიდი რაოდენობით დამუშავებისთვის შრომატევადი ოპერაციების აღმოსაფხვრელად, კომბინაციების რაოდენობის დასადგენად, შეგიძლიათ გამოიყენოთ სხვადასხვა განმეორებითი ურთიერთობები, რომლებიც პირდაპირ გამომდინარეობს მრავლობითი და ფაქტორიალური ფორმულებიდან. კერძოდ, გამრავლების ფორმულიდან გამომდინარეობს შემდეგი რეციდივის მიმართება, რომელიც საშუალებას გვაძლევს ავიღოთ მისი ინდექსების თანაფარდობა კომბინაციების რაოდენობის ნიშანს მიღმა:
დაბოლოს, სუბსკრიპტის მუდმივი შენარჩუნება უზრუნველყოფს შემდეგ განმეორებადობას, რომელიც ადვილად მიიღება კომბინაციების რაოდენობის ფაქტორული ფორმულიდან:
ელემენტარული გარდაქმნების შემდეგ, სამი შედეგიანი განმეორებითი ურთიერთობა შეიძლება წარმოდგენილი იყოს შემდეგი ფორმებით:
თუ ახლა დავამატებთ პირველი 2 ფორმულის მარცხენა და მარჯვენა მხარეს და შევამცირებთ შედეგს n-ით, მივიღებთ მნიშვნელოვან განმეორებით მიმართებას, რომელსაც ეწოდება კომბინირებული რიცხვების დამატების იდენტურობა:
შეკრების იდენტურობა უზრუნველყოფს ძირითადი განმეორების წესს n და m დიდი მნიშვნელობების კომბინაციების რაოდენობის ეფექტურად დასადგენად, რადგან ის საშუალებას აძლევს გამრავლების ოპერაციებს ფაქტორულ პროდუქტებში შეიცვალოს უფრო მარტივი შეკრების ოპერაციებით და კომბინაციების უფრო მცირე რაოდენობით. კერძოდ, მიმატების იდენტურობის გამოყენებით, ახლა ადვილია განვსაზღვროთ n=10 კომბინაციების რაოდენობა m=8 ელემენტით, რაც ზემოთ იყო განხილული, განმეორებადი გარდაქმნების შემდეგი თანმიმდევრობის შესრულებით:
გარდა ამისა, სასრული ჯამების გამოსათვლელად რამდენიმე სასარგებლო ურთიერთობა შეიძლება გამოვიდეს მიმატების იდენტურობიდან, კერძოდ, სუბსკრიპტის მიერ შეჯამების ფორმულიდან, რომელსაც აქვს შემდეგი ფორმა:
ეს მიმართება მიიღება, თუ დანამატის იდენტურობაში ჩვენ გავაფართოვებთ განმეორებას ტერმინის გასწვრივ ყველაზე დიდი ზემოწერით, ხოლო მისი ქვესკრიპტი მეტია 0-ზე. შემდეგი რიცხვითი მაგალითი ასახავს განმეორებადი გარდაქმნების ამ პროცესს:
აბსკრიპტის შეჯამების ფორმულა ხშირად გამოიყენება ნატურალური რიცხვების ძალების ჯამის გამოსათვლელად. კერძოდ, m=1 დაშვებით, ამ ფორმულის გამოყენებით ადვილია ნატურალური რიგის პირველი n რიცხვების ჯამის პოვნა:
შემაჯამებელი ფორმულის კიდევ ერთი სასარგებლო ვერსია შეიძლება მიღებულ იქნას მიმატების იდენტურობის განმეორების გაფართოებით ტერმინის გასწვრივ უმცირესი ზემოწერით. შემდეგი რიცხვითი მაგალითი ასახავს განმეორებადი გარდაქმნების ამ ვერსიას:
ზოგადად, ასეთი გარდაქმნების შედეგად, მიიღება კომბინაციების რიცხვების ჯამი, რომელთა ორივე მაჩვენებელი ერთით განსხვავდება მეზობელი ტერმინებისგან, ხოლო ინდექსებში განსხვავება რჩება მუდმივი (განხილულ მაგალითში ეს არის ასევე ერთის ტოლი). ამრიგად, ჩვენ ვიღებთ შეჯამების შემდეგ ფორმულას კომბინირებული რიცხვების ორივე ინდექსისთვის:
გარდა ზემოთ განხილული განმეორებითი ურთიერთობებისა და შეჯამების ფორმულებისა, კომბინაციურ ანალიზში მიღებულ იქნა მრავალი სხვა სასარგებლო იდენტობა კომბინირებული რიცხვებისთვის. მათ შორის ყველაზე მნიშვნელოვანია სიმეტრიის იდენტურობა, რომელიც ასე გამოიყურება:
სიმეტრიის იდენტურობის მართებულობა შეიძლება დადასტურდეს შემდეგ მაგალითში 5 ელემენტის კომბინაციების რიცხვების შედარებით 2-ით და (5 2) = 3-ით:
სიმეტრიის იდენტობას აქვს აშკარა კომბინატორული მნიშვნელობა, ვინაიდან, n ელემენტიდან m ელემენტების არჩევის ვარიანტების რაოდენობის განსაზღვრით, იგი ერთდროულად ადგენს კომბინაციების რაოდენობას დარჩენილი (ნმ) არჩეული ელემენტებიდან. მითითებული სიმეტრია დაუყოვნებლივ მიიღება m-ით (ნმ) შეცვლით კომბინაციების რაოდენობის ფაქტორულ ფორმულაში:
რიცხვები და კომბინირებული იდენტობები ფართოდ გამოიყენება თანამედროვე გამოთვლითი მათემატიკის სხვადასხვა სფეროში. თუმცა, მათი ყველაზე პოპულარული აპლიკაციები დაკავშირებულია ნიუტონის ბინომინთან და პასკალის სამკუთხედთან.
ბინომის თეორემა
სხვადასხვა მათემატიკური გარდაქმნებისა და გამოთვლების შესასრულებლად მნიშვნელოვანია ალგებრული ბინომის (ბინომის) ნებისმიერი ბუნებრივი სიძლიერის წარმოდგენა მრავალწევრის სახით. მცირე სიმძლავრეებისთვის სასურველი პოლინომი ადვილად შეიძლება მიღებულ იქნას ბინომების პირდაპირ გამრავლებით. კერძოდ, ელემენტარული მათემატიკის კურსიდან კარგად არის ცნობილი ორი წევრის ჯამის კვადრატისა და კუბის შემდეგი ფორმულები:
ზოგად შემთხვევაში, ბინომის თვითნებური n ხარისხისთვის, საჭირო წარმოდგენა მრავალწევრის სახით მოცემულია ნიუტონის ბინომის თეორემით, რომელიც აცხადებს შემდეგ ტოლობას ჭეშმარიტად:
ამ თანასწორობას ჩვეულებრივ უწოდებენ ნიუტონის ბინომალს. მის მარჯვენა მხარეს მყოფი მრავალწევრი წარმოიქმნება მარცხენა მხარის ბინომის n ტერმინების ნამრავლების ჯამით, ხოლო მათ წინ კოეფიციენტებს ბინომიური ეწოდება და უდრის ინდექსებთან კომბინაციების რაოდენობას, რომელიც მათი უფლებამოსილებიდან არის მიღებული. ნიუტონის ბინომიალური ფორმულის განსაკუთრებული პოპულარობის გათვალისწინებით კომბინატორულ ანალიზში, ტერმინები ბინომიალური კოეფიციენტი და კომბინაციების რაოდენობა ზოგადად სინონიმად ითვლება.
ცხადია, კვადრატული და კუბური ჯამის ფორმულები არის ბინომიალური თეორემის სპეციალური შემთხვევები n=2 და n=3 შესაბამისად. უფრო მაღალი ხარისხების დასამუშავებლად (n>3) უნდა იქნას გამოყენებული ნიუტონის ბინომიალური ფორმულა. მისი გამოყენება მეოთხე ხარისხის ბინომისთვის (n=4) ნაჩვენებია შემდეგი მაგალითით:
უნდა აღინიშნოს, რომ ბინომალური ფორმულა ნიუტონამდეც იყო ცნობილი არაბული აღმოსავლეთისა და დასავლეთ ევროპის შუა საუკუნეების მათემატიკოსებისთვის. ამიტომ, მისი საყოველთაოდ მიღებული სახელი ისტორიულად არ არის სამართლიანი. ნიუტონის დამსახურებაა ის, რომ მან განაზოგადა ეს ფორმულა თვითნებური რეალური მაჩვენებლის r შემთხვევაში, რომელსაც შეუძლია მიიღოს ნებისმიერი დადებითი ან უარყოფითი რაციონალური და ირაციონალური მნიშვნელობები. ზოგად შემთხვევაში, ნიუტონის ბინომის ასეთ ფორმულას აქვს უსასრულო ჯამი მარჯვენა მხარეს და ჩვეულებრივ იწერება შემდეგნაირად:
მაგალითად, r=1/2 მაჩვენებლის დადებითი წილადური მნიშვნელობით, ბინომალური კოეფიციენტების მნიშვნელობების გათვალისწინებით, მიიღება შემდეგი გაფართოება:
ზოგად შემთხვევაში, ნიუტონის ბინომიალური ფორმულა ნებისმიერი მაჩვენებლისთვის არის მაკლარინის ფორმულის სპეციალური ვერსია, რომელიც იძლევა თვითნებური ფუნქციის გაფართოებას სიმძლავრის სერიაში. ნიუტონმა აჩვენა, რომ |z|-ისთვის< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. თუ ახლა დავაყენებთ Z=X/Y და გავამრავლებთ მარცხენა და მარჯვენა გვერდებს Yn-ზე, მივიღებთ ზემოთ განხილული ნიუტონის ბინომიალური ფორმულის ვერსიას.
მიუხედავად უნივერსალურობისა, ბინომის თეორემა ინარჩუნებს კომბინატორულ მნიშვნელობას მხოლოდ ბინომის არაუარყოფითი მთელი რიცხვების ხარისხებისთვის. ამ შემთხვევაში, ის შეიძლება გამოყენებულ იქნას ბინომალური კოეფიციენტებისთვის რამდენიმე სასარგებლო იდენტობის დასამტკიცებლად. კერძოდ, ზემოთ განხილული იქნა კომბინაციების რიცხვების შეჯამების ფორმულები სუბსკრიპტის მიხედვით და ორივე ინდექსის მიხედვით. გამოტოვებული ზედნაწერის შეჯამების იდენტურობა ადვილად შეიძლება მივიღოთ ნიუტონის ბინომიალური ფორმულიდან მასში X = Y = 1 ან Z = 1 ჩასმით:
კიდევ ერთი სასარგებლო იდენტობა ადგენს ორობითი კოეფიციენტების ჯამების ტოლობას ლუწი და კენტი რიცხვებით. ის მაშინვე მიიღება ნიუტონის ბინომიალური ფორმულიდან, თუ X = 1 და Y = 1 ან Z = 1:
დაბოლოს, ორივე განხილული იდენტობიდან ვიღებთ ბინომური კოეფიციენტების ჯამის იდენტურობას მხოლოდ ლუწი ან მხოლოდ კენტი რიცხვებით:
განხილული იდენტობებისა და კომბინაციების რაოდენობის ნიშნის ქვემოდან ინდექსების ამოღების განმეორებითი წესიდან გამომდინარე, შეიძლება მივიღოთ არაერთი საინტერესო ურთიერთობა. მაგალითად, თუ ზემოწერის შეჯამების ფორმულაში ჩვენ ყველგან n-ს შევცვლით (n1)-ით და ამოვიღებთ ინდექსებს თითოეულ წევრში, მივიღებთ შემდეგ მიმართებას:
მსგავსი ტექნიკის გამოყენებით ლუწი და კენტი რიცხვებით ბინომიალური კოეფიციენტების ჯამის ფორმულაში, შესაძლებელია დაამტკიცოთ, მაგალითად, შემდეგი მიმართების მართებულობა:
კიდევ ერთი სასარგებლო იდენტობა საშუალებას გაძლევთ მარტივად გამოთვალოთ სიმეტრიულად განლაგებული ორობითი კოეფიციენტების ნამრავლების ჯამი n და k თვითნებური ხარისხის ორი ორობითი კუშის ფორმულის გამოყენებით:
ამ ფორმულის მართებულობა გამომდინარეობს კოეფიციენტების აუცილებელი თანასწორობიდან Z ცვლადის ნებისმიერი ხარისხის m-ისთვის შემდეგი იდენტური მიმართების მარცხენა და მარჯვენა მხარეს:
განსაკუთრებულ შემთხვევაში, როდესაც n=k=m, სიმეტრიის იდენტობის გათვალისწინებით, უფრო პოპულარული ფორმულა მიიღება ორობითი კოეფიციენტების კვადრატების ჯამისთვის:
ბინომიალური კოეფიციენტების მრავალი სხვა სასარგებლო იდენტობა გვხვდება კომბინატორული ანალიზის ვრცელ ლიტერატურაში. თუმცა, მათი ყველაზე ცნობილი პრაქტიკული გამოყენება დაკავშირებულია პასკალის სამკუთხედთან.
პასკალის სამკუთხედი
პასკალის არითმეტიკული სამკუთხედი ქმნის უსასრულო ციფრულ ცხრილს, რომელიც შედგება ბინომიალური კოეფიციენტებისგან. მისი ხაზები დალაგებულია ორობითი ძალების მიხედვით ზემოდან ქვემოდან. თითოეულ სტრიქონში ბინომალური კოეფიციენტები განლაგებულია შესაბამისი კომბინაციის რიცხვების ზედამხედველობის აღმავალი თანმიმდევრობით მარცხნიდან მარჯვნივ. პასკალის სამკუთხედი ჩვეულებრივ იწერება ტოლკუთხა ან მართკუთხა ფორმით.
უფრო ვიზუალური და გავრცელებულია ტოლკუთხედის ფორმატი, სადაც ბინომიალური კოეფიციენტები, ეტაპობრივად, ქმნიან უსასრულო ტოლფერდა სამკუთხედს. მის საწყის ფრაგმენტს მე-4 ხარისხამდე ბინომებისთვის (n=4) აქვს შემდეგი ფორმა:
ზოგადად, პასკალის ტოლფერდა სამკუთხედი იძლევა მოსახერხებელ გეომეტრიულ წესს ბინომალური კოეფიციენტების დასადგენად, რომელიც ეფუძნება შეკრების იდენტობებსა და რიცხვთა კომბინაციების სიმეტრიას. კერძოდ, მიმატების იდენტურობის მიხედვით, ნებისმიერი ბინომალური კოეფიციენტი არის წინა რიგის მასთან ყველაზე ახლოს მყოფი ორი კოეფიციენტის ჯამი. სიმეტრიის იდენტობის მიხედვით, პასკალის ტოლფერდა სამკუთხედი სიმეტრიულია ბისექტრის მიმართ. ამრიგად, მისი თითოეული ხაზი არის ბინომიალური კოეფიციენტების რიცხვითი პალინდრომი. მითითებული ალგებრული და გეომეტრიული მახასიათებლები საშუალებას გაძლევთ მარტივად გააფართოვოთ პასკალის ტოლფერდა სამკუთხედი და თანმიმდევრულად იპოვოთ თვითნებური ძალების ორობითი კოეფიციენტების მნიშვნელობები.
თუმცა, პასკალის სამკუთხედის სხვადასხვა თვისებების შესასწავლად უფრო მოსახერხებელია ფორმალურად უფრო მკაცრი მართკუთხა ფორმატის გამოყენება. ამ ფორმატში ის მითითებულია ორობითი კოეფიციენტების ქვედა სამკუთხა მატრიცით, სადაც ისინი ქმნიან უსასრულო მართკუთხა სამკუთხედს. პასკალის მართკუთხა სამკუთხედის საწყის ფრაგმენტს მე-9 ხარისხამდე ბინომებისთვის (n=9) აქვს შემდეგი ფორმა:
გეომეტრიულად ასეთი მართკუთხა ცხრილი მიიღება პასკალის ტოლფერდა სამკუთხედის ჰორიზონტალურად დეფორმირებით. შედეგად, პასკალის ტოლფერდა სამკუთხედის გვერდითი გვერდების პარალელურად რიცხვითი სერიები გადაიქცევა პასკალის მართკუთხა სამკუთხედის ვერტიკალებად და დიაგონალებად და ორივე სამკუთხედის ჰორიზონტალური ხაზები ემთხვევა. ამავდროულად, ბინომური კოეფიციენტების შეკრებისა და სიმეტრიის წესები ძალაში რჩება, თუმცა პასკალის მართკუთხა სამკუთხედი კარგავს ტოლფერდა კოეფიციენტისთვის დამახასიათებელ ვიზუალურ სიმეტრიას. ამის კომპენსაციის მიზნით, უფრო მოსახერხებელი ხდება პასკალის მართკუთხა სამკუთხედის ჰორიზონტალური, ვერტიკალებისა და დიაგონალების ორნომიალური კოეფიციენტების სხვადასხვა რიცხვითი თვისებების ოფიციალური ანალიზი.
პასკალის მართკუთხა სამკუთხედის ჰორიზონტალების ანალიზის დაწყებით, ადვილი შესამჩნევია, რომ ნებისმიერი მწკრივის ელემენტების ჯამი n ნომრით უდრის 2n-ს ზესკრიპტით ბინომების შეჯამების ფორმულის შესაბამისად. აქედან გამომდინარეობს, რომ ელემენტების ჯამი ნებისმიერი ჰორიზონტალური ხაზის ზემოთ n რიცხვით უდრის (2 n 1). ეს შედეგი საკმაოდ აშკარა ხდება, თუ თითოეული ჰორიზონტალური ელემენტების ჯამის მნიშვნელობა დაიწერება ორობით რიცხვთა სისტემაში. მაგალითად, n=4-ისთვის ეს დამატება შეიძლება ჩაიწეროს შემდეგნაირად:
აქ არის ჰორიზონტალური კიდევ რამდენიმე საინტერესო თვისება, რომლებიც ასევე დაკავშირებულია ორის სიმძლავრებთან. გამოდის, რომ თუ ჰორიზონტალური რიცხვი არის ორი ხარისხოვანი (n=2 k), მაშინ მისი ყველა შიდა ელემენტი (გარდა გარესა) ლუწი რიცხვებია. პირიქით, ჰორიზონტალური წრფის ყველა რიცხვი კენტი იქნება, თუ მისი რიცხვი ერთით ნაკლებია ორის ხარისხზე (n=2 k 1). ამ თვისებების მართებულობის შემოწმება შესაძლებელია შიდა ბინომური კოეფიციენტების პარიტეტის შემოწმებით, მაგალითად, ჰორიზონტალურ n=4 და n=3 ან n=8 და n=7.
მოდით, ახლა პასკალის მართკუთხა სამკუთხედის რიგის ნომერი იყოს მარტივი რიცხვი p. მაშინ მისი ყველა შიდა ორობითი კოეფიციენტი იყოფა p-ზე. ამ თვისების შემოწმება მარტივია მარტივი კონტურის რიცხვების მცირე მნიშვნელობებისთვის. მაგალითად, მეხუთე ჰორიზონტალური (5, 10 და 5) ყველა შიდა ბინომიალური კოეფიციენტი აშკარად იყოფა 5-ზე. ამ შედეგის დასამტკიცებლად ნებისმიერი მარტივი ჰორიზონტალური რიცხვისთვის p, თქვენ უნდა დაწეროთ გამრავლების ფორმულა მისი ბინომიური კოეფიციენტებისთვის შემდეგნაირად:
ვინაიდან p არის მარტივი რიცხვი და, მაშასადამე, არ იყოფა m!-ზე, ამ ფორმულის მრიცხველის დარჩენილი ფაქტორების ნამრავლი უნდა გაიყოს m!-ზე, რათა გარანტირებული იყოს ბინომიალური კოეფიციენტის მთელი რიცხვი. აქედან გამომდინარეობს, რომ კვადრატულ ფრჩხილებში შეფარდება არის ბუნებრივი რიცხვი N და სასურველი შედეგი აშკარა ხდება:
ამ შედეგის გამოყენებით შეგვიძლია დავადგინოთ, რომ პასკალის სამკუთხედის ყველა ჰორიზონტალური წრფის რიცხვები, რომელთა შიდა ელემენტები იყოფა მოცემულ მარტივ რიცხვზე p, არის p-ის ხარისხები, ანუ მათ აქვთ ფორმა n=p k. კერძოდ, თუ p=3, მაშინ მარტივი რიცხვი p ყოფს არა მხოლოდ მე-3 მწკრივის ყველა შიდა ელემენტს, როგორც ზემოთ ჩამოყალიბდა, არამედ, მაგალითად, მე-9 ჰორიზონტალურს (9, 36, 84 და 126). მეორეს მხრივ, პასკალის სამკუთხედში შეუძლებელია ჰორიზონტალური ხაზის პოვნა, რომლის შიდა ელემენტები იყოფა შედგენილ რიცხვზე. წინააღმდეგ შემთხვევაში, ასეთი ჰორიზონტალური ხაზის რიცხვი ერთდროულად უნდა იყოს კომპოზიტური რიცხვის ძირითადი გამყოფების სიძლიერე, რომლითაც იყოფა მისი ყველა შიდა ელემენტი, მაგრამ ეს შეუძლებელია გასაგები მიზეზების გამო.
განხილული მოსაზრებები საშუალებას გვაძლევს ჩამოვაყალიბოთ შემდეგი ზოგადი კრიტერიუმი პასკალის სამკუთხედის ჰორიზონტალური ელემენტების გასაყოფად. პასკალის სამკუთხედის ნებისმიერი ჰორიზონტალური ხაზის ყველა შიდა ელემენტის უდიდესი საერთო გამყოფი (GCD) რიცხვით n უდრის მარტივ რიცხვს p, თუ n=pk ან 1 ყველა სხვა შემთხვევაში:
GCD(Cmn) = ( ) ნებისმიერი 0-ისთვის< m < n .
ჰორიზონტალური ანალიზის დასასრულს, გასათვალისწინებელია კიდევ ერთი საინტერესო თვისება, რომელიც მათ ქმნიან ბინომიურ კოეფიციენტთა სერიას. თუ რომელიმე ჰორიზონტალური წრფის ბინომიალური კოეფიციენტები n ნომრით გამრავლდება 10 რიცხვის თანმიმდევრულ ძალებზე და შემდეგ ყველა ეს ნამრავლი დაემატება, შედეგი იქნება 11 n. ამ შედეგის ფორმალური დასაბუთება არის მნიშვნელობების ჩანაცვლება მნიშვნელობების X=10 და Y=1 (ან Z=1) ნიუტონის ბინომის ფორმულაში. შემდეგი რიცხვითი მაგალითი ასახავს ამ თვისების შესრულებას n=5-ისთვის:
პასკალის მართკუთხა სამკუთხედის ვერტიკალების თვისებების ანალიზი შეიძლება დაიწყოს მათი შემადგენელი ელემენტების ინდივიდუალური მახასიათებლების შესწავლით. ფორმალურად, ყოველი ვერტიკალური m იქმნება ბინომური კოეფიციენტების შემდეგი უსასრულო თანმიმდევრობით მუდმივი ზემოწერით (m) და ქვესკრიპტის ნაზრდით:
ცხადია, როცა m=0 მიიღება ერთთა მიმდევრობა, ხოლო როცა m=1 წარმოიქმნება ნატურალური რიცხვების სერია. როდესაც m=2 ვერტიკალი შედგება სამკუთხა რიცხვებისგან. თითოეული სამკუთხა რიცხვი შეიძლება გამოსახული იყოს სიბრტყეზე ტოლგვერდა სამკუთხედის სახით, რომელიც ივსება თვითნებური ობიექტებით (ბირთვები), რომლებიც განლაგებულია ჭადრაკით. ამ შემთხვევაში, თითოეული სამკუთხა რიცხვის მნიშვნელობა T k განსაზღვრავს გამომსახველი ბირთვების რაოდენობას და ინდექსი გვიჩვენებს ბირთვის რამდენი მწკრივია საჭირო მის წარმოსაჩენად. მაგალითად, 4 საწყისი სამკუთხა რიცხვი წარმოადგენს ბირთვული "@" სიმბოლოების შესაბამისი რაოდენობის შემდეგ კონფიგურაციას:
უნდა აღინიშნოს, რომ ანალოგიურად შეიძლება მხედველობაში მივიღოთ S k კვადრატული რიცხვები, რომლებიც მიიღება ნატურალური რიცხვების კვადრატში და, ზოგადად, მრავალკუთხა ფიგურული რიცხვები, რომლებიც წარმოიქმნება რეგულარული მრავალკუთხედების რეგულარული შევსებით. კერძოდ, 4 საწყისი კვადრატული რიცხვი შეიძლება წარმოდგენილი იყოს შემდეგნაირად:
პასკალის სამკუთხედის ვერტიკალების ანალიზს რომ დავუბრუნდეთ, შეგვიძლია აღვნიშნოთ, რომ შემდეგი ვერტიკალი m=3-ზე ივსება ტეტრაედრული (პირამიდული) რიცხვებით. თითოეული ასეთი რიცხვი P k განსაზღვრავს ბირთვების რაოდენობას, რომლებიც შეიძლება განლაგდეს ტეტრაედრის ფორმაში და ინდექსი განსაზღვრავს ბირთვების მწკრივების რამდენი ჰორიზონტალური სამკუთხა ფენა არის საჭირო მისი სამგანზომილებიან სივრცეში გამოსახვისთვის. ამ შემთხვევაში, ყველა ჰორიზონტალური ფენა უნდა იყოს წარმოდგენილი თანმიმდევრული სამკუთხა რიცხვების სახით. პასკალის სამკუთხედის შემდეგი ვერტიკალების ელემენტები m>3-ისთვის ქმნიან ჰიპერტეტრაედულ რიცხვებს, რომლებსაც არ აქვთ ვიზუალური გეომეტრიული ინტერპრეტაცია სიბრტყეზე ან სამგანზომილებიან სივრცეში, მაგრამ ფორმალურად შეესაბამება სამკუთხა და ოთხკუთხედის მრავალგანზომილებიან ანალოგებს.
მიუხედავად იმისა, რომ პასკალის სამკუთხედის ვერტიკალური რიცხვების სერიას აქვს განხილული ინდივიდუალური ფორმის მახასიათებლები, მათთვის შესაძლებელია საწყისი ელემენტების მნიშვნელობების ნაწილობრივი ჯამების გამოთვლა იმავე გზით, კომბინაციების რიცხვების შეჯამების ფორმულის გამოყენებით. . პასკალის სამკუთხედში ამ ფორმულას აქვს შემდეგი გეომეტრიული ინტერპრეტაცია. ნებისმიერი ვერტიკალის n ზედა ბინომიალური კოეფიციენტების მნიშვნელობების ჯამი უდრის შემდეგი ვერტიკალის ელემენტის მნიშვნელობას, რომელიც მდებარეობს ერთი ხაზის ქვემოთ. ეს შედეგი ასევე შეესაბამება სამკუთხა, ოთხკუთხა და ჰიპერტეტრაჰედული რიცხვების გეომეტრიულ სტრუქტურას, ვინაიდან თითოეული ასეთი რიცხვის წარმოდგენა შედგება ძირითადი ფენებისგან, რომლებიც წარმოადგენენ ქვედა რიგის რიცხვებს. კერძოდ, n-ე სამკუთხა რიცხვი Tn შეიძლება მივიღოთ ყველა ნატურალური რიცხვის შეჯამებით, რომლებიც წარმოადგენს მის წრფივ შრეებს:
ანალოგიურად, რთული არ არის Pn ტეტრაედრული რიცხვის პოვნა პირველი n სამკუთხა რიცხვების შემდეგი ჯამის გამოთვლით, რომლებიც ქმნიან მის ჰორიზონტალურ ბირთვს:
პასკალის მართკუთხა სამკუთხედში ჰორიზონტლებისა და ვერტიკალების გარდა, შესაძლებელია ელემენტების დიაგონალური რიგების მიკვრა, რომელთა თვისებების შესწავლაც ასევე საინტერესოა. ამ შემთხვევაში, ჩვეულებრივ, განასხვავებენ დაღმავალ და აღმავალ დიაგონალებს. დაღმავალი დიაგონალები პასკალის მართკუთხა სამკუთხედის ჰიპოტენუზის პარალელურია. ისინი წარმოიქმნება ბინომიალური კოეფიციენტების სერიებით ორივე ინდექსის ნაზრდით. სიმეტრიის იდენტურობის გამო, დაღმავალი დიაგონალები მათი ელემენტების მნიშვნელობებში ემთხვევა პასკალის სამკუთხედის შესაბამის ვერტიკალურ რიგებს და, შესაბამისად, იმეორებს მათ ზემოთ განხილულ ყველა თვისებას. მითითებულ კორესპონდენციას შეიძლება მივაკვლიოთ დაღმავალი დიაგონალის და ვერტიკალის ელემენტების მნიშვნელობების დამთხვევით ნებისმიერ n რიცხვთან, თუ ვერტიკალური ნულები არ არის გათვალისწინებული:
აღმავალი დიაგონალები ქმნიან რიცხვთა სერიას გეომეტრიულად პერპენდიკულარულ პასკალის მართკუთხა სამკუთხედის ჰიპოტენუზაზე. ისინი ივსება ბინომიალური კოეფიციენტებით ქვედა და ზედასკრიპტის კლებით. კერძოდ, 7 ზედა აღმავალი დიაგონალი ქმნიან შემდეგ ციფრულ თანმიმდევრობას უკანა ნულების გათვალისწინების გარეშე:
ზოგადად, აღმავალი დიაგონალური რიცხვი n შეიცავს შემდეგ ბინომურ კოეფიციენტებს, რომელთაგან თითოეულის ინდექსების ჯამი უდრის (n1):
კომბინირებული რიცხვების შეკრების იდენტურობის წყალობით, თითოეული დიაგონალური ელემენტი უდრის ორი ელემენტის ჯამს, რომლებიც შეესაბამება წინა ორი აღმავალი დიაგონალის ინდექსებს. ეს საშუალებას აძლევს ყოველი მომდევნო აღმავალი დიაგონალის აგებას ორი წინა დიაგონალიდან მიმდებარე ჰორიზონტალური ელემენტების წყვილი ჯამით, უსასრულოდ აფართოებს პასკალის სამკუთხედს დიაგონალის გასწვრივ. პასკალის სამკუთხედის შემდეგი ფრაგმენტი ასახავს აღმავალი დიაგონალის 8-ის აგებას 6 და 7 დიაგონალების გასწვრივ:
აგების ამ მეთოდით, ნებისმიერი აღმავალი დიაგონალის ელემენტების ჯამი, მე-3-დან დაწყებული, ტოლი იქნება ორი წინა აღმავალი დიაგონალის ელემენტების ჯამის, ხოლო პირველი 2 დიაგონალი შედგება მხოლოდ ერთი ელემენტისგან, მნიშვნელობისგან. რომელთაგან არის 1. შესაბამისი გამოთვლების შედეგები ქმნიან შემდეგ რიცხვობრივ სერიას, რომლის მიხედვითაც შეგიძლიათ შეამოწმოთ პასკალის მართკუთხა სამკუთხედის აღმავალი დიაგონალების განხილული თვისების მართებულობა:
ამ რიცხვების გაანალიზებისას ხედავთ, რომ მსგავსი კანონის მიხედვით, იქმნება ფიბონაჩის რიცხვების ცნობილი მიმდევრობა, სადაც ყოველი შემდეგი რიცხვი უდრის ორი წინა რიცხვის ჯამს, ხოლო პირველი ორი რიცხვი უდრის 1-ს:
ამრიგად, შეგვიძლია გამოვიტანოთ შემდეგი მნიშვნელოვანი დასკვნა: პასკალის სამკუთხედის ელემენტების დიაგონალური ჯამები ქმნიან ფიბონაჩის მიმდევრობას. ეს თვისება საშუალებას გვაძლევს დავადგინოთ პასკალის სამკუთხედის კიდევ ერთი საინტერესო თვისება. ფიბონაჩის ფორმულის რეკურსიულად გაფართოებით, ადვილია იმის მტკიცება, რომ პირველი n ფიბონაჩის რიცხვების ჯამი უდრის (F n+2 1).
მაშასადამე, ორობითი კოეფიციენტების ჯამი, რომლებიც ავსებენ ზედა n დიაგონალებს, ასევე უდრის (F n+2 1). აქედან გამომდინარეობს, რომ პასკალის სამკუთხედის პირველი n დიაგონალების ჯამი 1-ით ნაკლებია იმ ორობითი კოეფიციენტების ჯამზე, რომლებიც დგანან მის დიაგონალზე რიცხვთან (n+2).
დასასრულს, უნდა აღინიშნოს, რომ პასკალის სამკუთხედის ჰორიზონტალური, ვერტიკალებისა და დიაგონალების განხილული თვისებები არ ამოწურავს მრავალფეროვან შესაძლებლობებს, რომლებიც ერთმანეთთან აკავშირებს სხვადასხვა მათემატიკურ ასპექტებს, რომლებსაც ერთი შეხედვით საერთო არაფერი აქვთ. ასეთი უჩვეულო თვისებები საშუალებას გვაძლევს მივიჩნიოთ პასკალის სამკუთხედი ერთ-ერთი ყველაზე სრულყოფილი რიცხვითი სისტემა, რომლის ყველა შესაძლებლობების ჩამოთვლა შეუძლებელია და ძნელია გადაჭარბებული შეფასება.
პასკალის სამკუთხედის გამოყენებით კომბინაციების რაოდენობის გამოთვლის ალგორითმი წარმოდგენილია ქვემოთ:
პირადი ფუნქცია SochTT (ByVal n როგორც მთელი რიცხვი, ByVal k როგორც მთელი რიცხვი) როგორც ორმაგი Dim i როგორც მთელი Dim j როგორც მთელი Dim TT () როგორც Double ReDim TT (n, k) იყიდება i = 0-დან n TT-მდე (0, i) = 1 TT (i, i) = 1 შემდეგი For i = 2-დან n-მდე j = 1-მდე i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) შემდეგი შემდეგი SochTT = TT (n, k) ბოლო ფუნქცია
თუ თქვენ გჭირდებათ კომბინაციების რაოდენობის მრავალჯერ გამოთვლა, მაშინ შეიძლება უფრო მოსახერხებელი იყოს პასკალის სამკუთხედის ერთხელ აგება და შემდეგ მონაცემების მიღება მასივიდან.
Dim TT () როგორც Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 ბოლო Sub Private ფუნქცია SochTT (ByVal n როგორც მთელი რიცხვი, ByVal k როგორც მთელი რიცხვი) როგორც Double If n > Ubound (TT) შემდეგ BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) დასრულებული ფუნქცია Private Sub TerminateTT () ReDim TT (0, 0) ბოლო Sub Private Sub BuildTT (ByVal დაწყება როგორც მთელი რიცხვი, ByVal დასასრული როგორც მთელი რიცხვი) Dim i როგორც მთელი რიცხვი Dim j როგორც მთელი რიცხვი ReDim შენახვა TT (დასრულება, დასასრული) იყიდება i = დასაწყისი დასრულებამდე TT (0, i) = 1 TT (i, i) = 1 შემდეგი თუ დასასრული< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
ჯერ უნდა გამოიძახოთ CreateTT პროცედურა. ამის შემდეგ შეგიძლიათ მიიღოთ კომბინაციების რაოდენობა SochTT ფუნქციის გამოყენებით. როდესაც აღარ გჭირდებათ სამკუთხედი, გამოიძახეთ TerminateTT პროცედურა. ზემოთ მოყვანილ კოდში, SochTT ფუნქციის გამოძახებისას, თუ სამკუთხედი ჯერ არ არის დასრულებული საჭირო დონეზე, მაშინ ის სრულდება BuildTT პროცედურის გამოყენებით. შემდეგ ფუნქცია იღებს TT მასივის სასურველ ელემენტს და აბრუნებს მას.
Dim X () როგორც მთელი რიცხვი Dim მრიცხველი () როგორც მთელი რიცხვი Dim K როგორც მთელი Dim N როგორც მთელი საჯარო Sub Soch() Dim i როგორც მთელი N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1-დან N-მდე X(i) = i შემდეგი txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c როგორც მთელი რიცხვი) Dim i როგორც მთელი რიცხვი Dim j როგორც მთელი Dim n1 როგორც მთელი რიცხვი Dim Out() როგორც მთელი რიცხვი Dim X1() როგორც მთელი რიცხვი თუ c = K მაშინ ReDim Out(K) X1 = X იყიდება i = 1-დან K - 1 n1 = 0 j = 1-მდე N თუ X1(j)<>0 შემდეგ n1 = n1 + 1 თუ n1 = მრიცხველი(i) მაშინ Out(i) = X1(j) X1(j) = 0 გასასვლელი, თუ შემდეგი txtOut.Text = txtOut.Text & CStr(Out(i)) შემდეგი txtOut.Text = txtOut.Text & vbCrLf სხვა მრიცხველისთვის (c) = მრიცხველისათვის (c - 1) N - c + 1 SochGenerate c + 1 შემდეგი დასასრული თუ ბოლო Sub
ნატურალური რიცხვების კომბინაციების ჩამონათვალი
მრავალი პრაქტიკული პრობლემის გადასაჭრელად აუცილებელია ჩამოვთვალოთ ფიქსირებული კარდინალურობის ყველა კომბინაცია, რომელიც შეიძლება მიღებულ იქნას მოცემული სასრული ნაკრების ელემენტებიდან და არა მხოლოდ მათი რიცხვის დადგენა. ნებისმიერი სასრული სიმრავლის ელემენტების მთელი რიცხვითი ნუმერაციის ყოველთვის არსებული შესაძლებლობის გათვალისწინებით, უმეტეს შემთხვევაში დასაშვებია შემოვიფარგლოთ ნატურალური რიცხვების კომბინაციების ჩამოთვლის ალგორითმების გამოყენებით. მათგან ყველაზე ბუნებრივი და მარტივი არის ბუნებრივი რიცხვების კომბინაციების ჩამოთვლის ალგორითმი ლექსიგრაფიული წესრიგი.
ამ ალგორითმის ოფიციალურად აღწერისთვის მოსახერხებელია ვივარაუდოთ, რომ ძირითადი ნაკრები, რომლის m ელემენტების ყველა კომბინაცია უნდა იყოს ჩამოთვლილი, ქმნის თანმიმდევრულ ბუნებრივ რიცხვებს 1-დან n-მდე. მაშინ მ-ის ნებისმიერი კომბინაცია შეკვეთის შედეგად, კომბინაციების ასეთი ვექტორის თითოეულ პოზიციაში მნიშვნელობა ბუნებრივად გამოდის მნიშვნელობით შეზღუდული ზემოდან და ქვემოდან შემდეგნაირად: ლექსიგრაფიული ალგორითმი თანმიმდევრულად წარმოქმნის ასეთ კომბინირებულ ვექტორებს, დაწყებული ლექსიგრაფიულად უმცირესი ვექტორიდან, სადაც ყველა პოზიცია შეიცავს ელემენტების შემდეგ მინიმალურ შესაძლო მნიშვნელობებს მათი ინდექსების ტოლი: ყოველი თანმიმდევრული კომბინაციის ვექტორი წარმოიქმნება მიმდინარე ვექტორიდან მისი ელემენტების მარცხნიდან მარჯვნივ სკანირების შემდეგ, რათა ვიპოვოთ ყველაზე მარჯვენა ელემენტი, რომელსაც ჯერ არ მიუღწევია მის ზღვრულ მნიშვნელობას: ასეთი ელემენტის მნიშვნელობა უნდა გაიზარდოს 1-ით. თითოეულ ელემენტს მისგან მარჯვნივ უნდა მიენიჭოს უმცირესი შესაძლო მნიშვნელობა, რომელიც 1-ით მეტია მის მეზობელზე მარცხნივ. ამ ცვლილებების შემდეგ, კომბინაციების შემდეგ ვექტორს ექნება შემდეგი ელემენტარული შემადგენლობა: ამრიგად, შემდეგი კომბინაციის ვექტორი ლექსიგრაფიულად უფრო დიდი იქნება ვიდრე წინა, რადგან მათი საწყისი (j1) ელემენტების მნიშვნელობები ტოლია, ხოლო ელემენტის მნიშვნელობა j პოზიციაზე 1-ით მეტია წინაზე. . მზარდი ლექსიგრაფიული რიგის მითითებული მიმართება გარანტირებულია დაკმაყოფილებული ალგორითმის ყველა გამეორებისას. შედეგი არის მზარდი ლექსიგრაფიული თანმიმდევრობა, რომელიც სრულდება ლექსიგრაფიულად ყველაზე დიდი კომბინაციის ვექტორით, სადაც ყველა პოზიციის ელემენტებს აქვთ შემდეგი მაქსიმალური მნიშვნელობები: განხილული ლექსიგრაფიული ალგორითმი ილუსტრირებულია შემდეგი მაგალითით, სადაც საჭიროა მზარდი ლექსიგრაფიული თანმიმდევრობით ჩამოვთვალოთ n=6 პირველი ნატურალური რიცხვის ყველა 15 კომბინაცია m=4 რიცხვით, ანუ ძირითადი გენერირების ყველა შესაძლო 4 ელემენტიანი ქვესიმრავლე. კომპლექტი (1, 2, 3, 4, 5, 6) 6 ელემენტიდან. გაანგარიშების შედეგები მოცემულია შემდეგ ცხრილში: ამ მაგალითში, რიცხვების ყველაზე დიდი დასაშვები მნიშვნელობები კომბინაციის ვექტორების პოზიციებზე არის, შესაბამისად, 3, 4, 5 და 6. შედეგების ინტერპრეტაციის გასაადვილებლად, თითოეულ კომბინაციის ვექტორში ყველაზე მარჯვენა ელემენტია, რომელსაც აქვს ჯერ არ არის მიღწეული მისი მაქსიმალური მნიშვნელობა, ხაზგასმულია. კომბინირებული ვექტორების რიცხვითი ინდექსები განსაზღვრავს მათ რიცხვებს ლექსიგრაფიული თანმიმდევრობით. ზოგად შემთხვევაში, n ელემენტის ნებისმიერი კომბინაციის M ლექსიგრაფიული რიცხვი N შეიძლება გამოითვალოს შემდეგი ფორმულის გამოყენებით, სადაც კოსმეტიკური მიზეზების გამო გამოიყენება აპელური სიმბოლიზმი კომბინაციების რიცხვების აღსანიშნავად: კერძოდ, შემდეგი გამოთვლები ამ ფორმულის გამოყენებით ლექსიგრაფიული თანმიმდევრობით m=4 ელემენტის n=6 ელემენტის კომბინაციის რიცხვისთვის (1, 3, 4, 6), მიიღება შედეგი N=8, რომელიც შეესაბამება ზემოთ განხილულ მაგალითს: ზოგად შემთხვევაში, ორივე ინდექსისთვის კომბინაციების რიცხვების ჯამის იდენტურობის გამოყენებით, შესაძლებელია აჩვენოთ, რომ ლექსიგრაფიულად უმცირესი კომბინაციის რაოდენობა (1, ... i, ... m) ამ გამოთვლისას. ფორმულა ყოველთვის იქნება 1-ის ტოლი: ასევე აშკარაა, რომ ლექსიგრაფიულად ყველაზე დიდი კომბინაციის რაოდენობა (m, … nm+i, … n) ამ ფორმულის გამოყენებით ტოლი იქნება n ელემენტის კომბინაციების რაოდენობას m-ით: ლექსიგრაფიული კომბინაციის რიცხვების გამოთვლის ფორმულა შეიძლება გამოყენებულ იქნას შებრუნებული ამოცანის გადასაჭრელად, სადაც საჭიროა კომბინაციის ვექტორის განსაზღვრა მისი რიცხვით ლექსიგრაფიული თანმიმდევრობით. ასეთი შებრუნებული პრობლემის გადასაჭრელად, ის უნდა დაიწეროს განტოლების სახით, სადაც სასურველი კომბინაციის ვექტორის ელემენტების ყველა უცნობი მნიშვნელობა (C 1, ... C i, ... C m ) კონცენტრირებულია მისი მარჯვენა მხარის კომბინაციების რიცხვებში, ხოლო ცნობილი სხვაობა L კომბინაციების რიცხვში იწერება n ელემენტის მარცხენა მხარეს თითოეული m და საჭირო კომბინაციის N რიცხვი: ამ განტოლების ამოხსნა მოცემულია შემდეგი „ხარბი“ ალგორითმით, რომლის გამეორებების დროს თანმიმდევრულად ირჩევა სასურველი კომბინაციის ვექტორის ელემენტების მნიშვნელობები. საწყის გამეორებისას არჩეულია C 1-ის მინიმალური შესაძლო (მისი შეზღუდვების ფარგლებში) მნიშვნელობა, რომლის დროსაც მარჯვენა მხარეს პირველ ტერმინს ექნება მაქსიმალური მნიშვნელობა, რომელიც არ აღემატება L: ახლა L-ის მარცხენა მხარე უნდა შემცირდეს კომბინაციების პირველი რაოდენობით მარჯვენა მხარეს C 1 შერჩეული მნიშვნელობით და ანალოგიურად განვსაზღვროთ C 2-ის მნიშვნელობა მეორე გამეორებისას: ანალოგიურად, ყველა შემდგომი გამეორება უნდა შესრულდეს სასურველი კომბინაციის ყველა სხვა ელემენტის C i მნიშვნელობების შესარჩევად, ბოლო ელემენტამდე C m: აშკარა მიზეზების გამო, Cm ბოლო ელემენტის მნიშვნელობა შეიძლება განისაზღვროს მისი კომბინაციების რაოდენობის ტოლობის საფუძველზე L-ის მარცხენა მხარის ნარჩენი მნიშვნელობის მიხედვით: უნდა აღინიშნოს, რომ C m კომბინაციის ბოლო ელემენტის მნიშვნელობა შეიძლება კიდევ უფრო მარტივად მოიძებნოს, მისი შესაძლო მნიშვნელობების ჩამოთვლის გარეშე: განხილული ალგორითმის გამეორებების განხორციელება ილუსტრირებულია შემდეგი მაგალითით, სადაც საჭიროა ლექსიგრაფიული თანმიმდევრობით N=8 რიცხვთან კომბინაციების დადგენა, თუ n=6 და m=4: მოცემული რიცხვით კომბინაციის განსაზღვრის ალგორითმული უნარი ლექსიგრაფიული თანმიმდევრობით შეიძლება გამოყენებულ იქნას სხვადასხვა მიმართულებით. კერძოდ, კომბინაციების ლექსიგრაფიული თანმიმდევრობით ჩამოთვლისას აუცილებელია უზრუნველვყოთ ადრე მიღებულ ნებისმიერ კომბინაციაზე დაბრუნება, საკმარისია მხოლოდ მისი რიცხვის ცოდნა. გარდა ამისა, შესაძლებელი ხდება კომბინაციების გენერირება ნებისმიერი თანმიმდევრობით, რაც რეგულირდება მათი ლექსიგრაფიული რიცხვების თვითნებურად მოცემული თანმიმდევრობით. ახლა წარმოგიდგენთ კომბინაციების გენერირების ალგორითმს ლექსიკოგრაფიული თანმიმდევრობით: 2 i:= 1-დან k-მდე გააკეთე A[i] := i; 5 წერის დაწყება (A, …, A[k]); 6 თუ A[k] = n მაშინ p:= p 1 სხვას p:= k; 8 i:= k ქვემოთ p-მდე გააკეთე A[i] := A[p] + i p + 1 კომბინაციები განმეორებით ელემენტებთან კლასიკური კომბინაციისგან განსხვავებით, სადაც ყველა ელემენტი განსხვავებულია, გამეორებებთან კომბინაცია ქმნის სასრული ნაკრების ელემენტების შეურიგებელ არჩევანს, სადაც ნებისმიერი ელემენტი შეიძლება გამოჩნდეს განუსაზღვრელი დროით ხშირად და არ იყოს აუცილებლად წარმოდგენილი ერთ ეგზემპლარად. ამ შემთხვევაში, ელემენტების გამეორებების რაოდენობა ჩვეულებრივ შემოიფარგლება მხოლოდ კომბინაციის სიგრძით და კომბინაციები, რომლებიც განსხვავდება მინიმუმ ერთ ელემენტში, განსხვავებულად ითვლება. მაგალითად, 1, 2 და 3 ნაკრებიდან 4 სურვილისამებრ განსხვავებული რიცხვის არჩევით, შეგიძლიათ შექმნათ შემდეგი 15 კომბინაცია გამეორებებით: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
ზოგადად, კომბინაციები გამეორებით შეიძლება ჩამოყალიბდეს თვითნებური ტიპების n ელემენტის არჩევით. თუმცა, ისინი ყოველთვის შეიძლება ასოცირდეს თანმიმდევრულ ნატურალურ რიცხვებთან 1-დან n-მდე. შემდეგ ამ დიაპაზონში m სურვილისამებრ განსხვავებული რიცხვების ნებისმიერი კომბინაცია შეიძლება დაიწეროს ვექტორული ფორმით, დაალაგოთ ისინი მარცხნიდან მარჯვნივ შეუმცირებელი თანმიმდევრობით: ბუნებრივია, ნოტაციის ამ ფორმით, ნებისმიერი მეზობელი ელემენტი შეიძლება იყოს თანაბარი შეუზღუდავი გამეორების შესაძლებლობის გამო. თუმცა, ყოველი კომბინირებული ვექტორი n ელემენტის m-ით გამეორებით შეიძლება ასოცირებული იყოს (n+m−1) ელემენტების კომბინაციის ვექტორთან m-ით, რომელიც აგებულია შემდეგნაირად: ნათელია, რომ ვექტორის ელემენტის ნებისმიერი მნიშვნელობისთვის, ვექტორის C ელემენტები გარანტირებულია განსხვავებული და მკაცრად დალაგებული მათი მნიშვნელობების გაზრდის თანმიმდევრობით 1-დან (n+m1-მდე) დიაპაზონში. : კომბინაციის ვექტორების f და C ელემენტებს შორის ერთი-ერთზე კორესპონდენციის არსებობა საშუალებას გვაძლევს შემოგთავაზოთ შემდეგი მარტივი მეთოდი კომბინაციების სისტემატიურად ჩამოთვლისთვის n ელემენტის გამეორებით m-ით. საჭიროა მხოლოდ ჩამოვთვალოთ, მაგალითად, ლექსიგრაფიული თანმიმდევრობით, m-ის (n+m1) ელემენტების ყველა C კომბინაცია, თითოეული მათგანის ელემენტების თანმიმდევრულად გარდაქმნა კომბინაციების შესაბამის ელემენტებად f გამეორებებით შემდეგი ფორმულის გამოყენებით: შედეგად, იქმნება კომბინაციების ვექტორების თანმიმდევრობა ელემენტების გამეორებით, რომლებიც განლაგებულია გენერირებული თანმიმდევრობით, ელემენტების გამეორების გარეშე შესაბამისი კომბინაციების ჩამოთვლით. კერძოდ, 3 ციფრის 1, 2 და 3 კომბინაციების ზემოაღნიშნული თანმიმდევრობის მისაღებად 4 ციფრის გამეორებით, აუცილებელია ლექსიგრაფიული თანმიმდევრობით ჩამოვთვალოთ ყველა კომბინაცია 6 ციფრის გამეორების გარეშე 1,2,3,4, 5. და 6 არის 4 ციფრი თითოეული, გარდაქმნის მათ, როგორც მითითებულია. შემდეგი მაგალითი გვიჩვენებს კომბინაციის (1,3,4,6) ასეთ კონვერტაციას ლექსიკოგრაფიულ რიცხვთან 8: განხილული ერთი-ერთზე მიმოწერა კომბინაციებს შორის ელემენტების გამეორებით და მის გარეშე ნიშნავს, რომ მათი ნაკრები თანაბრად ძლიერია. მაშასადამე, ზოგად შემთხვევაში, კომბინაციების რაოდენობა n ელემენტის გამეორებით m-ით უდრის კომბინაციების რაოდენობას (n+m1) ელემენტების m-ით გამეორების გარეშე. იგივე სიმბოლიზმის გამოყენებით კომბინაციების რიცხვების აღსანიშნავად გამეორებებით f და გამეორებების გარეშე C, ეს თანასწორობა შეიძლება დაიწეროს შემდეგნაირად: ადვილია იმის შემოწმება, რომ ზემოთ განხილულ მაგალითზე, სადაც n=3 და m=4, განმეორებითი კომბინაციების რაოდენობა იქნება 15-ის ტოლი, რაც ემთხვევა მათი პირდაპირი ჩამონათვალის შედეგს: უნდა აღინიშნოს, რომ კლასიკური ვერსიისგან განსხვავებით, კომბინაციის პარამეტრების მნიშვნელობები n და m გამეორებებით პირდაპირ არ არის დაკავშირებული ერთმანეთთან, შესაბამისად f(n,m)>0 მათი დადებითი მნიშვნელობების ნებისმიერი კომბინაციისთვის. შესაბამისი სასაზღვრო პირობები განისაზღვრება (n+m1) და (n1) ან (n+m1) და m მნიშვნელობებს შორის თანასწორობიდან: ასევე აშკარა უნდა იყოს, რომ თუ m უდრის 1-ს, მაშინ ელემენტების გამეორება შეუძლებელია და, შესაბამისად, ნებისმიერი დადებითი მნიშვნელობისთვის n>0 შემდეგი ტოლობა იქნება ჭეშმარიტი: გარდა ამისა, n-ისა და m-ის ნებისმიერი დადებითი მნიშვნელობების გამეორებით კომბინაციების რიცხვისთვის მოქმედებს შემდეგი განმეორებითი მიმართება, რომელიც მსგავსია ელემენტების გამეორების გარეშე კომბინაციების რიცხვების დამატების იდენტურობისთვის: ფაქტობრივად, იგი იქცევა მითითებულ დანამატის იდენტურობაში კომბინაციების შესაბამისი რაოდენობის ოფიციალური ჩანაცვლებისას გამეორების გარეშე მის მარცხენა და მარჯვენა მხარეებში: განხილული რეციდივის მიმართება შეიძლება გამოყენებულ იქნას კომბინაციების რაოდენობის ეფექტურად დასადგენად გამეორებებით, როდესაც მნიშვნელოვანია ფაქტორული პროდუქტების გამოთვლის შრომატევადი ოპერაციების აღმოფხვრა და მათი ჩანაცვლება უფრო მარტივი დამატების ოპერაციებით. ამ შემთხვევაში, f(n,m) მნიშვნელობის გამოსათვლელად, თქვენ მხოლოდ უნდა გამოიყენოთ ეს განმეორებითი მიმართება, სანამ არ მიიღებთ f(1,m) და f(i,1) ფორმის წევრთა ჯამს, სადაც i. იღებს მნიშვნელობებს n-დან 1-მდე დიაპაზონში. სიდიდის განმარტებით ასეთი ტერმინები უდრის 1-ს და i-ს, შესაბამისად. შემდეგი მაგალითი ასახავს ამ ტრანსფორმაციის ტექნიკის გამოყენებას n=3 და m=4 შემთხვევისთვის: ბინარული კომბინაციების ჩამონათვალი აპარატურაში კომბინაციების განხორციელებისას ან ასამბლეის ენაზე პროგრამირებისას მნიშვნელოვანია კომბინაციის ჩანაწერების ორობით ფორმატში დამუშავება. ამ შემთხვევაში, m-ის n ელემენტების ნებისმიერი კომბინაცია უნდა იყოს მითითებული n-ბიტიანი ორობითი რიცხვის სახით (B n,...B j,...B 1), სადაც m ერთეული ციფრები მიუთითებს ელემენტის ელემენტებზე. კომბინაცია და დარჩენილ (ნმ) ციფრებს აქვთ ნულოვანი მნიშვნელობები. ცხადია, აღნიშვნის ამ ფორმით, სხვადასხვა კომბინაციები უნდა განსხვავდებოდეს 1-ის ციფრების განლაგებაში, და არსებობს მხოლოდ C(n,m) გზები m-ის ან (nm) ნულების დასალაგებლად n-ბიტიან ორობით სიმრავლეში. მაგალითად, შემდეგ ცხრილში მოცემულია 6-ვე ასეთი ორობითი კომბინაცია, რომელიც უზრუნველყოფს 4-ბიტიან ბინარულ რიცხვებს თვითნებური ნაკრების 4 ელემენტის ყველა კომბინაციისთვის (E 1, E 2, E 3, E 4 ) 2-ით: ზოგად შემთხვევაში, ასეთი ორობითი კომბინაციების ჩამოთვლის ამოცანა მთავრდება ყველა n-ბიტიანი ორობითი სიმრავლის სისტემატიურ ძიებამდე m ერთი და (nm) ნულოვანი ბიტების სხვადასხვა განლაგებით. უმარტივესი ფორმით, ასეთი ძიება ხორციელდება მიმდებარე ბიტების გადაადგილების სხვადასხვა მეთოდით (ტრანსპოზიტიურ-ცვლის ალგორითმები). ეს არის განმეორებითი ალგორითმები და მათი სახელები ასახავს თითოეულ საფეხურზე შესრულებული ოპერაციების ბუნებას. ტრანსპოზიტიური ცვლის ალგორითმების განმეორებითი პროცედურები ქმნიან ბინარული კომბინაციების თანმიმდევრობებს, რომლებიც იწყება ორობითი სიმრავლით, სადაც ყველა კონცენტრირებულია დაბალი რიგის ციფრებში (მარჯვნივ) და მთავრდება, როდესაც ყველა 1 მაღალი რიგის ციფრებშია ( მარცხნივ): საწყის და საბოლოო კომბინაციებში შეხამებისას, ეს თანმიმდევრობები განსხვავდება შუალედური ორობითი სიმრავლების ჩამოთვლის თანმიმდევრობით. თუმცა, ყველა შემთხვევაში, ყოველი მომდევნო ორობითი კომბინაცია წარმოიქმნება წინადან შესაბამისი ტრანსპოზიციისა და ცვლის ოპერაციების შესრულების შედეგად. ამავდროულად, ტრანსპოზიტიური ცვლის სხვადასხვა ალგორითმები განსხვავდება იმით, თუ როგორ ირჩევენ ბიტების წყვილს ტრანსპოზიციისთვის და ბიტების ჯგუფს გადასატანად. ეს სპეციფიკა განხილულია ქვემოთ ტრანსპოზიციის ალგორითმებისთვის მარცხნივ და მარჯვნივ. ტრანსპოზიციის ალგორითმში მარცხნივ ცვლაზე, ყოველ საფეხურზე, შემდეგი ორობითი კომბინაცია მიიღება მიმდინარედან, 01 ციფრის მარცხენა წყვილის 10-ით ჩანაცვლებით (ტრანსპოზიცია) და წამყვანი ერთეულების ჯგუფის გადაადგილებით, ასეთის არსებობის შემთხვევაში, ახლოს. ტრანსპოზიციის (ცვლის) შემდეგ მიღებული წყვილი 10. თუ ამ შემთხვევაში არ არის ერთეული წინა ციფრებში მიმდინარე ორობით კომბინაციაში, მაშინ ცვლა არ შესრულდება მაშინაც კი, როდესაც წამყვანი ერთეული მიიღება ტრანსპოზიციის შემდეგ ამ საფეხურზე. ცვლა ასევე არ შესრულდება, როდესაც ტრანსპოზიციის შემდეგ მიღებულ წყვილ 10-მდე არ არის ნულები ყველაზე მნიშვნელოვან ბიტებში. განხილული მოქმედებები ილუსტრირებულია ამ ალგორითმის ორი თანმიმდევრული გამეორების შესრულების შემდეგი მაგალითით, სადაც ერთ გამეორებაზე (15) შესრულებულია მხოლოდ ტრანსპოზიცია (T"), ხოლო მეორე გამეორებაზე (16) ტრანსპოზიცია ავსებს ცვლას ( T"+S"): მარჯვენა ცვლის ტრანსპოზიციის ალგორითმში, კონცეპტუალურად მსგავსი ნაბიჯები შესრულებულია თითოეულ საფეხურზე. მხოლოდ ტრანსპოზიცია უზრუნველყოფს, რომ 01-ის ყველაზე მარჯვენა ბიტი ჩანაცვლდება 10-ით (მარცხნივ ყველაზე მარცხნივ) და შემდეგ ყველა მისგან მარჯვნივ გადაინაცვლებს ყველაზე ნაკლებად მნიშვნელოვან ბიტებზე. როგორც ადრე, ცვლა ხორციელდება მხოლოდ იმ შემთხვევაში, თუ არის ერთეულები, რომელთა გადატანა შესაძლებელია მარჯვნივ. განხილული მოქმედებები ილუსტრირებულია ამ ალგორითმის ორი თანმიმდევრული გამეორების შესრულების შემდეგი მაგალითით, სადაც ერთ გამეორებაზე (3) შესრულებულია მხოლოდ ტრანსპოზიცია (T"), ხოლო მეორე გამეორებაზე (4) ტრანსპოზიციას ავსებს ცვლა ( T"+S"): უნდა აღინიშნოს, რომ ორივე ალგორითმის გამეორებები შეიძლება დაიწეროს დანამატის სახით, თუ ორობითი კომბინაციები ინტერპრეტირებულია, როგორც მთელი რიცხვები საბაზისო 2 რიცხვების სისტემაში. კერძოდ, ტრანსპოზიციის ალგორითმისთვის მარჯვნივ ცვლა, ყოველი შემდეგი ორობითი კომბინაცია (B" n ,…B" j , …B" 1), ყოველთვის შეიძლება მივიღოთ მიმდინარე კომბინაციიდან (B n,...B j,...B 1) მთელი რიცხვების დამატების ოპერაციების შესრულებით შემდეგი დანამატის ფორმულის გამოყენებით: ამ დანამატის ფორმულაში, f და t-ის ხარისხების მაჩვენებლები აღნიშნავენ, შესაბამისად, მიმდინარე ბინარული კომბინაციის დაბალი რიგის ნულოვანი ციფრების რაოდენობას და მათგან მარცხნივ ზედიზედ ერთეულთა რაოდენობას. მაგალითად, n=6 ციფრის მე-4 ორობითი კომბინაციისთვის (001110) f =1 და t =3. მაშასადამე, შემდეგი ორობითი კომბინაციის გამოთვლა დანამატის ფორმულის გამოყენებით მე-5 გამეორებისას მისცემს შემდეგ შედეგს, რომელიც ექვივალენტურია ტრანსპოზიციისა და ცვლის ოპერაციების შესრულებისას: განხილული ტრანსპოზიციის ალგორითმების შედარებითი ანალიზისთვის მარცხნივ და მარჯვნივ ცვლებით, მიზანშეწონილია შევადაროთ ორობითი კომბინაციების თანმიმდევრობები, რომლებსაც ისინი წარმოქმნიან თავიანთ გამეორებებში. შემდეგი ცხრილი გვიჩვენებს 2-ის 4 ელემენტის ორობითი კომბინაციების ორ ასეთ თანმიმდევრობას, რომლებიც მიღებულია მარცხნივ (TSL) და მარჯვნივ (TSR) ცვლის ალგორითმებით, შესაბამისად: ამ 2 თანმიმდევრობის შედარებისას ხედავთ, რომ ისინი საპირისპირო სარკეა. ეს ნიშნავს, რომ ნებისმიერი ორი ორობითი კომბინაცია, რომელიც მათში მდებარეობს მათი მიმდევრობების ურთიერთსაპირისპირო ბოლოებიდან ერთსა და იმავე მანძილზე, ერთმანეთის სარკისებური გამოსახულებაა, ანუ ისინი ემთხვევა, როდესაც რომელიმე მათგანში ბიტების ინდექსირება შებრუნებულია. მაგალითად, მეორე ორობითი ნიმუში TSL მიმდევრობის დასაწყისიდან (0101) არის ორობითი ნიმუშის სარკისებური გამოსახულება (1010), რომელიც მეორეა TSR მიმდევრობის ბოლოდან. ზოგადად, ნებისმიერი ორობითი კომბინაცია ერთი მიმდევრობის i რიცხვთან არის ორობითი კომბინაციის სარკისებური გამოსახულება სხვა მიმდევრობის რიცხვთან (ni+1). ამ თანმიმდევრობებს შორის ეს კავშირი არის ტრანსპოზიციისა და ცვლის ოპერაციების სიმეტრიული ბუნების შედეგი ორ განხილულ ალგორითმში ბინარული კომბინაციების ჩამოთვლისთვის. უნდა აღინიშნოს, რომ ორობითი ფორმატი ასევე შეიძლება გამოყენებულ იქნას ელემენტების გამეორებით კომბინაციების ჩასაწერად. ამისათვის აუცილებელია ერთი-ერთზე კორესპონდენციის დამყარება კომბინაციებს შორის გამეორებებით და ბინარული კომბინაციებით, რომლებიც აგებულია შემდეგნაირად. მოდით იყოს თვითნებური კომბინაცია გამეორებებთან, რომელიც მიიღება გენერატორი სიმრავლის n ელემენტებისგან m სურვილისამებრ განსხვავებული ელემენტების არჩევით. სასურველი თანხვედრის დასადგენად, ჯერ უნდა დაამატოთ ფორმირების ნაკრების (კატა) ყველა ელემენტი კომბინაციაში, შემდეგ კი დაალაგოთ მიღებული შეერთება (დახარისხება) ისე, რომ ყველა იდენტური ელემენტი იყოს გვერდიგვერდ. შედეგი არის (n+m) ელემენტების თანმიმდევრობა, სადაც არის იდენტური ელემენტების n ჯგუფი. ელემენტებს შორის იქნება მთლიანი (n+m1) უფსკრული, რომელთა შორის იქნება (n1) უფსკრული იდენტური ელემენტების ჯგუფებს შორის და m უფსკრული ჯგუფებში ელემენტებს შორის. სიცხადისთვის, შეგიძლიათ განათავსოთ სიმბოლოები "|" მითითებულ სივრცეებში. და შესაბამისად. თუ ახლა დავამთხვევთ 1-ს ჯგუფებს შორის (|) და 0-ს ყველა სხვა სივრცეს (), მივიღებთ ორობით კომბინაციას. იგი წარმოიქმნება (n+m1) ბიტების ორობითი სიმრავლით, სადაც (n1) არის ერთი და m ნულოვანი ბიტი, რომელთა მდებარეობა ცალსახად შეესაბამება თავდაპირველ კომბინაციას n-დან m-მდე ელემენტების გამეორებით. განხილული ტრანსფორმაციის ტექნიკა ილუსტრირებულია ორობითი კომბინაციის აგების შემდეგი მაგალითით (1001101) კომბინაციის გამოყენებით გამეორებებით (BBD), რომლის ელემენტები შერჩეულია პირველი ხუთი ლათინური ასოების გენერატორიდან: ზოგადად, ასეთი ორობითი სიმრავლეების რაოდენობა განსაზღვრავს (n1) ერთეულების (ან m ნულების) (n+m1) ორობით ციფრებში მოწყობის გზების რაოდენობას. ეს მნიშვნელობა აშკარად უდრის კომბინაციების რაოდენობას (n+m1)-დან (n1) ან m-ით, ანუ C(n+m1,n1) ან C(n+m1,m), რაც უდრის კომბინაციების რაოდენობა გამეორებით f(n,m) n ელემენტის, m თითოეული. ამრიგად, გამეორებებით და ორობითი კომბინაციებით კომბინაციების ერთი-ერთზე კორესპონდენციის მქონე, ლეგიტიმურია კომბინაციების რიცხვის შემცირება გამეორებით ორობითი კომბინაციების ჩამოთვლამდე, მაგალითად, ტრანსპოზიციის ალგორითმების გამოყენებით მარცხნივ ან მარჯვნივ. ამის შემდეგ საჭიროა მხოლოდ საჭირო კომბინაციების აღდგენა გამეორებებით მიღებული ორობითი კომბინაციების გამოყენებით. ეს ყოველთვის შეიძლება გაკეთდეს შემდეგი აღდგენის ტექნიკის გამოყენებით. მოდით, ძირითადი ნაკრები, რომლის ელემენტებიდანაც ჩამოყალიბდება კომბინაციები m-ის გამეორებით, სულაც არ არის განსხვავებული ელემენტები, დაალაგეთ თვითნებურად ისე, რომ მის თითოეულ ელემენტს ჰქონდეს გარკვეული სერიული ნომერი 1-დან n-მდე. ასევე განვახორციელოთ (n+m1) ორობითი ციფრების ორობითი კომბინაციების ჩამოთვლა, სადაც (n1) ერთეული და m ნულოვანი ციფრი. ყოველი მიღებული ორობითი კომბინაცია შეიძლება დაემატოს მარცხნივ ფიქტიური ერთეულის ციფრით და ყველა ერთეული ციფრი შეიძლება დანომრილი იყოს მარცხნიდან მარჯვნივ მთელი რიცხვებით 1-დან n-მდე. მაშინ ორობითი კომბინაციის ყოველი i-ე ერთეულის შემდეგ ზედიზედ ნულების რიცხვი ტოლი იქნება ძირითადი ნაკრების i-ე ელემენტის შემთხვევების რაოდენობას შესაბამის კომბინაციაში გამეორებებით. განხილული ტექნიკა ილუსტრირებულია შემდეგი მაგალითით, სადაც ორობითი კომბინაციის (1001101) გამოყენებით აღდგება კომბინაცია BBD-ის გამეორებით, რომლის ელემენტები შერჩეულია პირველი ხუთი ლათინური ასოების გენერატორიდან, დაწერილი ანბანური თანმიმდევრობით. და გადახაზვა მიუთითებს ელემენტებზე, რომლებიც არ არის ამ კომბინაციაში: ამ მაგალითის პირობებში მსგავსი მოქმედებების შესრულებით, შეგიძლიათ ჩამოთვალოთ 35-ვე ორობითი კომბინაცია, რომლებიც ქმნიან 7-ბიტიან ორობით კომპლექტს, სადაც არის 4 ერთეული და 3 ნული, და აღადგინოთ შესაბამისი კომბინაციები 3-ის 5 ელემენტის გამეორებით. ზამთარი მოახლოვდა და ხომამ და სუსლიკმა გადაწყვიტეს ბარდა მოეგროვებინათ. მთელი დღე ბეღელში დარბოდნენ და რამდენიმე ღვეზელი მიჰქონდათ: ხომა, ოთხი და სუსლიკი, ორი. საღამომდე დათვალეს ყველა წიპწა, რომელიც მოკრეფილი ჰქონდათ და აინტერესებდათ, როგორ დაყოთ ახლა ეს ბარდა. ხომა ამტკიცებდა, რომ თუ სუსლიკზე ორჯერ მეტი ათრევდა, მაშინ ორჯერ მეტი ბარდა უნდა მიეღო. სუსლიკი გონივრულად აპროტესტებდა ამას, რომ ჯერ ერთი, ხომას სიჩქარე შესამჩნევად დაბალია, ვიდრე სუსლიკი, მეორეც, ვინ იცის, ხომამ შეიძლება მხოლოდ ერთი-ორჯერ გაიქცა, დანარჩენ დროს კი უსაქმოდ იყო... დაეხმარეთ თქვენს მეგობრებს ოდნავ მაინც გაიგონ ეს რთული სიტუაცია. დაადგინეთ ყველა შესაძლო ვარიანტი, თუ რამდენი პოდი მოიტანა სუსლიკმა და რამდენი ხომა. პირველ სტრიქონში არის ბუნებრივი ლუწი რიცხვი M - მოპარული წიპწების რაოდენობა, 2 ≤ M ≤ 1000. სუსლიკისა და ხომას მიერ მოტანილი წიპწების რაოდენობის ყველა შესაძლო კომბინაცია, თითო კომბინაცია ხაზში. თითოეული კომბინაცია წარმოადგენს ორ არაუარყოფით მთელ რიცხვს, რომლებიც გამოყოფილია ინტერვალით: პირველი რიცხვი არის სუსლიკის მიერ მოტანილი პოდრების რაოდენობა, მეორე - ხომას მიერ მოტანილი. დაალაგეთ კომბინაციები პირველი რიცხვის კლებადობით. #შეიცავს სახელთა სივრცის გამოყენებით std ; int main()( int a, b = 0; cin >> a ; ხოლო (a >= 0 ) ( კოუტ<<
a
<<
" "
<<
b
<<
"\n"
;
a -= 4; b += 4 ; დაბრუნება 0; მოდით a იყოს ჰომას მიერ მოტანილი წიპწების რაოდენობა და b იყოს სუსლიკის მიერ მოტანილი წიპწების რაოდენობა. ვინაიდან, ამოცანის პირობების მიხედვით, ხომამ მხოლოდ ოთხი ჯირკვალი ატარებდა, განვიხილავთ a = a-4 და b = b + 4, რათა ამგვარად ჩამოვთვალოთ სუსლიკისა და ხომას მიერ მოტანილი წიპწების რიცხვების ყველა შესაძლო კომბინაცია. მოდით ასევე გამოვიყენოთ მარყუჟი ხოლო, რომელიც გაიმეორებს ზემოთ აღწერილ ქმედებას \geq 0-მდე. პასუხში ვბეჭდავთ მეგობრების მიერ მოტანილი პოდების რიცხვის ყველა შესაძლო კომბინაციას, თითო სტრიქონზე, დალაგებულია პირველი ნომრის კლებადობით. მაგალითი // 52-დან 3-ის კომბინაცია (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
აქ განვიხილავთ უფრო რთულ პრობლემას, რომლის გადაწყვეტაც ვერ ვიპოვე RuNet-ში (თუმცა, ერთ ბმულს მივცემ, მაგრამ ეს ფორმულა აშკარად არასწორია) - დაფუძნებული თავად კომბინაციის საფუძველზე (ამ შემთხვევაში, კომპლექტი სამი რიცხვი) იპოვეთ მისი ინდექსი. დავუშვათ, განსაზღვრულობისთვის, i1 = 3, i2 = 7, i3 = 12 შეკვეთის შემდეგ. ტიპიური გენერირების ალგორითმი არის ის, რომ ჩვენ ვქმნით კომბინაციებს 2-დან 52-დან, და თითოეული ასეთი კომბინაციისთვის წყობილ მარყუჟში ჩვენ ვქმნით 3 კომბინაციებს 50-დან და ვამოწმებთ, რომ ინდექსები (i3, i4, i5) წყობილ კომბინაციაში ასეა. არ ემთხვევა ინდექსებს (i1, i2) გარე კომბინაციაში: C++ კოდი // გარე კომბინაცია (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ კოდი თუ (i3 >= i1) --i3; თუ (i3 >= i2) --i2; // მსგავსი i4, i5 მაგალითის კოდი გაყოფის ინდექსისთვის 2, 3, 47-ით int get_split_2_3_47_index(int 'i1, int i2, int i3, int i4, int i5) ( // 52-დან 2-ის კომბინაციის ინდექსი, გამრავლებული C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "ხელახლა ინდექსირება" შიდა ჯგუფი ისე, რომ ნუმერაცია არის 0...49, თუ (i3 > = i1) --i3; თუ (i3 >= i2) --i3; თუ (i4 >= i1) --i4; თუ (i4 >= i2) --i4; თუ (i5 >= i1) --i5 ; თუ (i5 >= i2) --i5; // ახლა დაამატეთ კომბინაციის ინდექსი 3-ით // 0: // SUM n = 0-ისთვის i3-1-ით COMBINATIONS (2, 49-n) // = SUM m = 50-i3-ისთვის 49-ით (m * (m-1) / 2) ოფსეტური += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // ჯამი n = i3+1-დან i4-1-მდე კომბინაციებისთვის (1, 49-n) ოფსეტური += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUM n = i4+1-დან i5-1-მდე (1) ოფსეტისთვის + = (i5 - i4 - 1); დაბრუნების ოფსეტური ;) ზოგადად, კომბინატორულ ალგორითმებს დავყოფ შემდეგ კლასებად: კომბინაციების რაოდენობა კომბინაციასაწყისი ნავტორი კკომპლექტს უწოდებენ კმონაცემებიდან შერჩეული ელემენტები ნელემენტები. კომპლექტები, რომლებიც განსხვავდებიან მხოლოდ ელემენტების თანმიმდევრობით (მაგრამ არა შემადგენლობით) განიხილება იდენტურად, ამიტომ კომბინაციები განსხვავდება განლაგებისგან. კომბინაციების რაოდენობა ნავტორი კ
ბინომალური კოეფიციენტის ტოლია ფიქსირებული ღირებულებისთვის ნკომბინაციების რიცხვების გენერირების ფუნქცია გამეორებით ნავტორი კარის: კომბინაციების რიცხვების ორგანზომილებიანი გენერირების ფუნქცია გამეორებებით არის: ფონდი ვიკიმედია. 2010 წელი. 70 სამოცდაათი 67 68 69 70 71 72 73 40 50 60 70 80 90 100 ფაქტორიზაცია: 2×5×7 რომაული აღნიშვნა: LXX ორობითი: 100 0110 ... ვიკიპედია მსუბუქი რიცხვი, პირობითი რიცხვი, რომელიც ცალსახად გამოხატავს გარეგანს პირობები ფოტოგრაფიის დროს (ჩვეულებრივ საგნის სიკაშკაშე და გამოყენებული ფოტომასალას ფოტომგრძნობელობა). E.h-ის ნებისმიერი მნიშვნელობა შეიძლება რამდენჯერმე შეირჩეს. კომბინაციები დიაფრაგმის ნომერი ... ... დიდი ენციკლოპედიური პოლიტექნიკური ლექსიკონი რიცხვის ფორმა, რომელიც განასხვავებს ორ ობიექტს როგორც ერთ ობიექტთან, ასევე ბევრ ობიექტთან მიმართებაში. ეს ფორმა არ არსებობს თანამედროვე რუსულში, მაგრამ მისი გავლენის ნარჩენები რჩება. ასე რომ, ორი ცხრილის კომბინაცია (შდრ. მრავლობითი... ... ლინგვისტური ტერმინების ლექსიკონი კომბინატორიული მათემატიკა, კომბინატორიკა, მათემატიკის ფილიალი, რომელიც ეძღვნება გარკვეული, ჩვეულებრივ სასრული, ელემენტების არჩევისა და მოწყობის ამოცანების გადაჭრას მოცემული წესების შესაბამისად. ყოველი ასეთი წესი განსაზღვრავს მშენებლობის მეთოდს... ... მათემატიკური ენციკლოპედია კომბინატორიკაში by-ის კომბინაცია არის მოცემული სიმრავლიდან შერჩეული ელემენტების ნაკრები, რომელიც შეიცავს სხვადასხვა ელემენტებს. კომპლექტები, რომლებიც განსხვავდებიან მხოლოდ ელემენტების თანმიმდევრობით (მაგრამ არა შემადგენლობით) იდენტურად ითვლება, ეს კომბინაციები ... ... ვიკიპედია დაკავებულია მოვლენების შესწავლით, რომელთა დადგომა დანამდვილებით არ არის ცნობილი. ეს საშუალებას გვაძლევს ვიმსჯელოთ ზოგიერთი მოვლენის მოლოდინის გონივრული მნიშვნელობის შესახებ სხვებთან შედარებით, თუმცა მოვლენების ალბათობებისთვის რიცხვითი მნიშვნელობების მინიჭება ხშირად არასაჭიროა... ... კოლიერის ენციკლოპედია 1) იგივეა, რაც მათემატიკური კომბინატორიული ანალიზი. 2) ელემენტარული მათემატიკის განყოფილება, რომელიც დაკავშირებულია კომბინაციების რაოდენობის შესწავლასთან, გარკვეული პირობების გათვალისწინებით, რომელიც შეიძლება შედგებოდეს ობიექტების მოცემული სასრული სიმრავლისგან... ... დიდი საბჭოთა ენციკლოპედია - (ბერძნული პარადოქსები მოულოდნელი, უცნაური) ფართო გაგებით: განცხადება, რომელიც მკვეთრად განსხვავდება საყოველთაოდ მიღებული, დამკვიდრებული აზრისგან, უარყოფა იმისა, რაც ჩანს „უპირობოდ სწორი“; ვიწრო გაგებით, ორი საპირისპირო განცხადება, ამისთვის... ... ფილოსოფიური ენციკლოპედია - (ან ჩართვისა და გამორიცხვის პრინციპი) კომბინატორიული ფორმულა, რომელიც საშუალებას გაძლევთ განსაზღვროთ სასრული სიმრავლეების გაერთიანების კარდინალურობა, რომლებიც ზოგად შემთხვევაში შეიძლება იკვეთებოდეს ერთმანეთთან... ვიკიპედია მათემატიკური თეორია, რომელიც ეხება მოცემული ობიექტების ცნობილი თანმიმდევრობით განაწილების სხვადასხვა გზების რაოდენობის განსაზღვრას; განსაკუთრებით მნიშვნელოვანია განტოლებების თეორიასა და ალბათობის თეორიაში. ამ ტიპის უმარტივესი ამოცანებია... ... ენციკლოპედიური ლექსიკონი F.A. ბროკჰაუსი და ი.ა. ეფრონიᲨესაყვანი მონაცემები
გამომავალი
ტესტები
Შესაყვანი მონაცემები
გამომავალი
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
პროგრამის კოდი
პრობლემის გადაწყვეტა
კომბინაციის ინდექსი
ყოველი კომბინაცია, პერმუტაცია, განლაგება და სხვა კომბინატორული ობიექტები შეიძლება ასოცირებული იყოს ინდექსთან - ეს ის რიცხვია, რომელშიც ის ჩნდება ამ ალგორითმის გამეორებისას.
არსებობს "პირადი" ძებნის ვარიანტი. ჩართავთ კომბინაციის მრიცხველს, ვიღებთ ზემოთ მოცემულ ალგორითმს და ვცდილობთ ყველაფერს, სანამ არ მივაღწევთ სასურველ ვარიანტს. ამ ვარიანტს აქვს ძალიან დიდი დროის სირთულე, ამიტომ ჩვენ ამ ვარიანტს უარვყოფთ.
დავუშვათ, რომ შეყვანა შეიცავს რიცხვებს i1, i2, i3. უპირველეს ყოვლისა, ჩვენ უნდა მოვაწყოთ ისინი აღმავალი თანმიმდევრობით (გაითვალისწინეთ, რომ თავად გენერირების ალგორითმი, ზემოთ მოყვანილი, ყოველთვის აწარმოებს მათ მოწესრიგებულ ფორმაში, თუმცა თავად „კომბინაციის“ კონცეფცია გულისხმობს თვითნებურ წესრიგს).
ეს ნიშნავს, რომ ჩვენ „გავიარეთ“ ყველა კომბინაცია, სადაც i1 იყო 0, 1 და 2-ის ტოლი.
i1 = 0-ისთვის ჩვენ გავიარეთ C(2, 51) კომბინაციები, ვინაიდან i1, i2 ინდექსები გადის 51 რიცხვიდან 2-ის ყველა კომბინაციას.
i1 = 1-ისთვის გავიარეთ C(2, 50) კომბინაციები.
i1 = 2-ისთვის გავიარეთ C(2, 49) კომბინაციები.
საერთო ჯამში, ჩვენ გავიარეთ SUM (n = 0-დან n = i1-1-მდე) C(2, 51-n).
i1 = 3-ისთვის, განვიხილოთ ის კომბინაციები, რომლებიც გავიარეთ ინდექსი i2-ის გავლისას (და ჩვენთვის ის იწყება i2 = i1+1 = 4-ით).
როდესაც i2 = 4, C(1, 47) კომბინაციები გავიდა, როდესაც i2 = 5, C(1, 46) კომბინაციები გავიდა, როდესაც i2 = 6, C(1, 45) კომბინაციები გავიდა.
სრული ანალოგიით, i2 = 7-ისთვის განვიხილავთ კომბინაციებს, რომლებზეც გადიოდა ინდექსმა i3.
ჩვენ ვიღებთ ზოგად ფორმულას:
საჭირო კომბინაციის ინდექსი = SUM (n = 0-დან i1-1-მდე) C(2, 51-n) + SUM (n = i1+1-დან i2-1-მდე) C(1, 51-n) + SUM (დან n = i2+1-დან i3-1-მდე) C (0, 51-n).ქვეჯგუფის ინდექსი
კომბინატორიკაში არის უფრო რთული ობიექტი - დაყოფა ქვეჯგუფებად. მაგალითად, 52 ელემენტიანი ნაკრების დაყოფა სამ ქვეჯგუფად, მაგალითად, 2, 3 და 47 ელემენტების შესაბამისად, სადაც ელემენტების თანმიმდევრობა თითოეულ ქვეჯგუფში უმნიშვნელოა. (სხვათა შორის, 52-დან 2-ის კომბინაცია უბრალოდ 2 და 50 ელემენტის ორ ქვეჯგუფად გაყოფის განსაკუთრებული შემთხვევაა).
ისევ და ისევ, თითოეულ ასეთ დანაყოფს აქვს საკუთარი ინდექსი.
გამოდის, რომ ჩვენი ალგორითმი კომბინაციის ინდექსის მოსაძებნად შეიძლება შეიცვალოს დანაყოფის ინდექსის მოსაძებნად.
უნდა აღინიშნოს, რომ ინდექსები უნდა მოვაწყოთ „გარე კომბინაციით“ i1, i2 ერთმანეთში, ხოლო ინდექსები i3, i4, i5 ერთმანეთში, მაგრამ პირველი ორისგან დამოუკიდებლად.
გასათვალისწინებელია ისიც, რომ „ბუდებული კომბინაციით“ ჩვენ არსებითად ვმუშაობთ 50 ელემენტიან კომპლექტთან, მაგრამ i3, i4, i5 ინდექსები უნდა „გადაინაცვლოს“ გარკვეული გზით ისე, რომ ისინი არ შეიცვალოს 0-დან. 51-მდე, მაგრამ 0-დან 49-მდე:
(ასე ვთქვათ, ჩვენ ამოვჭრით i1, i2 ინდექსები ჩვენი 52 ელემენტიანი ნაკრებიდან და შემდეგ გადავიტანთ დარჩენილი ნაკრები ხვრელების დასახურავად, ხოლო i3-i5 ინდექსები გადაადგილებულია).
გასათვალისწინებელია, რომ ყოველი "გარე" კომბინაციის შიგნით გვაქვს ზუსტად C(3, 50) "ბუდებული" კომბინაცია.
შემდეგ ალგორითმი შემცირდება შემდეგზე:
COMBINATION_INDEX (i1, i2 52-დან) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 50-დან ინდექსის ცვლის შემდეგ). ალგორითმების მუდმივ სირთულემდე მიყვანა
დაუყოვნებლივ უნდა აღვნიშნო, რომ "შეცდომა" ჩნდება ფორმულაში, თუ, მაგალითად, i1 = 0 (ჩვენ ვითვლით ჯამს n = 0-დან -1-მდე) ან i2 = 1 (ჯამს ვითვლით 1-დან 0-მდე). ფაქტობრივად, ასეთ შემთხვევებში შესაბამისი ჯამი უნდა იქნას მიღებული ნულის ტოლი და შედეგი იქნება სწორი.
ასევე ყურადღება უნდა მივაქციო ჩვენი ალგორითმების დროის სირთულეს: მათ აქვთ წრფივი სირთულე, იმ პირობით, რომ C განიხილავთ მუდმივ დროს. ეს უკვე ბევრად უკეთესია ვიდრე უხეში ძალა.
Მაგრამ სინამდვილეში (ჩვენს შემთხვევაში 52) არაფერი გვიშლის ხელს ალგორითმის მუდმივ სირთულემდე შემცირებაში. ამისთვის გამოვიყენებთ მათემატიკის ცოდნას და ანალიტიკურად გამოვთვლით ყველა თანხას.
მაგალითად, C(2, K) კომბინაციების რაოდენობა, თუ მას „გაფართოვებთ“ K ფორმულის სახით! / ((K-2)! * 2!), იკლებს მე-2 ხარისხის მრავალწევრამდე. და რადგან ის გვაქვს ჯამის ნიშნის ქვეშ, შეგვიძლია გამოვიყენოთ ფორმულები ნატურალური რიგის რიცხვების N-ე ხარისხების ჯამისთვის (იხ. ვიკიპედია) და მივიღოთ მე-3 ხარისხის ერთი პოლინომი. რომელსაც აშკარად აქვს მუდმივი დროის სირთულე. (უფრო მეტიც, „შეცდომა“, რომელიც მე მოვიყვანე ქვესათაურის დასაწყისში, არანაირად არ იჩენს თავს; ფორმულა სწორი რჩება).
ვიმეორებ, ეს ბაზის ნაკრების ფიქსირებული განზომილებისთვის. თუმცა, დარწმუნებული ვარ, რომ მეტაპროგრამირების დახმარებით თქვენ შეგიძლიათ „ასწავლოთ“ შემდგენელი ისე, რომ მან ეს საქმე გააკეთოს თქვენთვის. შემდგომი სიტყვა
ჩემს პოკერის სიმულატორში (ტეხასის ჰოლდემი) მინდოდა წინასწარ გამოვთვალო და შემენახა მოგების ალბათობა ჩემი ხელის ბარათების ყველა შესაძლო კომბინაციისთვის (2 ცალი) და ყველა ფლოპის კარტის (მაგიდაზე 3 ბარათი). ეს შეესაბამება გაყოფას. 52 კომპლექტი 2, 3, 47 ქვეჯგუფით.
გამოთვლილი და შენახული.
მაგრამ როდესაც დადგა დრო, რომ წაიკითხა მონაცემები ფაილიდან კონკრეტული კომბინაციისთვის, მე ნამდვილად არ მინდოდა რაიმეს დიდი ხნის განმავლობაში გამოთვლა ან გიგაბაიტის ფაილში ძებნა. ახლა უბრალოდ ვადგენ ოფსეტს ფაილში და პირდაპირ ვკითხულობ იმას, რაც მჭირდება.
საინტერესო იქნებოდა საცნობარო წიგნის ქონა კომბინატორიული ალგორითმების შესახებ ყველა კომბინატორიული ობიექტისთვის, მათ შორის პერმუტაციების, კომბინაციების, განლაგების, ქვესიმრავლეების, კომბინაციების გამეორებით, განლაგების გამეორებით. აშკარა ფორმულები
ბმულები
ნახეთ, რა არის „კომბინაციების რაოდენობა“ სხვა ლექსიკონებში:
წიგნები