ОСНОВНІ ТИПИ ЗАДАЧ КОМБІНАТОРИКИ   

         Комбінаторика – розділ математики, в якому вивчаються питання про те, скільки різних комбінацій, підлеглим тим чи іншим умовам, можна скласти з даних об’єктів.

        Вибором об’єктів і розміщенням їх в тому чи іншому порядку приходиться займатися чи не у всіх областях людської діяльності, наприклад  конструктору,що розробляє нову модель механізму, вченому – агроному, плануючому розподіл сільськогосподарських культур на декількох полях, хіміку, що вивчає будову органічних молекул, що мають даний атомний склад.

        З аналогічними задачами, що отримали назву комбінаторних, люди зіштовхнулись в глибокій давнині. Декілька тисячоліть тому в Стародавньому Китаї  захоплювалися складанням магічних квадратів, в яких задані числа розподіляли так, що їх сума по всім горизонталям і вертикалям та головним діагоналям була однією і тою ж. В Стародавній Греції підраховували число різних комбінацій  довгих і коротких складів в віршових розмірах, займалися теорією фігурних чисел, вивчали фігури, які можна скласти з частин певним чином розрізаного квадрата, і т. д.

        Комбінаторні задачі виникали і в зв’язку з такими іграми, як шашки, шахи, доміно і т.д. (Наприклад, задача про розміщення восьми ферзів на шаховій  дошці так, щоб жоден з них не опинився під боєм, про обхід шахової дошки шаховим конем і т. д.

        Комбінаторика стає наукою лише в ХVIII столітті в період, коли виникла теорія ймовірностей. Щоб розв’язувати теоретично – ймовірнісні задачі, треба було вміти підраховувати число різних комбінацій, підлеглим тим чи іншим умовам. Після перших робіт, виконаних в XVI столітті  італійськими вченими Дж. Кардано, Н. Тартальє і Г. Галілеєм, такі задачі вивчали французькі математики Б. Паскаль і П. Ферма. Першим розглядав комбінаторику як самостійну гілку науки німецький філософ і математик Г. Лейбніц, який опублікував у 1666 р. роботу “ Про мистецтво комбінаторики”, в якій вперше появляється термін “комбінаторний”. Чудові відкриття в області комбінаторики належать  Л.Ейлеру. До комбінаторних задач мали інтерес і математики, що займалися складанням і розгадуванням шифрів, вивчанням стародавніх письменностей. Зараз комбінаторика застосовується в багатьох областях науки: в біології, де вона застосовується для вивчення складу білків та ДНК, в хімії, в механіці складних споруд і т.д.

        По мірі розвитку комбінаторики виявилось, що, незважаючи на зовнішню відмінність досліджуваних нею питань, багато з них мають один і той самий математичний зміст і зводяться до задач про скінченні множини та їх підмножини. Поступово виявилось кілька основних типів задач, до яких зводиться більшість комбінаторних проблем.

1.  ОСНОВНА ЛЕМА КОМБІНАТОРИКИ

        Лема: Якщо множина А складається з n елементів, а множина В – з m елементів, то можна скласти рівно n∙m пар виду (a_i,b_j), де а_і Є А, b_j Є В.

        Наслідок: Якщо множина А₁ складається з n₁ елементів, А₂ – з n₂ елементів , … , А_к – з n_k елементів,  то число послідовностей (a_i1 ,a_i2 ,…,a_ik ), де а_і1 Є А_1, ,…,а_ікЄ А_к ,дорівнює n₁n₂ …n_{k .}

          Твердження леми і наслідок можна розуміти таким чином: якщо для заповнення першого місця послідовності  елементом з множини А₁ маємо n₁ можливостей, другого місця – елементом з множини А₂ – n₂ можливостей, … ,k-го місця  –  елементом  з множини А_к –  n_k можливостей, то всього таких послідовностей буде n₁n₂…n_k.

        Задача 1. На паралельних прямих а і в розміщено n і m точок відповідно. Скільки існує відрізків, що з’єднують точки прямих а і в ? 

        Розв’язання: Нехай а₁, а₂, …, а_n – точки на прямій а, в₁, в₂, …,в_m— точки на прямій в. Для кожної точки а_і матимемо m відрізків, що сполучають цю точку з точками прямої в. Кожному відрізку відповідатиме пара (а_і ,в_j). За основною лемою комбінаторики таких пар буде nm.

      Задача 2.  На сторонах АВ і ВС трикутника АВС взято точки

P₁, P₂, … , P_n і Q₁, Q₂, …. , Q_m  відповідно. Проведено відрізки AQ_j і CP_i . Скільки будемо мати точок перетину цих відрізків ? На скільки частин поділиться трикутник цими відрізками ?

     Відповідь: nm; (n+1)(m+1).

Задача 3. У просторі ( або на площині ) взято n синіх точок , m червоних та k зелених точок. Скільки існує відрізків з кінцями різного кольору ?

        Розв’язання: Не обмежуючи загальності, розмістимо точки на паралельних прямих a, b, с відповідно по n, m, k штук. За результатами задачі 1 кількість відрізків дорівнюватимете nm+mk+kn.

        Відповідь: nm + mk + kn.

     Задача 4. Світланці на день народження подарували 4 плюшевих іграшки, 2 м’ячі і 5 ляльок (іграшки, м’ячі і ляльки різні ). Мама поклала все це у велику коробку. Скількома способами Світлана може дістати набір з 1 іграшки, 1 м’яча і 1 ляльки ?

        Розв’язання: Світланка має 4 варіанти вибору плюшевих іграшок, 2 варіанти вибору м’ячів та 5 варіантів вибору ляльок. Тому загальна кількість варіантів за наслідком з леми буде дорівнювати 4∙2∙5=40 варіантів.

        Відповідь: 40 варіантів.  

     Задача 5. Скільки парних двозначних чисел можна скласти з цифр 0,2,3,6,7,9 ?

        Розв’язання: Для вибору першої цифри є 5 можливостей (цифри 2,3,6,7,9. Нуль на першому місці стояти не може). Для вибору другої цифри числа є 3 можливості (цифри 0,2,6 – ознака по-дільності на 2).

        Відповідь: 5∙3=15 чисел.

     Задача 6. Скільки існує чотирицифрових чисел, що діляться на 5, записаних за допомогою цифр: а) 1,2,3, … ,8,9; б) 0,1,…,9 ?

        Розв’язання: а) Для запису перших трьох цифр числа на місце кожної цифри є по 9 можливостей. На місце останньої цифри – одна можливість – цифра 5. Остаточно   матимемо  9∙9∙9∙1= 729 чисел; б) 9∙10∙10∙2=1800 чисел.

        Відповідь: 729, 1800.            

      Задача 7. Скільки чотирицифрових натуральних чисел, які діляться на 25, можна записати, використавши цифри

