8 липня о 18:00Вебінар: Проєктне навчання: розвиваємо логічне, критичне та креативне мислення школярів

Стаття "Основні типи задач комбінаторики"

Про матеріал

Пропонована стаття є маленьким науковим посібником, збірником задач з комбінаторики з розв'язками. Ним можуть користуватися як учні, так і вчителі. Задачі різного характеру. Обсяг - від 6 класу до 11-го. Надіюсь, що моя праця принесе користь учням у вивченні комбінаторики.

Перегляд файлу

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

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

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

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

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

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

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

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

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

        Наслідок: Якщо множина А1 складається з n1 елементів, А2 – з n2 елементів , … , Ак – з nk елементів,  то число послідовностей (ai1 ,ai2 ,…,aik ), де аі1 Є А1, ,…,аікЄ Ак ,дорівнює n1n2 …nk .

          Твердження леми і наслідок можна розуміти таким чином: якщо для заповнення першого місця послідовності  елементом з множини А1 маємо n1 можливостей, другого місця – елементом з множини А2 – n2 можливостей, … ,k-го місця  –  елементом  з множини Ак –  nk можливостей, то всього таких послідовностей буде n1n2…nk.

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

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

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

P1, P2, … , Pn і Q1, Q2, …. , Qm  відповідно. Проведено відрізки AQj і CPi . Скільки будемо мати точок перетину цих відрізків ? На скільки частин поділиться трикутник цими відрізками ?

     Відповідь: 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 елементів :  М={a1,a2, … , an}. Скількома способами можна лінійно упорядкувати цю множину, тобто розмістити її елементи один за одним, утворити з них 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

способів.

        Відповідь: 2∙(5!)2= 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. Нехай М={a1, a2,…,an}. Лінійно впорядковані kелементні підмножини (або послідовності, 0≤k≤n) множини М називають k-розміщенням елементів цієї множини. Число всіх таких розміщень позначають 𝐴𝑘𝑛 . Чому дорівнює це число ?

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

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

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

Зокрема 𝐴𝑛𝑛 = Pn.

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

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

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

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

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

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

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

А

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

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

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

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

𝐴𝑘(𝑛) =  nk                  (3)

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

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

𝐴4(10).

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

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

𝐴26𝐴103 = (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 чашок між трьома студентами можна розподілити А36 способами, 8 блюдець А38 способами, 10 ложечок

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

А

        Відповідь: 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 різні. Тому в результаті матимемо С35 = А35/3! = = 10 трикутників.

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

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

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

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

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

𝑛(𝑛−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) 𝐶𝑚2 , б)𝐶𝑛2.

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

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

4)   Аналогічно міркуючи, маємо: а)𝐶𝑚4 , б)n𝐶𝑚3 , в) 𝐶𝑛2𝐶𝑚2 .

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

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

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

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

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

S2 = mnk + n(𝐶𝑚2 +𝐶𝑘2) + m(𝐶𝑛2+𝐶𝑘2) + k(𝐶𝑛2+𝐶𝑚2 ) =

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

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

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

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

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

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

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

С способами.

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

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

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

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

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

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

𝑛

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

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

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

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

        Розв’язання: Різних букв, у запису яких вико-ристовуються k символів, буде стільки, скільки існує підмножин k-елементної множини. Їх, як відомо, 2k. За умовою задачі загальна кількість букв дорівнюватиме 2+22+23+24 = 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! рази менше, тобто .

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

        Нехай М={a1,a2,…,an}—непорожня множина з n елементів, і і12,…,іn – натуральні числа такі, що їх сума дорівнює певному числу k. Кожний упорядкований набір k чисел, що містить в собі елемент aj  рівно ij раз (1≤j≤n), називається перестановкою множини М з повторенням.

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

Число Рк12,…,іn) різних перестановок множини М з повторенням дорівнює

Рк12,…,іn) = 𝑘!⁄(𝑖1!∙i2!∙…∙in!), де ∑ 𝑖j = k.     (5)

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

!

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

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

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

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

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

   Р10(2,3,2,1,1,1) = Р10(2,3,2) =  = 151200.

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

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

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

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

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

!

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

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

Р5(5,0)+Р6(5,1)+Р7(5,2)+Р8(5,3) = С05+С16+С27+С38 = С39 =! = 84.

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

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

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

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

2                     7

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

1                   8

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

1                   8

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

Р9(2,7) + 2Р9(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−1 =𝐶𝑛𝑘+𝑘−1 способів розстановки n-1 рисочок на n+k-1 місцях. Отже, і k-послідовностей з повтореннями з множини М існує стільки ж. Число комбінацій з повтореннями позначатимемо 𝑪𝒌(𝒏). Отже,

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

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

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

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

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

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

                 М = {     ⏟a       ,    в    ,    с    }.

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

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

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

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

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

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

кульки можна розмістити 𝐶(𝑛𝑚)𝑚 =𝐶𝑛𝑛1𝑚 = 𝐶𝑛𝑚11 способами.

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

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

           Розв’язання: Білі кульки ми можемо розмістити в урни С5(4) способами, чорні – С6(4) способами і сині –  С7(4) способами. Але оскільки розміщення  кульок різного кольору не залежать одне від одного, то, за комбінаторним правилом множення, загальна

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

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

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

        Відповідь: 𝐶(𝑛9)  = 𝐶9𝑛+𝑛−1 = 𝐶𝑛𝑛+8.

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

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

        Відповідь: С2(4)= С25 = 10.

     Задача 40. Довести, що кількість різних розв’язків рівняння х12+…+хm  = n в натуральних числах дорівнює 𝐶𝑛𝑚11.

    Доведення:  Розіб’ємо число 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 учнями, якщо кожен учень може отримати тільки один квиток ?              (А325)

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

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

чорних клітинах ?                                   ((Р4)2)

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

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

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

 

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

різні.  (С

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

)    

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

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

𝐶44(𝑛−1)- 4𝐶𝑛41 -- 12(n-1)𝐶𝑛31)

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

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

 

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

?   (С

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

розподілити розділи між авторами ? (С175 С124 С58С33=17!/(5!5!4!3!))

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

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

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

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

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

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

(303∙104)

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

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

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

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

( 16100 )

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

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

(С105 )

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

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

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

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

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

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

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

34)      Довести, що число різних розв’язків рівняння х12+…+хm=n в невід’ємних цілих числах дорівнює 𝐶𝑛𝑚+𝑚1−1.

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)            4.

                                                                                   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 с.: ил.  

Середня оцінка розробки
Структурованість
5.0
Оригінальність викладу
5.0
Відповідність темі
5.0
Загальна:
5.0
Всього відгуків: 1
Оцінки та відгуки
  1. Малиновська Марина Василівна
    Дякую за такий чудовий посібник!!!!!!!!!!!
    Загальна:
    5.0
    Структурованість
    5.0
    Оригінальність викладу
    5.0
    Відповідність темі
    5.0
pdf
Додано
9 лютого 2018
Переглядів
19447
Оцінка розробки
5.0 (1 відгук)
Безкоштовний сертифікат
про публікацію авторської розробки
Щоб отримати, додайте розробку

Додати розробку