Людині часто доводиться мати справу із завданнями, в яких треба підрахувати число усіх можливих способів розташування деяких предметів або число усіх можливих способів здійснення деякої дії. Наприклад, скількома способами можна утворити чергу із 50 чоловік у касу за квитками в кіно, скількома способами можуть бути розподілені золота, срібна і бронзова медалі на чемпіонаті Європи по футболу? Завдання такого типу називаються комбінаторними. При знаходженні розв'язку в комбінаториці використовуються кілька корисних комбінаторних правил або комбінаторних принципів.
Правило суми, правило добутку і формула включень-виключень часто використовуються для задач підрахунку. Бієктивні доведення використовуються, щоб продемонструвати, що дві множини мають однакову кількість елементів. Принцип Діріхле часто констатує існування чогось або використовується для визначення мінімальної та максимальної кількості чогось у дискретному контексті. Багато виникають з методів [en] або способу виділеного головного елементу. Твірні функції та рекурентні співвідношення є потужними інструментами, які можуть бути використані для дій з послідовністю, і можуть описати багато комбінаторних ситуацій.
Комбінаторні з'єднання
Правило додавання є інтуїтивно положенням про те, що якщо існує A можливих результатів для випадку (або способів зробити щось) і B можливих результатів для іншої події (або способів зробити ще одну річ), і ці дві події не можуть одночасно відбуватися (або ці дві умови не можуть бути виконаними одночасно), тоді існують A + B загально можливих результатів для події (або всі можливі шляхи, щоб зробити одну з речей). Більш формально, сума кількості елементів двох множин, які не перетинаються дорівнює кількості елементів їх об'єднання.
Деяка сукупність елементів вибраних з заданих множин називається вибіркою. Число елементів у вибірці називається довжиною вибірки.
Приклад 1. Нехай дана множина Х — множина цифр, тобто {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Ця множина складається з 10 елементів. Будь-який набір цифр, що складається, наприклад, з 4 цифр буде вибіркою довжини 4.
Зауваження. Деяку сукупність елементів з цієї кінцевої множини можна вибирати по-різному: якщо при складанні вибірки враховується порядок дотримання елементів у вибірці, тоді вибірка називається впорядкованою; якщо ж при складанні вибірки не враховується порядок дотримання елементів в ній, то вибірка називається невпорядкованою; якщо при складанні вибірки в неї може бути включений один і той же елемент кілька разів, то вибірка називається вибіркою з повтореннями; якщо ж елементи входять у вибірку тільки по одному разу, то вибірка називається вибіркою без повторень.
Приклад 2. Нехай дана множина Х — множина цифр, тобто {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Скласти з цифр п'ятизначне число, цифри в якому не повторюються. Цим п'ятизначним числом може бути, наприклад, число 54321. Переставимо цифри в цьому числі, наприклад, так 45321, в результаті отримаємо інше число (іншу вибірку). Таким чином, при зміні порядку дотримання елементів у вибірці, змінюється сама вибірка, тому кожне п'ятизначне число є впорядкованою вибіркою. Оскільки обидва складені числа не мають у складі однакових цифр, ці вибірки є вибірками без повторень. Проте п'ятизначне число, наприклад, 554331 є впорядкованою вибіркою, але з повтореннями.
Приклад 3. Нехай є листівки 6 видів. Скласти з цих листівок набір, що складається з 4 листівок. Кожен набір з 4 листівок буде вибіркою. Якщо ми поміняємо в наборі місцями дві листівки, то від цього набір листівок не змінитися, тобто вибірка залишиться колишньою. Таким чином, при зміні порядку дотримання елементів у вибірці вибірка не міняється, отже, в даному випадку вибірка невпорядкована. Якщо в складеному наборі будуть однакові листівки, то він буде вибіркою з повтореннями, якщо ж усі листівки в наборі будуть різними, то набір буде вибіркою без повторень.
Зауваження. Набір властивостей, які має вибірка (впорядкованість, невпорядкованість, з повтореннями або без повторень) називатимемо характером вибірки. Встановлення характеру вибірки дуже важливе для вирішення комбінаторного завдання.
Правило добутку
Правило множення є ще одним інтуїтивним положенням про те, що якщо є A можливих результатів події та B можливих результатів для іншої події, тоді існують A · В можливих результатів.
Більш формально, якщо дана послідовність k подій з n1 можливими результатами першої, n2 другої, і так далі, аж до nk можливих результатів останньої події, загальне число результатів послідовності k подій дорівнює твору n1* n2*…* nk.
Завдання 1. У невеликій кондитерській до кінця робочого дня залишилося декілька тістечок: чотири ванільних, два шоколадних і три фруктових. Один покупець збирається купити тістечка перед закриттям кондитерської. Скільки тістечок може вибрати покупець?
Завдання 2. Необхідно вибрати змішану команду, яка представлятиме місцевий тенісний клуб на змаганнях. У спортивному клубі полягають 6 жінок і 9 чоловіків. Скільки різних пар можна вибрати для участі в змаганнях?
Завдання 3. Скільки тризначних чисел починаються з 3 або 4?
Перше завдання вирішується простим підрахунком. Оскільки усі тістечка різні, ми просто можемо скласти їх кількості. Це дає 4+2+3 = 9 тістечок, з яких покупець може зробити вибір. У другому завданні у нас є 6 жінок, з яких ми можемо вибрати представницю клубу, і для кожної з них ми можемо підібрати партнера серед дев'яти чоловіків. Таким чином, загальне число різних пар, які ми можемо скласти, рівне 6*9 = 54. Для вирішення третього завдання необхідно використати, як правило, суми, так і твори. Тризначні числа, про які йде мова в завданні, природним чином розбиваються на два класи, що не перетинаються. До одного з них відносяться числа, що починаються з 3, а до другого з 4. Для підрахунку чисел в першому класі помітимо, що існує один можливий результат для першої цифри (вона має дорівнювати 3), 10 результатів для другої і 10 результатів для останньої цифри. За правилом твору отримуємо, що всього чисел в першому класі налічується рівно 1*10*10 = 100. Аналогічно можна підрахувати кількість чисел в другому класі. Воно теж дорівнює 100. Нарешті, за правилом суми отримуємо, що існує 100+100 = 200 тризначних чисел, що починаються з 3 або 4.
Принцип включення-виключення
Принцип включення-виключення пов'язаний з розміром об'єднання декількох множин, розміром кожної множини та розміром кожного можливого перетину множин. Найменший приклад, коли є дві множини: кількість елементів в об'єднанні А і B дорівнює сумі кількості елементів в А і B мінус число елементів їх перетину.
Взагалі, згідно з цим принципом, якщо A1, …, An є кінцеві множини, то
Бієктивне доведення
При знаходженні бієктивної функції (взаємно однозначна відповідність), від одного набору до іншого, бієктивні доведення показують, що дві множини мають однакову кількість елементів.
Метод подвійного обліку
Подвійний облік є методом, який прирівнює два вирази, які підраховують кількість елементів множини двома способами.
Принцип Діріхле
Принцип Діріхле говорить про те, що якщо А елементів розташувати в B ящиках, де A > В, то принаймні один з ящиків буде містити більше одного елемента. За допомогою цього методу можна, наприклад, продемонструвати наявність елемента в наборі з деякими специфічними властивостями.
Метод виділеного головного елементу
Метод виділеного головного елемента виділяє «головний елемент» з набору, щоб довести, якийсь результат.
Твірна функція
Твірну функцію можна розглядати як поліноми з нескінченного числа доданків, коефіцієнти яких відповідають членам послідовності. Це нове уявлення про послідовності відкриває нові методи для пошуку однорідностей та закритих форм, що належать до певних послідовностей. Далі наведена твірна функція загального виду, що генерує послідовність an:
Рекурентне співвідношення
Рекурентне співвідношення визначає кожний член послідовності через попередні члени. Рекурентні співвідношення можуть привести до раніше невідомих властивостей послідовності, але в цілому аналітичний вираз для членів послідовності є більш бажаним.
Список літератури
- J. H. van Lint і R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Lyudini chasto dovoditsya mati spravu iz zavdannyami v yakih treba pidrahuvati chislo usih mozhlivih sposobiv roztashuvannya deyakih predmetiv abo chislo usih mozhlivih sposobiv zdijsnennya deyakoyi diyi Napriklad skilkoma sposobami mozhna utvoriti chergu iz 50 cholovik u kasu za kvitkami v kino skilkoma sposobami mozhut buti rozpodileni zolota sribna i bronzova medali na chempionati Yevropi po futbolu Zavdannya takogo tipu nazivayutsya kombinatornimi Pri znahodzhenni rozv yazku v kombinatorici vikoristovuyutsya kilka korisnih kombinatornih pravil abo kombinatornih principiv Pravilo sumi pravilo dobutku i formula vklyuchen viklyuchen chasto vikoristovuyutsya dlya zadach pidrahunku Biyektivni dovedennya vikoristovuyutsya shob prodemonstruvati sho dvi mnozhini mayut odnakovu kilkist elementiv Princip Dirihle chasto konstatuye isnuvannya chogos abo vikoristovuyetsya dlya viznachennya minimalnoyi ta maksimalnoyi kilkosti chogos u diskretnomu konteksti Bagato vinikayut z metodiv en abo sposobu vidilenogo golovnogo elementu Tvirni funkciyi ta rekurentni spivvidnoshennya ye potuzhnimi instrumentami yaki mozhut buti vikoristani dlya dij z poslidovnistyu i mozhut opisati bagato kombinatornih situacij Kombinatorni z yednannyaDokladnishe Pravilo sumi Pravilo dodavannya ye intuyitivno polozhennyam pro te sho yaksho isnuye A mozhlivih rezultativ dlya vipadku abo sposobiv zrobiti shos i B mozhlivih rezultativ dlya inshoyi podiyi abo sposobiv zrobiti she odnu rich i ci dvi podiyi ne mozhut odnochasno vidbuvatisya abo ci dvi umovi ne mozhut buti vikonanimi odnochasno todi isnuyut A B zagalno mozhlivih rezultativ dlya podiyi abo vsi mozhlivi shlyahi shob zrobiti odnu z rechej Bilsh formalno suma kilkosti elementiv dvoh mnozhin yaki ne peretinayutsya dorivnyuye kilkosti elementiv yih ob yednannya Deyaka sukupnist elementiv vibranih z zadanih mnozhin nazivayetsya vibirkoyu Chislo elementiv u vibirci nazivayetsya dovzhinoyu vibirki Priklad 1 Nehaj dana mnozhina H mnozhina cifr tobto 0 1 2 3 4 5 6 7 8 9 Cya mnozhina skladayetsya z 10 elementiv Bud yakij nabir cifr sho skladayetsya napriklad z 4 cifr bude vibirkoyu dovzhini 4 Zauvazhennya Deyaku sukupnist elementiv z ciyeyi kincevoyi mnozhini mozhna vibirati po riznomu yaksho pri skladanni vibirki vrahovuyetsya poryadok dotrimannya elementiv u vibirci todi vibirka nazivayetsya vporyadkovanoyu yaksho zh pri skladanni vibirki ne vrahovuyetsya poryadok dotrimannya elementiv v nij to vibirka nazivayetsya nevporyadkovanoyu yaksho pri skladanni vibirki v neyi mozhe buti vklyuchenij odin i toj zhe element kilka raziv to vibirka nazivayetsya vibirkoyu z povtorennyami yaksho zh elementi vhodyat u vibirku tilki po odnomu razu to vibirka nazivayetsya vibirkoyu bez povtoren Priklad 2 Nehaj dana mnozhina H mnozhina cifr tobto 0 1 2 3 4 5 6 7 8 9 Sklasti z cifr p yatiznachne chislo cifri v yakomu ne povtoryuyutsya Cim p yatiznachnim chislom mozhe buti napriklad chislo 54321 Perestavimo cifri v comu chisli napriklad tak 45321 v rezultati otrimayemo inshe chislo inshu vibirku Takim chinom pri zmini poryadku dotrimannya elementiv u vibirci zminyuyetsya sama vibirka tomu kozhne p yatiznachne chislo ye vporyadkovanoyu vibirkoyu Oskilki obidva skladeni chisla ne mayut u skladi odnakovih cifr ci vibirki ye vibirkami bez povtoren Prote p yatiznachne chislo napriklad 554331 ye vporyadkovanoyu vibirkoyu ale z povtorennyami Priklad 3 Nehaj ye listivki 6 vidiv Sklasti z cih listivok nabir sho skladayetsya z 4 listivok Kozhen nabir z 4 listivok bude vibirkoyu Yaksho mi pominyayemo v nabori miscyami dvi listivki to vid cogo nabir listivok ne zminitisya tobto vibirka zalishitsya kolishnoyu Takim chinom pri zmini poryadku dotrimannya elementiv u vibirci vibirka ne minyayetsya otzhe v danomu vipadku vibirka nevporyadkovana Yaksho v skladenomu nabori budut odnakovi listivki to vin bude vibirkoyu z povtorennyami yaksho zh usi listivki v nabori budut riznimi to nabir bude vibirkoyu bez povtoren Zauvazhennya Nabir vlastivostej yaki maye vibirka vporyadkovanist nevporyadkovanist z povtorennyami abo bez povtoren nazivatimemo harakterom vibirki Vstanovlennya harakteru vibirki duzhe vazhlive dlya virishennya kombinatornogo zavdannya Pravilo dobutkuDokladnishe Pravilo mnozhennya Pravilo mnozhennya ye she odnim intuyitivnim polozhennyam pro te sho yaksho ye A mozhlivih rezultativ podiyi ta B mozhlivih rezultativ dlya inshoyi podiyi todi isnuyut A V mozhlivih rezultativ Bilsh formalno yaksho dana poslidovnist k podij z n1 mozhlivimi rezultatami pershoyi n2 drugoyi i tak dali azh do nk mozhlivih rezultativ ostannoyi podiyi zagalne chislo rezultativ poslidovnosti k podij dorivnyuye tvoru n1 n2 nk Zavdannya 1 U nevelikij konditerskij do kincya robochogo dnya zalishilosya dekilka tistechok chotiri vanilnih dva shokoladnih i tri fruktovih Odin pokupec zbirayetsya kupiti tistechka pered zakrittyam konditerskoyi Skilki tistechok mozhe vibrati pokupec Zavdannya 2 Neobhidno vibrati zmishanu komandu yaka predstavlyatime miscevij tenisnij klub na zmagannyah U sportivnomu klubi polyagayut 6 zhinok i 9 cholovikiv Skilki riznih par mozhna vibrati dlya uchasti v zmagannyah Zavdannya 3 Skilki triznachnih chisel pochinayutsya z 3 abo 4 Pershe zavdannya virishuyetsya prostim pidrahunkom Oskilki usi tistechka rizni mi prosto mozhemo sklasti yih kilkosti Ce daye 4 2 3 9 tistechok z yakih pokupec mozhe zrobiti vibir U drugomu zavdanni u nas ye 6 zhinok z yakih mi mozhemo vibrati predstavnicyu klubu i dlya kozhnoyi z nih mi mozhemo pidibrati partnera sered dev yati cholovikiv Takim chinom zagalne chislo riznih par yaki mi mozhemo sklasti rivne 6 9 54 Dlya virishennya tretogo zavdannya neobhidno vikoristati yak pravilo sumi tak i tvori Triznachni chisla pro yaki jde mova v zavdanni prirodnim chinom rozbivayutsya na dva klasi sho ne peretinayutsya Do odnogo z nih vidnosyatsya chisla sho pochinayutsya z 3 a do drugogo z 4 Dlya pidrahunku chisel v pershomu klasi pomitimo sho isnuye odin mozhlivij rezultat dlya pershoyi cifri vona maye dorivnyuvati 3 10 rezultativ dlya drugoyi i 10 rezultativ dlya ostannoyi cifri Za pravilom tvoru otrimuyemo sho vsogo chisel v pershomu klasi nalichuyetsya rivno 1 10 10 100 Analogichno mozhna pidrahuvati kilkist chisel v drugomu klasi Vono tezh dorivnyuye 100 Nareshti za pravilom sumi otrimuyemo sho isnuye 100 100 200 triznachnih chisel sho pochinayutsya z 3 abo 4 Princip vklyuchennya viklyuchennyaPrincip vklyuchennya viklyuchennya pokazani na tri komplekti Dokladnishe Formula vklyuchen viklyuchen Princip vklyuchennya viklyuchennya pov yazanij z rozmirom ob yednannya dekilkoh mnozhin rozmirom kozhnoyi mnozhini ta rozmirom kozhnogo mozhlivogo peretinu mnozhin Najmenshij priklad koli ye dvi mnozhini kilkist elementiv v ob yednanni A i B dorivnyuye sumi kilkosti elementiv v A i B minus chislo elementiv yih peretinu Vzagali zgidno z cim principom yaksho A1 An ye kincevi mnozhini to i 1 n A i i 1 n A i i j 1 i lt j n A i A j i j k 1 i lt j lt k n A i A j A k 1 n 1 A 1 A n displaystyle begin aligned biggl bigcup i 1 n A i biggr amp sum i 1 n left A i right sum i j 1 leq i lt j leq n left A i cap A j right amp qquad sum i j k 1 leq i lt j lt k leq n left A i cap A j cap A k right cdots left 1 right n 1 left A 1 cap cdots cap A n right end aligned Biyektivne dovedennyaDokladnishe Biyektivne dovedennya Pri znahodzhenni biyektivnoyi funkciyi vzayemno odnoznachna vidpovidnist vid odnogo naboru do inshogo biyektivni dovedennya pokazuyut sho dvi mnozhini mayut odnakovu kilkist elementiv Metod podvijnogo oblikuDokladnishe Podvijnij oblik ye metodom yakij pririvnyuye dva virazi yaki pidrahovuyut kilkist elementiv mnozhini dvoma sposobami Princip DirihleDokladnishe Princip Dirihle Princip Dirihle govorit pro te sho yaksho A elementiv roztashuvati v B yashikah de A gt V to prinajmni odin z yashikiv bude mistiti bilshe odnogo elementa Za dopomogoyu cogo metodu mozhna napriklad prodemonstruvati nayavnist elementa v nabori z deyakimi specifichnimi vlastivostyami Metod vidilenogo golovnogo elementuDokladnishe Metod vidilenogo golovnogo elementa vidilyaye golovnij element z naboru shob dovesti yakijs rezultat Tvirna funkciyaDokladnishe Generatrisa Tvirnu funkciyu mozhna rozglyadati yak polinomi z neskinchennogo chisla dodankiv koeficiyenti yakih vidpovidayut chlenam poslidovnosti Ce nove uyavlennya pro poslidovnosti vidkrivaye novi metodi dlya poshuku odnoridnostej ta zakritih form sho nalezhat do pevnih poslidovnostej Dali navedena tvirna funkciya zagalnogo vidu sho generuye poslidovnist an G a n x n 0 a n x n displaystyle G a n x sum n 0 infty a n x n Rekurentne spivvidnoshennyaDokladnishe Rekurentne spivvidnoshennya Rekurentne spivvidnoshennya viznachaye kozhnij chlen poslidovnosti cherez poperedni chleni Rekurentni spivvidnoshennya mozhut privesti do ranishe nevidomih vlastivostej poslidovnosti ale v cilomu analitichnij viraz dlya chleniv poslidovnosti ye bilsh bazhanim Spisok literaturiJ H van Lint i R M Wilson 2001 A Course in Combinatorics Paperback 2nd edition Cambridge University Press ISBN 0 521 00601 5