2,3,4,5,6,7,8 ?

        Розв’язання: Ознака подільності на 25: запис числа повинен закінчуватися парою цифр 00, 25, 50, 75. У нашому випадку можливі тільки пари 25 і 75. Тому будемо мати 7∙7∙2∙1=98 чисел.

        Відповідь: 98 чисел.

     Задача 8. Міс Марпл, розслідуючи вбивство, замітила від’їжджаюче від дому містера Девідсона таксі. Вона запам’ятала першу цифру 2 номера машини. В місті номери машин були чотирьохзначними і складалися з цифр 1,2,3,4,5. Після цифр йшли дві букви з множини букв A,B,C,D. Скількох водіїв у найгіршому випадку їй прийдеться опитати, щоб знайти справжнього злочинця

?

        Відповідь: (1∙5∙5∙5)∙(4∙4)=2000 водіїв. 

2. ПЕРЕСТАНОВКИ

     Задача 9. Нехай М – множина, що складається з n елементів :  М={a₁,a₂, … , a_n}. Скількома способами можна лінійно упорядкувати цю множину, тобто розмістити її елементи один за одним, утворити з них n-членну послідовність, в якій жодний елемент з М не повторюється ?  

        Розв’язання: Для вибору першого члена послідовності маємо n можливостей ( будь-який елемент з М ). Незалежно від того, який елемент з М взято як перший член послідовності, для вибору її другого члена  у нашому розпорядженні буде (n-1) можливостей ( будь-який елемент з М, крім використаного на першому кроці ). Взагалі, якщо перші k членів послідовності вже вибрано, то для вибору її (k+1)-го члена буде (n-k)  можливостей. Тому згідно з наслідком основної леми комбінаторики ( комбінаторного правила множення ) з елементів множини М всього можна побудувати n(n1)(n-2)∙…∙3∙2∙1 різних n-членних послідовностей. Цей добуток коротко позначають через n!.

        Лінійно упорядковані скінченні множини називаються перестановками. Тому останній результат можна сформулювати так: з n елементів можна утворити n! різних перестановок. Число всіх перестановок будемо позначати символом Р_n. Отже,

Р_n = n!                                     (1)

     Задача 10. Олександр, Іван, Петро, Денис, Оля та Настя часто ходять в кафе. Кожен раз, обідаючи там, вони розсаджуються порізному. Скільки днів друзі можуть це зробити без повтору ?

        Відповідь: 6!=6∙5∙4∙3∙2∙1=720 днів (приблизно два роки !!!).

     Задача 11. Десять чоловік сідають за круглий стіл. Два розміщення по місцям будемо вважати однаковими, якщо кожна людина має одних і тих самих сусідів в обох випадках. Скільки існує способів сісти за стіл ?

        Розв’язання: Загальне число перестановок дорівнює 10!. Але відношення сусідства буде зберігатися, якщо усі 10 чоловік разом встануть і пересядуть на місце, наприклад, правого сусіда. Таких пересадок можна зробити 10 разів, поки люди не сядуть на ті ж самі місця. Так само сусіди будуть ті ж самі при симетричному відображенні. Тому всього способів (10!⁄10): 2 = 9!:2 = 181440.

        Відповідь: 181440 способів.

     Задача 12. Скількома способами можна посадити за круглий стіл 5 чоловіків і 5 жінок так, щоб ніякі дві особи однієї статі не сиділи поряд ?

        Розв’ язання: Перенумеруємо місця від 1 до 10-ти. Для жінок і чоловіків можна вибрати місця двома способами – місця з парними номерами, або місця з непарними номерами. Після цього чоловіків на обраних місцях можна посадити 5! способами. На інших місцях 5! способами можна посадити жінок. Всього 2∙(5!)²

способів.

        Відповідь: 2∙(5!)²= 28800 способів.

     Задача 13. На книжній полиці n=10 книжок. Скількома способами  можна переставити книги на полиці так, щоб m=3 виділених книг були поряд в будь-якому порядку ?

        Розв’язання: Зв’яжемо m виділених книг в групу і будемо рахувати їх як одну книгу. Всього перестановок із зв’язаними книгами буде         (n-m+1)!. Так як зв’язані між собою m книг теж можна  переставити m! способами, то остаточно матимемо  (nm+1)!m! способів.

         Відповідь: (n-m+1)!m! способів. Якщо n=10, m=3, то

8!∙3!=241920 способів.

3. ЧИСЛО РОЗМІЩЕНЬ З n  ЕЛЕМЕНТІВ ПО  k 

     Задача 14. Нехай М={a₁, a₂,…,a_n}. Лінійно впорядковані kелементні підмножини (або послідовності, 0≤k≤n) множини М називають k-розміщенням елементів цієї множини. Число всіх таких розміщень позначають 𝐴^𝑘_𝑛 . Чому дорівнює це число ?

        Розв’язання: Будь-яке k-розміщення (α₁,α₂,…,α_k) можна дістати за допомогою такої послідовної процедури: спочатку вибираємо з множини М перший елемент k-розміщення α₁ (це можна зробити n різними способами), потім вибираємо елемент α₂ (n-1 можливостей), потім α₃ (n-2 можливостей) і, нарешті, α_k (nk+1  мож-ливостей). Згідно з комбінаторним правилом множення в підсумку матимемо: 

𝐴^𝑘_𝑛= n(n-1)(n-2)∙…∙(n-k+1) = _(𝑛−^𝑛!_𝑘)!         (2)

Щоб ця формула була правильною для k=n, вважаємо 0!=1.

Зокрема 𝐴^𝑛_𝑛 = P_n.

     Задача 15. Скількома способами можна скласти трьохкольоровий прапор, якщо є матерії 8-ми різних кольорів ?

        Розв’язання: Оскільки на прапорі використовуються різні кольори і порядок їх важливий, то кожному прапору відповідає одне з розміщень з 8 елементів по 3. Число всіх можливих прапорів вказаного виду дорівнює А

        Відповідь: 336 способів.

     Задача 16. Скільки є п’ятицифрових чисел, записаних за допомогою цифр а) 1,2,…,9 ;           б) 0,1,2,…,9 , якщо цифри числа не повторюються ?

        Розв’язання: а) на першому місці запису п’ятицифрового числа може стояти одна з дев’яти даних цифр, на другому – одна з восьми і т.д. Тому у відповіді матимемо число розміщень з 9 елементів по 5: А у випадку а), але враховуючи те, що нуль не може бути першим у запису числа, отримаємо таку відповідь: 9∙9∙8∙7∙6 = 27216 чисел.  

        Цю ж саму відповідь можна отримати, міркуючи так:

Знайдемо всі розміщення 5-ти цифр з 10-ти : А₁₀⁵ -- усі  п’ятизначні числа, враховуючи на першому місці нуль. Відкинемо тепер ті, на першому місці у яких є нуль. Їх буде А⁴₉  . Матимемо: 

А

       Відповідь: 27216 чисел.

        Зупинимося ще на цій задачі, змінивши її умову. Нехай цифри числа можуть повторювати-ся. Тоді у випадку а) на кожному місці цифр числа може стояти будь-яка з дев’яти цифр, тому будемо мати  9∙9∙9∙9∙9=9⁵=59049 чисел.  

        Будь-який впорядкований набір k елементів з множини М={a₁,a₂,…,a_n}   називається розміщенням з повтореннями.

Число різних розміщень з повтореннями дорівнює   

𝐴^𝑘_(𝑛) =  n^k                  (3)

       У випадку б) попередньої задачі з умови, що цифри числа

можуть повторюватися-

𝐴⁴₍10).

     Задача 17. В кабінеті завідуючого ювелірним магазином  є код, що складається з двох різних голосних букв українського алфавіту (не йотованих), за якими слідують три різні цифри. Скільки варіантів у найгіршому випадку прийдеться перебрати злодію, щоб добути коштовності, які там зберігаються ?

        Розв’язання: Голосних не йотованих букв в українському алфавіті 6, цифр – 10. Записати дві різні букви з шести можна 𝐴²₆ способами, три різні цифри з десяти 𝐴₁₀³ способами. За комбінаторним правилом множення матимемо:

𝐴²₆∙𝐴₁₀³ = (6∙5)∙(10∙9∙8)=21600 варіантів.

        Відповідь: 21600 варіантів.

        Зокрема, якби в задачі не наголошувалось про те, що цифри і букви різні, було б 𝐴 =36000 варіантів перебору.

     Задача 18. В студентському гуртожитку в одній кімнаті живуть троє студентів. В них є 6 чашок, 8 блюдець і 10 ложечок (всі приналеж-ності відрізняються одне від одного). Скількома способами хлопці можуть накрити стіл для чаювання ?

        Розв’язання:  1 спосіб. Для одного з студентів з 6 чашок, 8 блюдець і 10 ложечок існує 6∙8∙10 способів вибору. Після того, як для цього студента набір готовий, для другого студента є 5∙7∙9 способів вибору. І нарешті, третій студент матиме 4∙6∙8 способів вибору. За комбінаторним правилом множення матимемо

(6∙8∙10)(5∙7∙9)(4∙6∙8) способів накриття столу для чаювання.   

        Розв’язання: 2 спосіб. 6 чашок між трьома студентами можна розподілити А³₆ способами, 8 блюдець А³₈ способами, 10 ложечок

А₁₀³      спо-собами.       За       правилом       добутку       матимемо

А

        Відповідь: 8∙10! способів.

        4.  ЧИСЛО КОМБІНАЦІЙ З n ЕЛЕМЕНТІВ ПО k

Позначимо через С^𝑘_𝑛 кількість невпорядкованих kелементних послідовностей   (підмножин)   n-елементної множини(0≤k≤n). Оскільки кожну k-елементну множину можна впорядку-вати k! способами, то

𝐶_𝑛^𝑘 = 𝐴^𝑘_𝑛/k! = _𝑘!(𝑛^𝑛₋^! _𝑘)! (4)

        Щоб детальніше зрозуміти суть цього числа, розглянемо такий приклад на основі двох задач.

     Приклад. Задача (1). Скільки різних тризнач-них чисел можна записати за допомогою цифр 1,2,3,4,5 ? Відповідь: А

60.

           Задача (2). На площині є 5 точок, жодні три з них не лежать на одній прямій. (Такі точки дуже зручно розміщати на колі ). Скільки існує трикутників з вершинами у цих точках ?

        Розв’язання:                           

Перенумеруємо точки номерами 1,2,3,4,5. Кожному трикутнику ставиться у відповідність трійка чисел. Наприклад, трикутник (2,4,5). Цей трикутник можна назвати і інакше, а саме: (2,5,4), (5,2,4), (5,4,2), (4,2,5), (4,5,2). Усі ці 3!=6 назв є тим самим трикутником, хоча в задачі (1) числа 245, … , 452 різні. Тому в результаті матимемо С³₅ = А³₅/3! = = 10 трикутників.

        Отже, у числі 𝐴^𝑘_𝑛 порядок елементів послідовності чисел важливий, у числі С^𝑘_𝑛 – порядок не важливий (!!!).

        Саме на число комбінацій існує найбільше задач, особливо геометричного змісту. На дея-ких з них зараз і зупинимося.

        Примітка: Відповідно формулі (4) 𝐶_𝑛^𝑘=𝐶_𝑛^𝑛−𝑘.

     Задача 19. Скільки діагоналей у опуклого n-кутника ?

        Розв’язання: Не обмежуючи загальності, припустимо, що nкутник можна вписати в коло. Отже, n вершин многокутника належать колу. Дізнаємося, скільки відрізків сполучають ці точки. Перенумеруємо точки номерами 1,2,…,n. Кожному відрізку відповідатиме пара (i,j)=(j,i). Тому кількість відрізків буде 𝐶_𝑛² =

𝑛(𝑛−1)

. Відкинемо тепер n відрізків – сторони многокутника.

2

Кількість діагоналей даного многокутника дорівнюватиме

𝐶𝑛2 - n = 𝑛(𝑛2−3) .

𝑛(𝑛−3)

        Відповідь:  діагоналей.

2

     Задача 20. На колі взято n точок і сполучено їх відрізками так, що жодні три з них не перетинаються в одній точці. Скільки існує точок перети-ну цих відрізків ?

Розв’язання: Перенумеруємо точки кола. Кожній точці перетину двох відрізків ставиться у відповідність четвірка чисел (s,t,u,v), яка для цієї точки єдина. Так як порядок чисел s, t, u, v не суттєвий, маємо число комбінацій з n елементів по 4.

Відповідь: 𝐶𝑛4 = 𝑛(𝑛−1)(𝑛24−2)(𝑛−3).

     Задача 21. У просторі взяли n червоних (Ч) і m синіх (С) точок, причому жодні 4 з них не лежать в одній площині.

1)  Скільки є відрізків типу (СЧ) – один кінець синя точка, другий – червона ?

2)  Скільки є відрізків типу а)(СС), б)(ЧЧ) ?

3)  Скільки є трикутників типу а)(ССС), б)(ЧЧЧ), в)(ССЧ), г)(СЧЧ) ?

4)  Скільки є тетраедрів типу а)(СССС), б)(СССЧ), в)(ССЧЧ) ?

        Розв’язання: 1) mn.

2)   a) 𝐶_𝑚² , б)𝐶_𝑛².

3)   a)𝐶_𝑚³ , б)𝐶_𝑛³,

в) Для кожної червоної вершини  існує 𝐶_𝑚² про-тилежних сторін із синіми кінцями. Тому маємо  𝐶_𝑚² трикутників. г)  m𝐶_𝑛² трикутників.

4)   Аналогічно міркуючи, маємо: а)𝐶_𝑚⁴ , б)n𝐶_𝑚³ , в) 𝐶_𝑛²∙𝐶_𝑚² .

     Задача 22. На одній стороні трикутника взяли n точок, на другій – m точок і на третій k точок, причому жодна з них не збігається з вершинами трикутника.

Скільки є трикутників з вершинами в цих точках ?     Скільки є чотирикутників з вершинами в цих точках ?    

    Розв’язання: 1)  Всього комбінацій з  n+m+k точок по три є 𝐶_𝑛³_+𝑚+𝑘. Але серед цих точок жодні три не повинні лежати на одній прямій. Тому ми повинні виключити з загальної кількості комбінацій числа 𝐶_𝑛³, 𝐶_𝑚³ , 𝐶_𝑘³ − комбінації точок,що лежать    на сторонах трикутника. Отримаємо результат: S₁ =  𝐶_𝑛³_+𝑚+𝑘 - 𝐶_𝑛³ -

𝐶_𝑚³ - 𝐶_𝑘³. ( Зрозуміло, якщо j≤2, то 𝐶_𝑗³ = 0 ). Можна міркувати поіншому. Підрахуємо трикутники з вершинами на кожній стороні даного трикутника. Їх буде mnk. Зафіксуємо одну вершину на

стороні (n).  З стороною (m) матимемо 𝐶_𝑚² , а з стороною (k) - 𝐶_𝑘² трикутників. Так як на стороні (n) n точок, то всього буде n(𝐶 ²_𝑚+𝐶_𝑘²) трикутників. Аналогічно для сторін (m)  і  (k) матимемо ще m(𝐶_𝑛²+𝐶_𝑘²) i k(𝐶_𝑛²+𝐶_𝑚² ) трикутників. Всього тепер

S₂ = mnk + n(𝐶_𝑚² +𝐶_𝑘²) + m(𝐶_𝑛²+𝐶_𝑘²) + k(𝐶_𝑛²+𝐶_𝑚² ) =

= mnk + (n+k)𝐶_𝑚² + (m+k)𝐶_𝑛² + (n+m)𝐶_𝑘²  трикутни-ків.  

        Числа S₁ i S₂ рівні між собою, що можна перевірити за допомогою елементарних перетворень.

2)Чотирикутників з вершинами в даних точках буде 𝐶_𝑛⁴_+𝑚+𝑘 - (𝐶_𝑛⁴ + 𝐶_𝑚⁴ + 𝐶_𝑘⁴) – ((m+k)𝐶_𝑛³ + (k+n)𝐶_𝑚³ + (n+m)𝐶_𝑘³).

     Задача 23. В ювелірну майстерню привезли 6 смарагдів, 9 алмазів та 7 сапфірів. Ювеліру замовили браслет, в якому 3 смарагди, 5 алмазів і 2 сапфіри. Скількома способами він може вибрати каміння на браслет ?

        Відповідь: С.

     Задача 24. 20 карток для гри в лото роздаються чотирьом гравцям, по 5 карток кожному. Скількома способами можна роздати ці картки ?

        Розв’язання: Першому гравцю, який має отримати 5 карток з 20-ти є  С⁵₂₀ можливостей вибору. Для другого гравця треба вибрати 5 карток з 15-ти тих, що залишились, тобто С₁₅⁵ способами, для третього гравця будемо мати С₁₀⁵ варіантів вибору, а для четвертого є 1=С⁵₅ варіант вибору. За комбінаторним правилом множення 20 карток чотирьом гравцям можна роздати

С способами.

        Відповідь: 20!⁄(5!)⁴ способів.

     Задача 25. У розіграші першості з футболу  було зіграно 153 матчі. Кожні дві команди зустрічалися між собою один раз. Скільки команд приймали участь у розіграші першості ?

        Розв’язання: Розв’яжемо рівняння:  𝐶_𝑛²=153, n²-n-306=0, n=18.

        Відповідь: 18 команд.

     Задача 26. Довести, що  = 2ⁿ.

        Доведення: Нехай М={a₁,a₂,…,a_n}. Будь-якій підмножині Р, що належить М поставимо у відповідність послідовність довжини n, місця в якій зайняті нулем або одиницею, причому, якщо і-й елемент належить множині Р, на і-му місці стоїть одиниця, якщо ні – то нуль. Наприклад, підмножині Р₁={a₁,a₂,a₄} відповідає послідовність {1,1,0,1,0,…,0}. Таким чином між множиною таких послідовностей  та множиною усіх підмножин існує взаємнооднозначна відповідність. Зокрема порожній множині відповідає послідовність з усіх нулів, самій множині М – послідовність з одиниць. Оскільки для заповнення кожного місця послідовності маємо 2 можливості, то відповідно з комбінаторним правилом множення отримуємо, що число послідовностей такого типу, і отже, число всіх підмножин дорівнює ⏟  = 2ⁿ.

𝑛

       З іншого боку, існує С⁰_𝑛 підмножин, що не містять жодного елемента, С¹_𝑛 підмножин з одним елементом, … , С^𝑘_𝑛 підмножин, що містять k елементів, і т. д. Тому існує всього 𝐶_𝑛⁰+𝐶_𝑛¹+𝐶_𝑛²+…+𝐶_𝑛^𝑛 підмножин. Отже, 2ⁿ = ∑^𝑛_𝑘=0 𝐶_𝑛^𝑘.

     Задача 27. Відомо, що крокодил має не більше 68 зубів. Довести, що серед  16¹⁷ крокодилів може не знайтися двох крокодилів з одним і тим самим набором зубів.

        Доведення: Підрахуємо максимальне число крокодилів з різними наборами зубів. Їх число дорівнює числу всіх підмножин у 68-елементній множині, тобто дорівнює 2⁶⁸=16¹⁷. Ясно, якщо крокодилів більше 16¹⁷, то серед них обов’язко-во знайдуться по крайній мірі два з одним і тим самим набором зубів.

     Задача 28. Букви азбуки Морзе представ-ляють собою набір точок і тире. Скільки букв може бути в азбуці Морзе, якщо буква не повинна мати більше 4-х знаків ?

        Розв’язання: Різних букв, у запису яких вико-ристовуються k символів, буде стільки, скільки існує підмножин k-елементної множини. Їх, як відомо, 2^k. За умовою задачі загальна кількість букв дорівнюватиме 2+2²+2³+2⁴ = 30.

        Відповідь: 30 букв.

5.  ПЕРЕСТАНОВКИ З ПОВТОРЕННЯМ

        Якщо розглядати впорядковані k-елементні підмножини (послідовності) з множини М, то отримаємо перестановки з повторенням.

     Приклад 1. Скількома способами можна переставити букви слова МАМА так, щоб отримати різні “слова”. Можливі перестановки такі: ММАА, МААМ, ААММ, АМАМ, АММА.

     Приклад 2. Скільки існує п’ятизначних чисел, що складаються з двох одиниць, двох двійок і однієї трійки ? Попробуємо записати всі ці числа.

11223 22113  12213  21123  12123  21213

11232 22131  12231  21132  12132  21231

11322 22311  12321  21312  12312  21321

13122 23211  13221  23112  13212  23121

31122 32211  31221  32112  31212  32121

Якби повтору цифр не було, то ми б отримали 5!=120 чисел. В нашому випадку ми отримали в 4 рази менше чисел. Чому ? Помінявши місцями в будь-якому числі з нашого прикладу дві одиниці або дві двійки, ми отримаємо одне й те ж число. Кількість перестановок з двох елементів дорівнює 2!=2. Тих елементів, під час перестановки яких число не змінюється – дві пари – (1,1) і (2,2). Тому загальна кількість перестановок буде у 2!∙2! рази менше, тобто .

        Введемо тепер означення числа перестановок з повторенням.

        Нехай М={a₁,a₂,…,a_n}—непорожня множина з n елементів, і і₁,і₂,…,і_n – натуральні числа такі, що їх сума дорівнює певному числу k. Кожний упорядкований набір k чисел, що містить в собі елемент a_j  рівно i_j раз (1≤j≤n), називається перестановкою множини М з повторенням.

        Примітка:       При і₁=і₂=…=і_n=1, отримаємо      перестановки множини з n елементів. 

Число Р_к(і₁,і₂,…,і_n) різних перестановок множини М з повторенням дорівнює

Р_к(і₁,і₂,…,і_n) = 𝑘!⁄(𝑖₁!∙i₂!∙…∙i_n!), де ∑ 𝑖_j = k.     (5)

У прикладі 1   М = {М,А}, і₁=2 – двічі зустрічається буква М, і₂=2 – двічі зустрічається буква А. Р₄(2,2) =  = 6.

!

У прикладі 2   М={1,2,3}, і₁=2 – дві цифри 1, і₂=2 – дві цифри 2, і₃=1 – одна трійка.

Р₅(2,2,1) =  = 30.

 Примітка: Число комбінацій 𝐶_𝑛^𝑘 є частинний випадок числа перестановок з повторенням P_n(k₁,k₂), де k₁=k, k₂ = n-k.

     Задача 29. Скільки існує перестановок букв слова МАТЕМАТИКА ?

       Розв’язання: Дане слово має 10 літер. Тому k=10. Літера М зустрічається 2 рази. і₁=2. Літера А зустрічається 3 рази, і₂=3. Літера Т зустрічається 2 рази, і₃=2. Інші літери – Е,И,К – по одному разу.

   Р₁₀(2,3,2,1,1,1) = Р₁₀(2,3,2) =  = 151200.

        Відповідь: 151200 перестановок.

     Задача 30. Скількома способами можна розселити 8 учнів по трьом кімнатам – одномісній, тримісній, чотиримісній ?

        Розв’язання:  В тримісній кімнаті три учні можуть зайняти місця 3! різними способами, не виходячи з неї. Аналогічно, в чотиримісній кімнаті чотири учні можуть зайняти місця 4! різними способами, не виходячи з неї. Тому загальна кількість способів розселення  учнів по кімнатам дорівнює Р₈(1,3,4) =  = 280.

        Відповідь: 280 способів.

     Задача 31. Скількома способами можна розподілити 10 спеціалістів по чотирьом цехам №1, №2, №3, №4 так, щоб в них попали відповідно 1, 2, 3, 4 спеціаліста ?         Відповідь: Р₁₀(1,2,3,4) =  = 12600.

!

     Задача 32. Скільки слів можна скласти з 5-ти букв А і не більше, ніж трьох букв Б ?

        Розв’язання:  

Р₅(5,0)+Р₆(5,1)+Р₇(5,2)+Р₈(5,3) = С⁰₅+С¹₆+С²₇+С³₈ = С³₉ =_! = 84.

       Відповідь: 84 слова.

     Задача 33. Скільки існує 10-значних чисел, у яких сума цифр дорівнює 3 ?

        Розв’язання: Зафіксуємо на першому місці цифру 1, потім 2, потім 3. Можливі випадки:

111⏟ ⏟0000000       – Р₉(2,7) перестановок

2                     7

1⏟2 ⏟00000000       – Р₉(1,8) перестановок

1                   8

2⏟1 ⏟00000000       – Р₉(1,8) перестановок

1                   8

3000000000  – одне число.

Р₉(2,7) + 2Р₉(1,8) + 1 =  

        Відповідь: 55 чисел.

6.   КОМБІНАЦІЇ З ПОВТОРЕННЯМ З n ЕЛЕМЕНТІВ ПО k

 

        Нехай маємо n-елементну множину М. Розглянемо невпорядковану підмножину (послідовність) з k елементів, які можуть повторюватися. До k-елементної послідовності (наприклад, до b,c,b з М = {a,b,c,d,e}) припишемо всі n елементів множини М і отримані n+k елементів запишемо по порядку, ставлячи однакові елементи поряд (a,b,b,b,c,c,d,e). Потім підмножини  однакових елементів  розділимо n-1 рисочками (a|bbb|cc|d|e). Нарешті, замінимо всі елементи між рисочками на точки (∙|∙∙∙|∙∙|∙|∙). Таким чином ми ставимо у відповідність  k-елементній  послідовності розстановку n-1 рисочок в n+k-1 проміжках. І навпаки, по кожній такій розстановці однозначно відновлюється відповідна їй kпослідовність. Наприклад,

(∙∙∙|∙|∙∙|∙|∙∙)  (aaa|b|cc|d|ee) → {a,a,c,e}.

        Всього існує 𝐶_𝑛^𝑛₊⁻_𝑘¹₋₁ =𝐶_𝑛^𝑘_+𝑘−1 способів розстановки n-1 рисочок на n+k-1 місцях. Отже, і k-послідовностей з повтореннями з множини М існує стільки ж. Число комбінацій з повтореннями позначатимемо 𝑪^𝒌_(𝒏). Отже,

𝐶(𝑘𝑛 ) = 𝐶𝑛𝑘+𝑘−1 (6)

     Задача 34. Скільки різних результатів можна отримати при киданні двох однакових гральних кубиків ?

        Розв’язання: При киданні двох гральних кубиків може випасти невпорядкована пара (i,j) чисел, 1≤i,j≤6. Маємо число

комбінацій з повторенням С

     Задача 35. Скількома способами можна розмістити 5 однакових кульок в три різні урни ?

        Розв’язання: Кожному способу розміщення відповідає 5елементна послідовність з множини М, яка має три типи елементів.

                 М = {     ⏟a       ,    ⏟в    ,    ⏟с    }.

перша урна друга урна третя урна

(Передбачається, що місткість урн необмежена). Тому будемо мати число комбінацій з повтореннями:  С⁵₍₃₎= С⁵₇= 21 різних способів.

     Задача 36. Скількома способами можна розмістити n однакових кульок в m різних урнах за наступними умовами:

1)  Порожніх урн нема.  

2)  В другій урні k кульок.

    Розв’язання: 1). Покладемо в кожну з урн по кульці. Інші

кульки можна розмістити 𝐶₍^𝑛_𝑚⁻₎^𝑚 =𝐶_𝑛^𝑛₋⁻₁^𝑚 = 𝐶_𝑛^𝑚₋⁻₁¹ способами.

2) Відповідь: 𝐶(𝑛𝑚−−𝑘1) = 𝐶𝑛𝑛−−𝑘𝑘+𝑚−2 способів.

   Задача 37. Скількома способами можна роз-містити 5 білих, 6 чорних і 7 синіх кульок в 4 різні урни ?

           Розв’язання: Білі кульки ми можемо розмістити в урни С⁵₍₄₎ способами, чорні – С⁶₍₄₎ способами і сині –  С⁷₍₄₎ способами. Але оскільки розміщення  кульок різного кольору не залежать одне від одного, то, за комбінаторним правилом множення, загальна

кількість способів дорівнює С

     Задача 38. Скільки існує n-значних натуральних чисел, у яких цифри розміщені в неспадному порядку ?

        Розв’язання: Для того, щоб характеризувати число, що задовольняє умові задачі, достатньо сказати, скільки в цьому числі зустрічається одиниць, двійок, … , дев’яток. Інтерпретувати цю задачу можна так: маємо множину М = {1,2,3,4,5,6,7,8,9} і nпослідовність з повторен-нями. Скільки існує способів вибору ?

        Відповідь: ^𝐶₍^𝑛₉₎  = 𝐶₉^𝑛_+𝑛−1 = 𝐶_𝑛^𝑛₊₈.

     Задача 39. В гості запрошені 4 різні пари близнюків. Скількома способами можна вибрати двох з восьми гостей ?

        Розв’язання: кожному способу вибору відповідає двохелементна послідовність з множини М, яка має 4 типи елементів.  

        Відповідь: С²₍₄₎= С²₅ = 10.

     Задача 40. Довести, що кількість різних розв’язків рівняння х₁+х₂+…+х_m  = n в натуральних числах дорівнює 𝐶_𝑛^𝑚₋⁻₁¹.

    Доведення:  Розіб’ємо число n на суму n одиниць. Нехай одиниці – кульки, а числа х_і – урни. З умови задачі жодна урна не може бути порожньою. Тому будемо мати результат задачі 36(1).

7. ЗАДАЧІ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗАННЯ

 

	Без повтору	З повторенням
Перестановки     Розміщення     Комбінації	Pn = n!     𝐴𝑘𝑛=(𝑛−𝑛!𝑘)!   𝐶𝑛𝑘=𝑘!(𝑛𝑛−! 𝑘)!	Pk(i1,i2,…,in) = =k!/(i1!i2!...in!), i1+i2+…+in = k.   𝐴𝑘(𝑛) = nk   𝐶(𝑘𝑛) = 𝐶𝑛𝑘+𝑘−1

 

1)        З села А в село В веде k доріг, а з села В у село С  веде m доріг. Скільки існує різних способів поїздки  з А в С ?    ( km )

2)        Скількома способами можна розмістити на шаховій дошці дві тури так, щоб одна не могла взяти іншу ?                    (49∙64)

3)        Дві тури різного кольору розміщені на шаховій дошці так, що кожна може взяти іншу. Скільки існує таких розміщень ?    (14∙64)

4)        Є три квитки в різні театри. Скількома способами вони можуть бути розподілені між 25 учнями, якщо кожен учень може отримати тільки один квиток ?              (А³₂₅)

5)        Є три квитки на КВК. Скількома способами вони можуть бути розподілені між 25 учнями? Більше одного білета в руки не давати.  (С³₂₅)

6)        Скількома способами на шаховій дошці можна розмістити 8 тур одного кольору, щоб вони не били одна одну і стояли тільки на

чорних клітинах ?                                   ((Р₄)²)

7)        10 груп займаються в 10 розміщених підряд аудиторіях. Скільки існує варіантів розкладу, при яких групи №1 і№2 знаходились в

сусідніх аудиторіях ? (9!2!)  

8)        За круглим столом короля Артура сидять 12 рицарів. З них кожен ворогує з своїми сусідами. Для участі в спецоперації  по звільненню зачарованої принцеси треба вибрати 5 рицарів, але при цьому не можна відправляти разом рицарів, які ворогують один з одним. Яким числом способів це можна зробити ?    

 

9)        Скількома способами можна розмістити 5 білих і 4 чорних кулі так, щоб чорні кулі не лежали поруч ? Розглянути два випадки: а) кулі одного кольору не відрізняються один від одного, б) всі кулі

різні.  (С

10)    На першій з двох паралельних прямих лежить 10 точок, а на другій – 20. Скільки існує трикутників з вершинами в цих точках ?        

)    

11)    Кожну сторону квадрата поділили на n частин. Скільки є трикутників з      вершинами     в     точках    поділу?   Скільки   є

чотирикутників з вершинами в точках поділу?  (^С3_4(𝑛−1)- 4𝐶_𝑛³₋₁,

𝐶₄⁴₍𝑛−1)- 4𝐶_𝑛⁴₋1 -- 12(n-1)𝐶_𝑛³₋1)

12)    Кожну сторону правильного шестикутника поділено на n+1 рівних частин. Скільки є прямокутників з вершинами в точках поділу, в яких є сторони, паралельні сторонам шестикутника? (1,5n(n+1))

13)    Хокейна команда складається з 2-х воротарів, 7 захисників, 10 нападаючих. Скількома способами тренер може утворити стартову шестірку, яка складається з воротаря, двох захисників і трьох

 

14)    В фортепіанному гуртку займаються 10 чоловік, в гуртку художнього слова – 15, у вокальному гуртку – 12 і в фотогуртку – 20 чоловік. Скількома способами можна скласти бригаду з чотирьох читців, трьох піаністів, п’яти співаків і одного фотографа

?   (С

15)    Чотири автори повинні написати книгу  з 17 розділів, причому перший і третій повинні написати по 5 розділів, другий –4, а четвертий – 3 розділи книги. Скількома способами можна

розподілити розділи між авторами ? (С₁₇⁵ С₁₂⁴ С⁵₈С³₃=17!/(5!5!4!3!))

16)    Скільки різних перестановок можна утворити з букв наступних слів: зебра, баран, абракадабра ?  (120, 420, 83160 )

17)    Скількома способами можна роздати 28 кісток доміно чотирьом гравцям так, щоб кожний отримав 7 кісток ?    (28!/(7!)⁴)

18)    Чотири стрілки повинні поразити 8 мішеней (кожен по дві).

Скількома способами вони можуть розподілити мішені між собою?  (2520)

19)    З групи, яка складається з 12 чоловік, щоденно на протязі 6 днів вибирають двох чергових. Визначити кількість різних списків чергових, якщо кожна особа чергує один раз ? (12!/(2!)⁶)

20)    Автомобільні номери складаються з 3-х букв (всього використовується 30 букв) і чотирьох цифр (використовуються усі 10 цифр). Скільки автомобілів можна занумерувати таким чином, щоб ніякі два автомобілі не мали однакових номерів ?      

(30³∙10⁴)

21)Скільки існує 6-значних чисел, всі цифри яких непарні ?     (5⁶)

22)      Шість ящиків різних матеріалів доставляються на 5 поверхів будівлі. Скількома способами можна розподілити матеріали по поверхах ? В скількох варіантах на 5-й поверх доставлений будьякий матеріал?   ( 5⁶, 6∙4⁵ )

23)      Два поштарі  повинні рознести 10 листів за 10 адресами. Скількома способами вони можуть розподілити роботу?   ( 2¹⁰ )

24)      Поїзд метро робить 16 зупинок, на яких виходять всі пасажири. Скількома способами можуть розподілитися між цими зупинками 100 пасажирів, які зайшли в потяг на кінцевій зупинці?     

( 16100 )

25)      Букви азбуки Морзе представляють собою набір точок і тире. Скільки букв може бути в азбуці Морзе, якщо буква не повинна мати більше 5 знаків?         (62)

26)Скільки є п’ятицифрових натуральних чисел, у десятковому запису яких кожна наступна цифра менша від попередньої?    

(С105 )

27)Скільки є п’ятицифрових натуральних чисел, у десятковому запису яких кожна наступна цифра більша від попередньої?    (С⁵₉)

28)      Скількома способами 12 однакових монет можна розкласти в 5 різних гаманців так, щоб жоден гаманець не був порожнім?  (С⁷₍₅₎)

29)      Садівник повинен на протязі  трьох днів посадити 10 дерев. Скількома способами він може розподілити по днях роботу, якщо буде садити не менше одного дерева в день? ( 36 )

30)      В буфеті продаються 5 сортів пиріжків: з яблуками, з капустою, картоплею, м’ясом і грибами (ціна всіх однакова). Яким числом способів можна зробити покупку з 10 пиріжків? (С¹⁰₍₅₎)

31)… Яким числом способів можна зробити покупку так, щоб покуштувати пиріжків усіх видів? (  С⁵₍₅₎ )

32)…, щоб у неї увійшло не менше 2 пиріжків з м’ясом і хоча б 1 пиріжок з яблуками? (С⁷₍₅₎)

33)      Скількома способами можна розмістити 15 однакових куль в 5 різних ящиків так, щоб виявилося не більше 2-х порожніх ящиків?(С¹²₍₅₎)        

34)      Довести, що число різних розв’язків рівняння х₁+х₂+…+х_m=n в невід’ємних цілих числах дорівнює 𝐶_𝑛^𝑚₊⁻_𝑚¹₋₁.

35)      Число 5 можна шістьма способами записати у вигляді суми трьох натуральних чисел: 5=1+1+3, 5=1+2+2, 5=1+3+1, 5=2+1+2, 5=3+1+1, 5=2+2+1. Скількома способами можна

записати натуральне число n у вигляді суми k натуральних чисел?    

(С𝑘𝑛−−11)

36)      На скільки частин розбивають круг n хорд, проведених так, щоб не було перетину трьох і більше хорд в одній точці?  

Розв’язання: Сполучимо послідовно точки, взяті на колі, хордами. Підрахуємо, на скільки частин розбивається многокутник діагоналями. Після проведення кожної діагоналі число частин збільшується на число, яке на одиницю більше від числа точок перетину, що з’являються після проведення діагоналі. Тому число частин, на які діагоналі розбивають многокутник, дорівнює одиниці (на початку ми мали одну частину – весь многокутник) плюс число діагоналей, плюс число точок перетину діагоналей.

Отже, число частин, на які розіб’ється круг, дорівнює

                                                                                                        𝑛(𝑛−3)            ⁴.

                                                                                   n+1+ 2 + 𝐶_𝑛

 

Література:

1)   К. А. Рыбников. Введение в комбинаторный анализ / 2-е изд. – М.: изд-во Моск. ун-та, 1985 – 308 с.

2)   Комбинаторный анализ. Задачи и упражнения: Учебное пособие/Под ред. К.А.Рыбникова.—М.: Наука. Главная редакция физико-математической литературы, 1982.-368 с

3)   Математика: Пособие для подгот. отд-ний/ Под общ. Изд. проф. А. И. Бородина –2-е изд., перераб. и доп. – К. Вища школа. Головное изд-во, 1984. – 288 с.

4)   Пособие по математике для поступающих в ВУЗы: Учеб. Пособие Кутасов А. Д. и др./ Под ред.. Г.Н. Яковлева. – 2-е узд. – М.: Наука. Гл. ред. физ.-мат. лит., 1985.—480 с.

5)   Збірник задач з математики: Навч. посібник/ В.А. Вишенський та ін.. – 2-е вид., доп. – К.: Либідь, 1993. – 344 с.

6)   Сборник задач по математике для поступающих во ВТУЗы. В.К.

Егерев и др./ Под ред. М.И.Сканави. – Мн.: Выш. шк., 1990. – 528 с.: ил.