Для яких комбінацій важливим є порядок елементів. Завдання з комбінаторики. Приклади рішень

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

Правило множення (основна формула комбінаторики)

Загальна кількість способів, якими можна вибрати по одному елементу з кожної групи і розставити їх у певному порядку (тобто отримати впорядковану сукупність), дорівнює:

Приклад 1

Монету підкинули 3 рази. Скільки різних результатів кидання можна очікувати?

Рішення

Перша монета має альтернативи - або орел, або решка. Для другої монети також є альтернативи тощо, тобто. .

Потрібна кількість способів:

Правило додавання

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

Приклад 2

На полиці 30 книг, з них 20 математичних, 6 технічних та 4 економічних. Скільки існує способів вибору однієї математичної чи економічної книги.

Рішення

Математична книга може бути обрана засобами, економічна - засобами.

За правилом суми існує спосіб вибору математичної чи економічної книги.

Розміщення та перестановки

Розміщення- Це впорядковані сукупності елементів, що відрізняються один від одного або складом, або порядком елементів.

Розміщення без повтореньколи відібраний елемент перед відбором наступного не повертається в генеральну сукупність. Такий вибір називається послідовним вибором без повернення, яке результат – розміщенням без повторень з елементів по .

Число різних способів, якими можна зробити послідовний вибір без повернення елементів з генеральної сукупності обсягу, дорівнює:

Приклад 3

Розклад дня складається із 5 різних уроків. Визначте кількість варіантів розкладу при виборі 11 дисциплін.

Рішення

Кожен варіант розкладу представляє набір 5 дисциплін з 11, від інших варіантів як складом, і порядком прямування. тому:

Перестановки- це впорядковані сукупності, що відрізняються один від одного лише порядком елементів. Число всіх перестановок множини з елементів дорівнює

Приклад 4

Скільки способами можна розсадити 4 людей за одним столом?

Рішення

Кожен варіант розсаджування відрізняється лише порядком учасників, тобто є перестановкою із 4 елементів:

Розміщення з повтореннямиколи відібраний елемент перед відбором наступного повертається в генеральну сукупність. Такий вибір називається послідовним вибором з поверненням, яке результат - розміщенням з повтореннями з елементів по .

Загальна кількість різних способів, якими можна зробити вибір з поверненням елементів з генеральної сукупності обсягу

Приклад 5

Ліфт зупиняється на 7 поверхах. Скільки способами можуть вийти цих поверхах 6 пасажирів, що у кабіні ліфта?

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

Рішення

Кожен із способів розподілу пасажирів по поверхах є комбінацією 6 пасажирів по 7 поверхах, що відрізняється від інших комбінацій як складом, так і їх порядком. Так як на одному поверсі може вийти як один, так і кілька пасажирів, то одні й ті самі пасажири можуть повторюватися. Тому число таких комбінацій дорівнює кількості розміщень з повтореннями з 7 елементів по 6:

Поєднання

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

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

Число поєднань з елементів дорівнює:

Приклад 6

У ящику 9 яблук. Скільки можна вибрати 3 яблука з ящика?

Рішення

Кожен варіант вибору складається з 3 яблук і відрізняється від інших тільки складом, тобто є поєднанням без повторень з 9 елементів:

Кількість способів, якими можна вибрати 3 яблука з 9:

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

Число поєднань з повтореннями з елементів за :

Приклад 7

Поштою продають листівки 3 видів. Скільки можна купити 6 листівок?

Це завдання знайти число поєднань з повтореннями з 3 по 6:

Розбиття множини на групи

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

Число розбиття на груп, коли в першу потрапляють елементів, в другу - елементів, в k-ю групу - елементів, так само:

Приклад 8

Групу з 16 осіб потрібно розбити на три підгрупи, у першій з яких має бути 5 осіб, у другій – 7 осіб, у третій – 4 особи. Скільки способами це можна зробити?

Рішення

Тут

Число розбиття на 3 підгрупи:

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

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

Значну роль комбінаторні методи грають і в суто математичних питаннях - теорії груп та їх уявлень, вивченні основ геометрії, неасоціативних алгебр та ін.

Приклад комбінаторного завдання. Скільки трицифрових чисел можна становити з цифр 0, 2, 4, 6, 8, використовуючи в записі числа кожну з них не більше одного разу?

IМетод. Постараємося виписати усі такі числа. На першому місці може стояти будь-яка цифра крім 0. Наприклад, 2. На другому місці будь-яка цифра з 0, 4, 6 і 8. Нехай 0. Тоді як третю цифру можна вибрати будь-яку з 4, 6, 8. Отримуємо три числа

Замість 0 на друге місце можна було поставити 4, тоді третє цифрою можна записати або 0 або 6, або 8:

Розмірковуючи аналогічно, отримуємо ще дві трійки тризначних чисел із цифрою 2 на першому місці:

Інших, окрім виписаних 12-ти, тризначних чисел із цифрою 2 на першому місці, і задовольняють умові, немає.

Якщо на першому місці записати цифру 4, а решту вибирати із цифр 0, 2, 6, 8, то отримаємо ще 12 чисел:

По стільки тризначних чисел можна скласти з цифрою 6 на першому місці і цифрою 8 на першому місці. Отже, потрібна кількість:

Ось ці числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Відповідь: 48. ◄

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

Правила складання та множення

Комбінаторне правило додавання(правило "або") — одне з основних правил комбінаторики, яке стверджує, що якщо є n елементів та елемент A 1можна вибрати m 1 способами, елемент A 2можна вибрати m 2 A n можна вибрати m n способами, то вибрати або A 1, або A 2, або, і так далі, A n можна, можливо

m 1 + m 2 + ... + m n

методами.

Наприклад, вибрати подарунок дитині з 9 машинок, 7 плюшевих ведмедів та 3 залізниць можна

методами.

Відповідь: 19. ◄

Правило множення (правило "і") - Ще одне з важливих правил комбінаторики. Згідно з ним, якщо елемент A 1можна вибрати m 1 способами, елемент A 2можна вибрати m 2 способами і так далі, елемент A n можна вибрати m n способами, то набір елементів ( A 1, A 2, ... , A n ) можна вибрати

m 1 · m 2 · ... · m n

методами.

Наприклад.

1) Вибрати дитині в подарунок машинку, плюшевого ведмедя та залізницю, вибираючи з 9 машинок, 7 плюшевих ведмедів та 3 залізниць, можна

9 · 7 · 3 = 189

методами.

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

2) Скористаємося правилом множення для розв'язання задачі, вже розглянутої вище: Скільки трицифрових чисел можна становити з цифр 0, 2, 4, 6, 8, використовуючи в записі числа кожну з них не більше одного разу?

IIМетод.

0 не може стояти першим, значить першу цифру потрібно вибрати з 2, 4, 6, 8 - 4 способи;

другою цифрою може бути будь-яка з чотирьох, що залишилися - 4 способи;

третю цифру можна вибрати серед трьох решти - 3 способи.

Отже, кількість тризначних чисел, що шукається:

4 · 4 · 3 = 48.

Відповідь: 48. ◄

Перестановки

Безліч із n елементів називається упорядкованим якщо кожному його елементу поставлено у відповідність натуральне число від 1 до n .

Перестановкою з n елементів називається будь-яке впорядковане безліч з n елементів.

Наприклад, із 4 елементів ♦ ♣ ♠ можна скласти наступні 24 перестановки:

◄

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

P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.

Взагалі, кількість різноманітних перестановок з n елементів дорівнює добутку всіх натуральних чисел від 1 до n , тобто n! (читається "ен факторіал"):

P n= 1 · 2 · 3 · ... · ( n - 1 ) · n = n!.

Для P nсправедлива рекурентна формула:

P n = n· P n - 1 .

Значення факторіалу визначено не тільки для натуральних чисел, а й для 0:

0! = 1 .

Наприклад, скільки способів 5 хлопчиків і 5 дівчаток можуть зайняти в театрі місця в одному ряду з 1-го по 10-е місце, якщо жодні два хлопчики і жодні дві дівчинки не сидять поруч?

Можливі два випадки з однаковою кількістю способів: 1) хлопчики – на непарних місцях, дівчатка на парних та 2) навпаки.

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

P 5 = 120

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

120 · 120 = 14400

методами. Значить, всього способів

14 400 + 14 400 = 28 800.

Відповідь: 28 800. ◄

Перестановки із повтореннями

Перестановкою із повтореннями з n елементів, серед яких k різних, при цьому налічується n 1 невиразних елементів першого типу, n 2 невиразних елементів другого типу і так далі, n k невиразних елементів k -го типу (де n 1 + n 2 + … + n k = n ), називається будь-яке розташування цих елементів по n різних місць.

Число перестановок із повтореннями довжини n з k різних елементів, взятих відповідно n 1 , n 2 , …, n k раз кожен позначається і обчислюється так:$$P_(n_1,n_2, ... , n_k)=\frac(n{n_1!n_2! ... n_k!}~.$$!}

Наприклад, скільки різних десятизначних чисел можна становити з цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В даному випадку: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_(1, 2, 3, 4)=\frac(10{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$!}

Відповідь: 12 600. ◄

Розміщення

Розміщенням з n елементів m(m ≤ n) m елементів, взятих у певному порядку з даних n елементів.

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

Наприклад, складемо всі розміщення з чотирьох елементів A, B, C, Dпо два елементи:

A B; A C; A D;

B A; B C; B D;

C A; C; C D;

D A; D; DC.

◄

Число всіх розміщень з nелементів по mпозначають \(A_n^m\) (читається: " Аз nпо m") і обчислюється за будь-якою з формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m= \frac(n{(n-m)!}$$!}

Приклади завдань.

1) Скористаємося поняттям розміщень з n елементів по m для вирішення задачі, вже двічі розглянутої раніше: Скільки трицифрових чисел можна становити з цифр 0, 2, 4, 6, 8, використовуючи в записі числа кожну з них не більше одного разу?

I IIМетод.

Першу цифру можна вибрати чотирма способами з набору 2, 4, 6, 8. У кожному з цих випадків кількість пар другої та третьої цифри дорівнює кількості розміщень з 4 цифр, що залишилися по 2. Значить кількість тризначних чисел, що шукається, дорівнює: 2=4\cdot \frac(4{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.!}

2) Для польоту в космос необхідно укомплектувати екіпаж із шести осіб. До нього повинні входити: командир корабля, перший і другий його помічники, два бортінженери, один з яких старший, і один лікар. Командний склад вибирається з 20 льотчиків, бортінженери — із 15 фахівців, а лікар — із 5 медиків. Скільки способами можна укомплектувати екіпаж?

Оскільки у виборі командного складу важливий порядок, то командира і його помічників можна вибрати \(A_(20)^3\) способами. Порядок бортінженерів теж важливий, отже, їх вибору існує \(A_(15)^2\) способів. Лікар лише один, для його вибору існує 5 методів. Скористаємося комбінаторним правилом множення і знайдемо кількість можливих екіпажів корабля:$$A_(20)^3\cdot A_(15)^2\cdot 5=\frac(20{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. !} ◄

Зрозуміло, що якщо m = n , то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо також, що якщо m = n - 1 , то$$A_n^(n-1)=A_n^n=P_n=n!.$$

Розміщення з повтореннями

Крім звичайних розміщень бувають і розміщення з повтореннями або вибірки із поверненням .

Нехай є n різних об'єктів. Виберемо з них m штук, діючи за таким принципом. Візьмемо будь-який, але не будемо його встановлювати в якийсь ряд, а просто запишемо під номером 1 його назву, сам об'єкт після цього повернемо до інших. Потім знову з усіх n об'єктів оберемо один (у тому числі, можливо, і той, який був щойно взятий), запишемо його назву, позначивши номером 2, і знову повернемо об'єкт назад. І так далі, поки не отримаємо m назв.

Розміщення з повтореннями позначаються \(\overline(A)_n^m\) і, згідно з правилом множення, обчислюються за формулою $$\overline(A)_n^m=n^m.$$Зауважимо, що тут припустимо випадок, коли m > n тобто обраних об'єктів більше, ніж їх всього є. Це не дивно: кожен об'єкт після "використання" повертається і може бути використаний повторно.

Наприклад, кількість варіантів шестизначного пароля, в якому кожен знак є цифрою від 0 до 9 або літерою латинського алфавіту (одна і та ж мала та велика буква — один символ) і може повторюватися, так само:$$\overline(A)_(10 +26)^6=\overline(A)_(36)^6=36^6=2~176~782~336.$$Якщо ж малі та великі літери вважаються різними символами (як це зазвичай і буває), то кількість можливих паролів стає ще більш колосальним:$$\overline(A)_(10+26+26)^6=\overline(A)_(62)^6=62^6=56~800~235~584. $$

◄

Поєднання

Поєднанням з n елементів m(m ≤ n) називається будь-яка безліч, що складається з m елементів, вибраних із даних n елементів.

На відміну від розміщень у поєднаннях немає значення, у порядку зазначені елементи. Два поєднання з nелементів по mвважаються різними, якщо вони відрізняються хоча б одним елементом.

Наприклад, складемо всі поєднання із чотирьох елементів A, B, C, Dпо два елементи:

A B; A C; A D;

B C; B D;

C D.

◄

Число всіх поєднань з nелементів по mпозначають \(C_n^m\) (читається: " Cз nпо m") і обчислюється за будь-якою з формул: )~\cdot~ ...~\cdot~ (n-m+1))(1\cdot2\cdot3~\cdot~...~\cdot ~m)$$$$C_n^m=\frac( n{m!\cdot (n-m)!}.$$!}

Приклади завдань.

1) Бригада, що займається ремонтом школи, складається з 12 малярів та 5 теслярів. З них для ремонту фізкультурного залу треба виділити 4 малярів та 2 теслярів. Скільки можна це зробити?

Так як порядок малярів у кожній обраній четвірці і порядок теслярів у кожній обраній парі не має значення, то, згідно з комбінаторним правилом множення, кількість способів, що шукається, дорівнює:$$C_(12)^4 \cdot C_5^2 =\frac(12{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. !} ◄

2) У класі навчаються 30 учнів, серед яких 13 хлопчиків та 17 дівчаток. Скільки способами можна сформувати команду з 7 учнів цього класу, якщо до неї повинна входити хоча б одна дівчинка?

Кількість всіх можливих команд по 7 осіб із класу дорівнює \(C_(30)^7\). Кількість команд у яких лише хлопчики - \ (C_ (13) ^ 7 \). Отже, кількість команд, у яких є хоча б одна дівчинка, дорівнює $$C_(30)^7 - C_(13)^7 =\frac(30{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. !} ◄

Поєднання з повтореннями

Окрім звичайних поєднань розглядають поєднання з повтореннями .

Нехай у безлічі є n об'єктів. Виберемо з них m штук, діючи за таким принципом. Візьмемо будь-який, але не будемо його встановлювати в якийсь ряд, а просто запишемо, сам об'єкт після цього повернемо до інших. Потім знову з усіх n об'єктів виберемо один (у тому числі, можливо, і той, який було взято та записано раніше), запишемо його назву і знову повернемо об'єкт назад. І так далі, поки не отримаємо m назв.

Принципова відмінність від розміщень із повтореннями у тому, що у разі елементи списку не нумеруються. Наприклад, список "A, С, A, В"та список "А, А, В, С"вважаються однаковими.

Поєднання з повтореннями позначаються \(\overline(C)_n^m\) і обчислюються за формулою $$\overline(C)_n^m=P_(m,~n-1)=\frac((m+n-1 ){m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда !} m > n тобто обраних об'єктів більше, ніж їх всього є. Дійсно, кожен об'єкт після "використання" повертається назад і може бути використаний знову і знову.

Наприклад, з'ясуємо скільки можна купити 7 тістечок у кондитерському відділі, якщо у продажу 4 їх сорти?

Природно вважати, що кількість тістечок кожного виду не менше 7, і за бажання можна купити тільки тістечка одного з них. Так як порядок в якому кладуть куплені тістечка в коробку не важливий, маємо справу з поєднаннями з повтореннями. Так як потрібно вибрати 7 тістечок з 4 його видів, то кількість способів, що шукається, дорівнює:$$\overline(C)_4^7=\frac((7+4-1){7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$!}

Відповідь: 120. ◄

Біном Ньютона та біноміальні коефіцієнти

Рівність$$(x+a)^n=C_n^0x^na^0+C_n^1x^(n-1)a^1+...+C_n^mx^(n-m)a^m+...+ C_n^nx^0a^n$$називають біномом Ньютона або формулою Ньютона . Права частина рівності називається біноміальним розкладанням у суму а коефіцієнти \(C_n^0,~C_n^1,~...~,~C_n^n\) — біноміальними коефіцієнтами .

Властивості біномних коефіцієнтів:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^(n-m)\\ ~~ ~~~~~~3.~~C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m)\\ ~~~~~~~~4.~ ~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^ 4+~... =C_n^1+C_n^3+C_n^5+~...=2^(n-1)\\ ~~~~~~~~6.~~C_n^n+C_ (n+1)^n+C_(n+2)^n+~...~+C_(n+m-1)^n=C_(n+m)^(n+1)\\ \)

Властивості біномного розкладання:

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

тобто одно n+ 1 .

2. Сума показників ступенів x і a кожного члена розкладання дорівнює показнику ступеня бінома,

тобто (n - m) + m = n .

3. Загальний член розкладання (позначається T n+1 ) має вигляд$$T_(n+1)=C_n^m x^(n-m)a^m,~~~~m=0,~1,~2,~...~,~n.$$

Трикутник Паскаля

Усі можливі значення біномних коефіцієнтів (числа поєднань) для кожного показника ступеня бінома n можна записати у вигляді нескінченної трикутної таблиці. Така таблиця називається трикутником Паскаля:

У цьому трикутнику крайні числа у кожному рядку дорівнюють 1. Дійсно, \(C_n^0=C_n^n=1\). А кожне не крайнє число дорівнює сумі двох чисел попереднього рядка, що стоять над ним: \(C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m)\).

Таким чином, цей трикутник пропонує ще один (рекурентний) спосіб обчислення чисел \(C_n^m\):

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

Чим будемо займатися? У вузькому значенні комбінаторика - це підрахунок різних комбінацій, які можна скласти з деякої множини дискретнихоб'єктів. Під об'єктами розуміються якісь відокремлені предмети чи живі істоти – люди, звірі, гриби, рослини, комахи тощо. При цьому комбінаторику зовсім не хвилює, що безліч складається з тарілки манної каші, паяльника та болотяної жаби. Принципово важливо, що ці об'єкти піддаються перерахуванню – їх три (Дискретність)і суттєво те, що серед них немає однакових.

З безліччю розібралися, тепер про комбінації. Найпоширенішими видами комбінацій є перестановки об'єктів, їх вибірка з множини (поєднання) і розподіл (розміщення). Давайте прямо зараз подивимося, як це відбувається:

Перестановки, поєднання та розміщення без повторень

Не лякайтеся малозрозумілих термінів, тим більше деякі з них дійсно не дуже вдалі. Почнемо з хвоста заголовка – що означає « без повторень»? Це означає, що в даному параграфі будуть розглядатися множини, які складаються з різнихоб'єктів. Наприклад, … ні, кашу з паяльником і жабою пропонувати не буду, краще щось смачніше =) Уявіть, що перед вами на столі матеріалізувалося яблуко, груша і банан (за наявності таких ситуацію можна змоделювати і реально). Викладаємо фрукти зліва направо у такому порядку:

яблуко / груша / банан

Питання перше: Скільки способами їх можна переставити?

Одна комбінація вже записана вище та з іншими проблемами не виникає:

яблуко / банан / груша
груша / яблуко / банан
груша / банан / яблуко
банан / яблуко / груша
банан / груша / яблуко

Разом: 6 комбінацій або 6 перестановок.

Добре, тут не склало особливих труднощів перерахувати всі можливі випадки, але як бути, якщо предметів більше? Вже із чотирма різними фруктами кількість комбінацій значно зросте!

Будь ласка, відкрийте довідковий матеріал (методичку зручно роздрукувати)та у пункті № 2 знайдіть формулу кількості перестановок.

Жодних мук – 3 об'єкти можна переставити способами.

Питання друге: Скільки способами можна вибрати а) один фрукт, б) два фрукти, в) три фрукти, г) хоча б один фрукт?

Навіщо обирати? Так нагуляли апетит у попередньому пункті – для того, щоб з'їсти! =)

а) Один фрукт можна вибрати, очевидно, трьома способами - взяти або яблуко, грушу або банан. Формальний підрахунок проводиться за формулі кількості поєднань:

Запис у разі слід розуміти так: «скількими способами можна вибрати 1 фрукт з трьох?»

б) Перерахуємо всі можливі поєднання двох фруктів:

яблуко та груша;
яблуко та банан;
груші та банан.

Кількість комбінацій легко перевірити за тією самою формулою:

Запис розуміється аналогічно: «скільки можна вибрати 2 фрукти з трьох?».

в) І, нарешті, три фрукти можна вибрати єдиним способом:

До речі, формула кількості поєднань зберігає сенс і для порожньої вибірки:
способом можна вибрати жодного фрукта - власне, нічого не взяти і все.

г) Скільки способами можна взяти хоча б одинфрукт? Умова «хоча б один» передбачає, що нас влаштовує 1 фрукт (будь-який) або 2 будь-яких фрукти або всі 3 фрукти:
способами можна вибрати хоча б один фрукт.

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

Для відповіді на наступне запитання мені потрібні два добровольці… …Ну що ж, якщо ніхто не хоче, тоді викликатиму до дошки =)

Питання третє: Скільки способами можна роздати по одному фрукту Даші та Наташі?

Для того, щоб роздати два фрукти, спочатку потрібно їх вибрати. Відповідно до пункту «бе» попереднього питання, зробити це можна засобами, перепишу їх заново:

яблуко та груша;
яблуко та банан;
груші та банан.

Але комбінацій зараз буде вдвічі більше. Розглянемо, наприклад, першу пару фруктів:
яблуком можна пригостити Дашу, а грушею – Наташу;
або навпаки – груша дістанеться Даші, а яблуко – Наталці.

І така перестановка можлива кожної пари фруктів.

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

Способами можна вибрати 1 юнака;
способами можна вибрати 1 дівчину.

Таким чином, одного юнака іодну дівчину можна вибрати: методами.

Коли з кожної множини вибирається по 1 об'єкту, то справедливий наступний принцип підрахунку комбінацій: « коженоб'єкт з однієї множини може скласти пару з кожнимоб'єктом іншої множини».

Тобто Олег може запросити на танець будь-яку з 13 дівчат, Євген – теж будь-яку з тринадцяти, і аналогічний вибір має решта молодих людей. Разом: можливі пари.

Слід зазначити, що у цьому прикладі немає значення «історія» утворення пари; однак якщо взяти до уваги ініціативу, то кількість комбінацій треба подвоїти, оскільки кожна з 13 дівчат також може запросити на танець будь-якого юнака. Все залежить від умови того чи іншого завдання!

Схожий принцип справедливий і для складніших комбінацій, наприклад: скількома способами можна вибрати двох юнаків ідвох дівчат для участі у сценці КВК?

спілка Інедвозначно натякає, що комбінації необхідно перемножити:

Можливі групи артистів.

Іншими словами, кожнапара юнаків (45 унікальних пар) може виступати з будь-якийпарою дівчат (78 унікальних пар). А якщо розглянути розподіл ролей між учасниками, то комбінацій буде ще більше. …Дуже хочеться, але все-таки утримаюсь від продовження, щоб не прищепити вам огиду до студентського життя =).

Правило множення комбінацій поширюється і на більшу кількість множників:

Завдання 8

Скільки існує трицифрових чисел, які діляться на 5?

Рішення: для наочності позначимо це число трьома зірочками: ***

У розряд сотеньможна записати будь-яку з цифр (1, 2, 3, 4, 5, 6, 7, 8 чи 9). Нуль не годиться, тому що в цьому випадку число перестає бути тризначним.

А ось у розряд десятків(«посередині») можна вибрати будь-яку з 10 цифр: .

За умовою, число має ділитися на 5. Число ділиться на 5, якщо воно закінчується на 5 або на 0. Таким чином, у молодшому розряді нас влаштовують 2 цифри.

Отже, існує: трицифрових чисел, які діляться на 5.

При цьому твір розшифровується так: «9 способами можна вибрати цифру в розряд сотень і 10 способами вибрати цифру в розряд десятків і 2 способами в розряд одиниць»

Або ще простіше: « кожназ 9 цифр у розряді сотенькомбінується з кожноюз 10 цифр розряду десятків і з кожноюз двох цифр у розряд одиниць».

Відповідь: 180

А зараз…

Так, мало не забув про обіцяний коментар до завдання № 5, в якому Борі, Дімі та Володі можна здати за однією картою способами. Множення тут має той самий сенс: способами можна витягти 3 карти з колоди І в кожнійвибірці переставити їх засобами.

А тепер завдання для самостійного вирішення… зараз придумаю щось цікавіше, …нехай буде про ту ж російську версію блекджека:

Завдання 9

Скільки існує виграшних комбінацій з 2 карток при грі в «очко»?

Для тих, хто не знає: виграє комбінація 10 + ТУЗ (11 очок) = 21 очко і, давайте вважатимемо виграшною комбінацію з двох тузів.

(Порядок карт у будь-якій парі не має значення)

Коротке рішення та відповідь наприкінці уроку.

До речі, не слід вважати приклад примітивним. Блекджек - це чи не єдина гра, для якої існує математично обґрунтований алгоритм, що дозволяє вигравати у казино. Бажаючі можуть легко знайти масу інформації про оптимальну стратегію та тактику. Щоправда, такі майстри досить швидко потрапляють до чорного списку всіх закладів.

Настав час закріпити пройдений матеріал парою солідних завдань:

Завдання 10

У Васі вдома живуть 4 коти.

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

Вирішуємо: по-перше, знову слід звернути увагу на те, що в задачі йдеться про різнихоб'єктах (навіть якщо коти – однояйцеві близнюки). Це дуже важлива умова!

а) Мовчання котів. Цю кару зазнають відразу всі коти
+ важливе їх розташування, тому тут мають місце перестановки:
способами можна розсадити котів по кутах кімнати.

Повторюся, що з перестановках має значення лише кількість різних об'єктів та його взаємне розташування. Залежно від настрою Вася може розсаджувати тварин півколом на дивані, ряд на підвіконні і т.д. – перестановок у всіх випадках буде 24. Бажаючі можуть для зручності уявити, що коти різнокольорові (наприклад, білий, чорний, рудий та смугастий) та перерахувати всі можливі комбінації.

б) Скільки можна відпустити гуляти котів?

Передбачається, що коти ходять гуляти тільки через двері, при цьому питання має на увазі байдужість щодо кількості тварин – на прогулянку можуть вийти 1, 2, 3 або всі 4 коти.

Вважаємо всі можливі комбінації:

Способами можна відпустити гуляти одного кота (будь-якого з чотирьох);
способами можна відпустити гуляти двох котів (варіанти перерахуйте самостійно);
способами можна відпустити гуляти трьох котів (якийсь один із чотирьох сидить удома);
способом можна випустити всіх котів.

Напевно, ви здогадалися, що отримані значення слід підсумувати:
способами можна відпустити гуляти котів.

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

в) Скільки способами Вася може взяти на руки двох котів?

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

Другий варіант вирішення: способами можна вибрати двох котів іспособами посадити кожнупару на руки:

Відповідь: а) 24, б) 15, в) 12

Ну і для очищення совісті щось конкретніше на збільшення комбінацій. Нехай у Васі додатково живе 5 котів =) Скільки способами можна відпустити гуляти 2 котів і 1 кішку?

Тобто, з кожноюпарою котів можна випустити кожнукішку.

Ще один баян для самостійного вирішення:

Завдання 11

У ліфт 12-поверхового будинку сіли 3 пасажири. Кожен, незалежно від інших, з однаковою ймовірністю може вийти на будь-якому (починаючи з 2-го) поверсі. Скількими способами:

1) пасажири можуть вийти на тому самому поверсі (Порядок виходу не має значення);
2) дві людини можуть вийти на одному поверсі, а третя – на іншому;
3) люди можуть вийти різних поверхах;
4) пасажири можуть вийти із ліфта?

І тут часто перепитують, уточнюю: якщо 2 чи 3 особи виходять на одному поверсі, то черговість виходу не має значення. ДУМАЙТЕ, використовуйте формули та правила додавання/множення комбінацій. У разі труднощів пасажирам корисно дати імена та поміркувати, у яких комбінаціях вони можуть вийти з ліфта. Не треба засмучуватися, якщо щось не вийде, наприклад, пункт № 2 досить підступний.

Повне рішення із докладними коментарями наприкінці уроку.

Заключний параграф присвячений комбінаціям, які теж зустрічаються досить часто – за моєю суб'єктивною оцінкою, приблизно 20-30% комбінаторних завдань:

Перестановки, поєднання та розміщення з повтореннями

Перелічені види комбінацій законспектовані у пункті № 5 довідкового матеріалу Основні формули комбінаторикиПроте деякі з них за першим прочитанням можуть бути не дуже зрозумілими. І тут спочатку доцільно ознайомитися з практичними прикладами, і лише потім осмислювати загальне формулювання. Поїхали:

Перестановки із повтореннями

У перестановках із повтореннями, як і в «звичайних» перестановках, бере участь відразу все безліч об'єктів, але є одне але: в даному множині один або більша кількість елементів (об'єктів) повторюються. Зустрічайте черговий стандарт:

Завдання 12

Скільки різних буквосполучень можна отримати перестановкою карток із наступними літерами: К, О, Л, О, К, О, Л, Ь, Ч, І, К?

Рішення: у тому випадку, якби всі літери були різні, то слід було б застосувати тривіальну формулу , проте цілком зрозуміло, що для запропонованого набору карток деякі маніпуляції спрацьовуватимуть «вхолосту», наприклад, якщо поміняти місцями будь-які дві картки з літерами «К » у будь-якому слові, то вийде те саме слово. Причому фізично картки можуть сильно відрізнятися: одна бути круглою з надрукованою літерою «К», інша – квадратною з намальованою літерою «К». Але за змістом завдання навіть такі картки вважаються однаковими, оскільки в умові питається про буквосполучення.

Все дуже просто – всього: 11 карток, серед яких літера:

К - повторюється 3 рази;
Про - повторюється 3 рази;
Л – повторюється двічі;
Ь - повторюється 1 раз;
Ч – повторюється 1 раз;
І – повторюється один раз.

Перевірка: 3 + 3 + 2 + 1 + 1 + 1 = 11, що потрібно перевірити.

За формулою кількості перестановок із повтореннями:
різних буквосполучень можна отримати. Більше півмільйона!

Для швидкого розрахунку великого факторіального значення зручно використовувати стандартну функцію Екселю: забиваємо в будь-яку комірку =ФАКТР(11)і тиснемо Enter.

На практиці цілком допустимо не записувати загальну формулу і, крім того, опускати поодинокі факторіали:

Але попередні коментарі про літери, що повторюються, обов'язкові!

Відповідь: 554400

Інший типовий приклад перестановок з повтореннями зустрічається в задачі про розміщення шахових фігур, яку можна знайти на складі готових рішеньу відповідній pdf-ці. А для самостійного рішення я вигадав менш шаблонне завдання:

Завдання 13

Олексій займається спортом, причому 4 дні на тиждень – легкою атлетикою, 2 дні – силовими вправами та 1 день відпочиває. Скільки способами він може скласти собі розклад занять на тиждень?

Формула тут не годиться, оскільки враховує збігаються перестановки (наприклад, коли міняються місцями силові вправи у середу із силовими вправами у четвер). І знову - за фактом ті ж 2 силові тренування можуть сильно відрізнятися один від одного, але за контекстом завдання (з точки зору розкладу) вони вважаються однаковими елементами.

Дворядкове рішення та відповідь наприкінці уроку.

Поєднання з повтореннями

Характерна риса цього виду комбінацій у тому, що вибірка проводиться із кількох груп, кожна у тому числі складається з однакових об'єктів.

Сьогодні всі добре попрацювали, тому настав час підкріпитись:

Завдання 14

У студентській їдальні продають сосиски в тесті, ватрушки та пончики. Скільки можна придбати п'ять пиріжків?

Рішення: відразу зверніть увагу на типовий критерій поєднань із повтореннями – за умовою на вибір запропоновано не безліч об'єктів як таке, а різні видиоб'єктів; при цьому передбачається, що у продажу є не менше п'яти хот-догів, 5 ватрушок та 5 пончиків. Тістечка в кожній групі, зрозуміло, відрізняються - бо абсолютно ідентичні пончики можна змоделювати хіба що на комп'ютері =) Проте фізичні характеристики пиріжків за змістом завдання не суттєві, і хот-доги/ватрушки/пончики у своїх групах вважаються однаковими.

Що може бути у вибірці? Насамперед, слід зазначити, що у вибірці обов'язково будуть однакові пиріжки (обираємо 5 штук, а на вибір запропоновано 3 види). Варіанти тут на будь-який смак: 5 хот-догів, 5 ватрушок, 5 пончиків, 3 хот-доги + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончики і т.д.

Як і при «звичайних» поєднаннях, порядок вибору та розміщення пиріжків у вибірці не має значення – просто вибрали 5 штук та все.

Використовуємо формулу кількості поєднань із повтореннями:
способом можна придбати 5 пиріжків.

Смачного!

Відповідь: 21

Який висновок можна зробити із багатьох комбінаторних завдань?

Іноді найважче – це розібратися в умові.

Аналогічний приклад для самостійного вирішення:

Завдання 15

У гаманці знаходиться досить велика кількість 1-, 2-, 5- та 10-рублевих монет. Скільки способами можна витягти три монети з гаманця?

З метою самоконтролю дайте відповідь на кілька простих питань:

1) Чи можуть у вибірці всі монети бути різними?
2) Назвіть найдешевшу і найдорожчу комбінацію монет.

Рішення та відповіді наприкінці уроку.

З мого особистого досвіду, можу сказати, що поєднання з повтореннями – найрідкісніший гість на практиці, чого не скажеш про такий вид комбінацій:

Розміщення з повтореннями

З множини, що складається з елементів, вибирається елементів, при цьому важливий порядок елементів у кожній вибірці. І все було б нічого, але досить несподіваний прикол полягає в тому, що будь-який об'єкт вихідної множини ми можемо вибирати скільки завгодно разів. Образно кажучи, від «багато не убуде».

Коли таке буває? Типовим прикладом є кодовий замок з кількома дисками, але через розвиток технологій актуальніше розглянути його цифрового нащадка:

Завдання 16

Скільки існує чотиризначних пін-кодів?

Рішення: насправді для розрулювання завдання достатньо знань правил комбінаторики: способами можна вибрати першу цифру пін-коду іспособами – другу цифру пін-коду істільки ж способами – третю істільки ж – четверту. Таким чином, за правилом множення комбінацій, чотиризначний пін-код можна скласти: способами.

А тепер за допомогою формули. За умовою нам запропоновано набір із цифр, з якого вибираються цифри та розташовуються у визначеному порядку, при цьому цифри у вибірці можуть повторюватися (тобто будь-якою цифрою вихідного набору можна користуватися довільну кількість разів). За формулою кількості розміщень із повтореннями:

Відповідь: 10000

Що тут спадає на думку… …якщо банкомат «з'їдає» картку після третьої невдалої спроби введення пін-коду, то шанси підібрати його навмання дуже примарні.

І хто сказав, що у комбінаториці немає жодного практичного сенсу? Пізнавальне завдання для всіх читачів сайт:

Завдання 17

Згідно з державним стандартом, автомобільний номерний знак складається з 3 цифр та 3 літер. При цьому неприпустимий номер із трьома нулями, а літери вибираються з набору А, В, Е, К, М, Н, О, Р, С, Т, У, Х (використовуються лише ті літери кирилиці, написання яких збігається з латинськими літерами).

Скільки номерних знаків можна скласти для регіону?

Не так їх, до речі, багато. У великих регіонах такої кількості не вистачає, і тому для них існує кілька кодів до напису RUS.

Рішення та відповідь наприкінці уроку. Не забуваємо використовувати правила комбінаторики;-) …Хотів похвалитися ексклюзивом, та виявилося не ексклюзивом =) Заглянув у Вікіпедію – там є розрахунки, щоправда, без коментарів. Хоча у навчальних цілях, напевно, мало хто вирішував.

Наше захоплююче заняття добігло кінця, і насамкінець я хочу сказати, що ви не дарма витратили час – з тієї причини, що формули комбінаторики знаходять ще одне насущне практичне застосування: вони зустрічаються в різних завданнях теорії ймовірностей,
і в завдання на класичне визначення ймовірності- Особливо часто =)

Дякую всім за активну участь і до швидких зустрічей!

Рішення та відповіді:

Завдання 2: Рішення: знайдемо кількість всіх можливих перестановок 4 карток:

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

Примітка : т.к. карток небагато, то тут нескладно перерахувати всі такі варіанти:
0579
0597
0759
0795
0957
0975

Таким чином, із запропонованого набору можна скласти:
24 - 6 = 18 чотиризначних чисел
Відповідь : 18

Завдання 4: Рішення: способами можна вибрати 3 карти з 36
Відповідь : 7140

Завдання 6: Рішення: методами.
Інший варіант вирішення : способами можна вибрати двох осіб з групи та
2) «Найдешевший» набір містить 3 рублеві монети, а «найдорожчий» – 3 десятирублеві.

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

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

Народження комбінаторикипов'язано з роботами Б. Паскаляі П. Ферма з приводу азартних ігор, великий внесок зробили Лейбніц, Бернуллі, Ейлер. Нині інтерес до комбінаторики пов'язані з розвитком комп'ютерів. Нас у комбінаториці цікавитиме можливість визначення кількісно різних підмножин кінцевих множин для обчислення ймовірності класичним способом.

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

Правило nвиробництва:нехай з деякої кінцевої множини

1-й об'єкт можна вибрати k 1 способами,

Другий об'єкт - k 2 способами,

n-ий об'єкт - k nметодами. (1.1)

Тоді довільний набір, перерахованих nоб'єктів з даної множини можна вибрати k 1 , k 2 , …, k nметодами.

приклад 1.Скільки існує трицифрових чисел з різними цифрами?

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

За правилом твору 9 · 9 · 8 = 648 тризначних чисел мають різні цифри.

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

Рішення. У пункті є 3 способи вибору дороги в пункт, а в пункті є 4 способи потрапити до пункту. Згідно з принципом множення існує 3×4 = 12 способів потрапити з пункту у пункт.

Правило суми:під час виконання умов (1.1), будь-який з об'єктів можна вибрати k 1 +k 2 +…+k nметодами.

приклад 3.Скільки існує способів вибору одного олівця з коробки, що містить 5 червоних, 7 синіх, 3 зелених олівця.

Рішення. Один олівець за правилом суми можна вибрати 5+7+3 = 15 способами.

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

Рішення. Всі умови принципу додавання тут виконані, тому відповідно до цього принципу отримаємо 1+2+3 = 6 способів.

Розглянемо приклад, що ілюструє відмінність принципів множення та додавання.

Приклад 5.У магазині електроніки продаються три марки телевізорів та два види відеомагнітофонів. Покупець має можливість придбати або телевізор, або відеомагнітофон. Скільки способами він може зробити одну покупку? Скільки різних комплектів, що містять телевізор та магнітофон, можна придбати у цьому магазині, якщо покупець збирається придбати в парі і телевізор, і відеомагнітофон?

Рішення. Один телевізор можна вибрати трьома способами, а магнітофон іншими двома способами. Тоді телевізор або магнітофон можна купити 3+2=5 способами.

У другому випадку один телевізор можна вибрати трьома способами, після чого відеомагнітофон можна вибрати двома способами. Отже, в силу принципу множення купити телевізор і відеомагнітофон можна 3×2 = 6 способами.

Розглянемо тепер приклади, у яких застосовуються обидва правила комбінаторики: і принцип множення, і принцип додавання.

Приклад 6.У кошику лежать 12 яблук та 10 апельсинів. Ваня вибирає або яблуко, або апельсин. Після чого Надя вибирає з фруктів, що залишилися, і яблуко і апельсин. Скільки можливо таких виборів?

Рішення. Ваня може вибрати яблуко 12 способами, апельсин – 10 способами. Якщо Ваня вибирає яблуко, то Надя може вибрати яблуко 11 способами, а апельсин – 10 способами. Якщо Ваня вибирає апельсин, то Надя може вибрати яблуко 12 способами, а апельсин – 9 способами. Таким чином, Ваня та Надя можуть зробити свій вибір способами.

Приклад 7.Є 3 листи, кожний з яких можна надіслати на 6 адрес. Скільки способами це можна зробити?

Рішення. У цьому завдання ми повинні розглянути три випадки:

а) всі листи розсилаються на різні адреси;

б) усі листи надсилаються за однією адресою;

в) лише два листи надсилаються за однією адресою.

Якщо всі листи розсилаються на різні адреси, то число таких способів легко перебуває з принципу множення: n 1 = 6×5×4 = 120 способів. Якщо всі листи надсилаються на одну адресу, то таких способів буде n 2 = 6. Таким чином, залишається розглянути лише третій випадок, коли лише 2 листи надсилаються за однією адресою. Вибрати будь-який лист ми можемо 3 способами, і надіслати його за будь-якою обраною адресою можемо 6 способами. Два листи, що залишилися, ми можемо надіслати за адресами, що залишилися, 5 способами. Отже, надіслати лише два листи на одну адресу ми можемо n 3 =3×6×5=90 способами. Таким чином, розіслати 3 листи за 6 адресами у відповідність до принципу додавання можна

методами.

Зазвичай у комбінаториці розглядається ідеалізований експеримент щодо вибору навмання kелементів з n. При цьому елементи: а) не повертаються (схема вибору без повернень); б) повертаються назад (схема вибору із поверненням).

1. Схема вибору без повернень

Розміщеннямз nелементів по kназивають будь-який упорядкований набір з kелементів, що належать n- Елементній множині. Різні розміщення відмінні один від одного або порядком елементів або складом.

Кількість розміщень з nелементів по kпозначається та обчислюється за формулою

(1.2)

де n! = 1×2×3×…× n, 1! = 1, 0! = 1.

Приклад 8.У змаганнях бере участь 10 осіб, троє з них займуть 1, 2, 3 місце. Скільки існує різних варіантів?

Рішення. І тут важливий порядок розподілу місць. Число різних варіантів дорівнює

Перестановкоюз nелементів називають розміщення з nелементів по n.Число перестановок з nелементів позначають P nта обчислюють за формулою

(1.3)

Приклад 9.Скільки існує способів розміщення 10 книг на полиці?

Рішення. Загальна кількість способів розміщення визначається як число перестановок (1.3) з 10 елементів і дорівнює Р 10 = 10! = 3628 800.

2. Схема вибору із поверненнями

Якщо при виборі kелементів з n, елементи повертаються назад і впорядковуються, то кажуть, що це розміщення з новторіннями .

Кількість розміщень із повтореннями:

Приклад 11.У готелі є 10 кімнат, кожна з яких може розмістити чотирьох осіб. Скільки існує варіантів розміщення чотирьох гостей?

Рішення. Кожен наступний гість з 4 може бути поміщений в будь-яку з 10 кімнат, оскільки розглядається ідеалізований досвід, тому загальна кількість розміщень, за формулою розміщень з повтореннями (1.5), дорівнює

.

Якщо при виборі kелементів з nелементи повертаються назад без подальшого впорядкування, то кажуть, що це поєднання з новторіннями. Число поєднань з повтореннями з nелементів по kвизначається:

приклад 12.У магазині продається 10 видів тортів. Черговий покупець вибив чек на три торти. Вважаючи, що будь-який набір товарів рівноможливий, визначити кількість можливих замовлень.

Рішення. Число рівноможливих замовлень за формулою (1.6) дорівнює

.

У цій статті йтиметься про особливий розділ математики під назвою комбінаторика. Формули, правила, приклади вирішення завдань - все це ви зможете знайти тут, прочитавши статтю до кінця.

Отже, що це за розділ? Комбінаторика займається питанням підрахунку будь-яких об'єктів. Але в даному випадку об'єктами виступають не сливи, груші чи яблука, а щось інше. Комбінаторика допомагає нам знаходити ймовірність будь-якої події. Наприклад, при грі в карти - яка ймовірність того, що противник має козирну карту? Або такий приклад - яка ймовірність того, що з мішка з двадцятьма кульками ви дістанете саме білий? Саме для таких завдань нам і потрібно знати хоча б основи даного розділу математики.

Комбінаторні конфігурації

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

• розміщення;
• перестановка;
• поєднання;
• композиція числа;
• розбиття числа.

Про перші три ми поговоримо більш детально далі, а от композиції та розбиття ми приділимо увагу в даному розділі. Коли говорять про композицію деякого числа (припустимо, а), то мають на увазі уявлення числа а як упорядкованої суми деяких позитивних чисел. А розбиття – це невпорядкована сума.

Розділи

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

• перечислювальна;
• структурна;
• екстремальна;
• теорія Рамсея;
• імовірнісна;
• топологічна;
• інфінітарна.

У першому випадку йдеться про обчислювальну комбінаторику, завдання розглядають перерахування або підрахунок різних конфігурацій, які утворені елементами множин. На дані множини, як правило, накладаються будь-які обмеження (розрізність, нерозрізненість, можливість повтору тощо). А кількість цих змін підраховується за допомогою правила додавання або множення, про які ми поговоримо трохи пізніше. До структурної комбінаторики належать теорії графів та матроїдів. Приклад завдання екстремальної комбінаторики - найбільша розмірність графа, який задовольняє наступним властивостям… У четвертому пункті ми згадали теорію Рамсея, яка вивчає у випадкових конфігураціях наявність регулярних структур. Імовірнісна комбінаторика здатна нам відповісти на питання - яка ймовірність того, що у заданої множини є певна властивість. Як неважко здогадатися, топологічна комбінаторика застосовує методи топології. І, нарешті, сьомий пункт – інфінітарна комбінаторика вивчає застосування методів комбінаторики до нескінченних множин.

Правило додавання

Серед формул комбінаторики можна знайти і прості, з якими ми досить давно знайомі. Прикладом є правило суми. Припустимо, що нам дано дві дії (С та Е), якщо вони взаємовиключні, дію С виконаємо кількома способами (наприклад а), а дію Е виконаємо b-способами, то виконати будь-яку з них (С або Е) можна а+b способами .

Теоретично це зрозуміти досить важко, постараємося донести всю суть на простому прикладі. Візьмемо середню чисельність учнів одного класу – припустимо, це двадцять п'ять. Серед них п'ятнадцять дівчаток та десять хлопчиків. Щодня у класі призначається один черговий. Скільки є способів призначити чергового класу сьогодні? Вирішення завдання досить просте, ми вдамося до правила додавання. У тексті завдання не сказано, що черговими можуть бути лише хлопчики чи дівчатка. Отже, ним може бути будь-яка з п'ятнадцяти дівчаток або будь-який з десяти хлопчиків. Застосовуючи правило суми, ми отримуємо досить простий приклад, з яким легко впорається школяр початкових класів: 15 + 10. Підрахувавши, отримуємо відповідь: двадцять п'ять. Тобто існує лише двадцять п'ять способів призначити сьогодні чергового класу.

Правило множення

До основних формул комбінаторики відноситься і правило множення. Почнемо з теорії. Припустимо, нам необхідно виконати кілька дій (а): перша дія виконується з 1 способами, друга - з 2 способами, третя - з 3 способами і так далі до останньої а-дії, що виконується зі способами. Тоді всі ці дії (яких у нас а) можуть бути виконані N способами. Як вирахувати невідому N? У цьому нам допоможе формула: N = с1 * с2 * с3 * ... * Са.

Знову ж таки, в теорії нічого не зрозуміло, переходимо до розгляду простого прикладу застосування правила множення. Візьмемо той самий клас із двадцяти п'яти чоловік, у якому навчається п'ятнадцять дівчаток і десять хлопчиків. Тільки цього разу нам необхідно вибрати двох чергових. Ними можуть бути як тільки хлопчики чи дівчатка, так і хлопчик із дівчинкою. Переходимо до елементарного розв'язання задачі. Вибираємо першого чергового, як ми вирішили у минулому пункті, у нас виходить двадцять п'ять можливих варіантів. Другим черговим може бути будь-яка людина, що залишилася. У нас було двадцять п'ять учнів, одного ми вибрали, значить другим черговим може бути будь-хто з двадцяти чотирьох чоловік. Нарешті, застосовуємо правило множення та отримуємо, що двох чергових можна обрати шістьма сотнями способів. Ми дане число отримали множенням двадцяти п'яти та двадцяти чотирьох.

Перестановка

Наразі ми розглянемо ще одну формулу комбінаторики. У розділі статті ми поговоримо про перестановках. Розглянути проблему пропонуємо відразу на прикладі. Візьмемо більярдні кулі у нас їх n-а кількість. Нам потрібно підрахувати: скільки є варіантів розставити їх до ряду, тобто скласти впорядкований набір.

Почнемо, якщо у нас немає куль, то і варіантів розміщення у нас так само нуль. А якщо у нас куля одна, то й розстановка теж одна (математично це можна записати так: Р1 = 1). Дві кулі можна розставити двома різними способами: 1,2 та 2,1. Отже, Р2 = 2. Три кулі можна розставити вже шістьма способами (Р3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А якщо таких куль не три, а десять чи п'ятнадцять? Перераховувати всі можливі варіанти дуже довго, тоді нам на допомогу приходить комбінаторика. Формула перестановки допоможе нам знайти відповідь на питання, що нас цікавить. Pn = n * P (n-1). Якщо спробувати спростити формулу, отримуємо: Pn = n* (n - 1) *…* 2 * 1. І це є твір перших натуральних чисел. Таке число називається факторіалом, а позначається як n!

Розглянемо завдання. Вожатий щоранку вибудовує свій загін у шеренгу (двадцять чоловік). У загоні є три найкращі друзі - Костя, Сашко та Льоша. Яка ймовірність того, що вони стоятимуть поряд? Щоб знайти відповідь на запитання, необхідно можливість «хорошого» результату поділити на загальну кількість результатів. Загальна кількість перестановок складає 20! = 2,5 квінтильйону. Як порахувати кількість «добрих» результатів? Припустимо, що Костя, Сашка та Льоша - це одна надлюдина. Тоді ми маємо лише вісімнадцять суб'єктів. Число перестановок у разі дорівнює 18 = 6,5 квадриллионов. При цьому, Костя, Сашко та Льоша можуть довільно переміщатися між собою у своїй неподільній трійці, а це ще три! = 6 варіантів. Отже, всього «хороших» розстановок у нас 18! * 3! Нам залишається тільки знайти ймовірність: (18! * 3!) / 20! Що дорівнює приблизно 0,016. Якщо перевести у відсотки, то це виходить лише 1,6%.

Розміщення

Зараз ми розглянемо ще одну дуже важливу та необхідну формулу комбінаторики. Розміщення - це наше наступне питання, яке пропонуємо вам розглянути в цьому розділі статті. Ми йдемо на ускладнення. Припустимо, що хочемо розглянути можливі перестановки, лише з безлічі (n), та якщо з меншого (m). Тобто ми розглядаємо перестановки з n предметів m.

Основні формули комбінаторики варто не просто заучувати, а розуміти їх. Навіть незважаючи на те, що вони ускладнюються, тому що у нас не один параметр, а два. Припустимо, що m = 1, то А = 1, m = 2, то А = n * (n - 1). Якщо далі спрощувати формулу і перейти на запис за допомогою факторіалів, то вийде лаконічна формула: А = n! /(n - m)!

Поєднання

Ми розглянули майже всі основні формули комбінаторики з прикладами. Тепер перейдемо до заключного етапу розгляду базового курсу комбінаторики – знайомство із поєднанням. Зараз ми вибиратимемо m предметів з наявних у нас n, при цьому всім ми вибиратимемо всіма можливими способами. Чим тоді це відрізняється від розміщення? Ми не враховуватимемо порядок. Цей невпорядкований набір і буде поєднанням.

Відразу введемо позначення: С. Беремо розміщення m кульок з n. Ми перестаємо звертати увагу на порядок і отримуємо повторювані поєднання. Щоб отримати кількість поєднань, нам треба поділити число розміщень на m! (m Факторіал). Тобто С = А/m! Таким чином, способів вибрати з n куль трошки, дорівнює приблизно стільки, скільки вибрати майже все. Цьому є логічний вираз: вибрати трохи однаково, що викинути майже все. Ще в даному пункті важливо згадати і те, що максимальної кількості поєднань можна досягти при спробі вибрати половину предметів.

Як вибрати формулу для розв'язання задачі?

Ми детально розглянули основні формули комбінаторики: розміщення, перестановка та поєднання. Тепер наше завдання – полегшити вибір необхідної формули для вирішення задачі з комбінаторики. Можна скористатися такою досить простою схемою:

1. Поставте собі питання: порядок розміщення елементів враховується у тексті завдання?
2. Якщо відповіді немає, то скористайтеся формулою поєднання (С = n!/(m!*(n – m)!)).
3. Якщо відповіді немає, необхідно відповісти ще одне питання: чи всі елементи входять у комбінацію?
4. Якщо так, то скористайтеся формулою перестановки (Р = n!).
5. Якщо відповіді немає, то скористайтеся формулою розміщення (А = n!/(n – m)!).

приклад

Ми розглянули елементи комбінаторики, формули та деякі інші питання. Тепер перейдемо до розгляду реального завдання. Уявіть, що перед вами лежать ківі, апельсин та банан.

Питання перше: скільки їх можна переставити? І тому скористаємося формулою перестановок: Р = 3! = 6 методів.

Питання друге: скільки можна вибрати один фрукт? Це очевидно, у нас всього три варіанти – вибрати ківі, апельсин чи банан, але застосуємо формулу поєднань: С = 3! / (2! * 1!) = 3.

Питання третє: скільки можна вибрати два фрукти? Які у нас взагалі варіанти? Ківі та апельсин; ківі та банан; апельсин та банан. Тобто три варіанти, але це легко перевірити за допомогою формули поєднання С = 3! / (1! * 2!) = 3

Питання четверте: скільки можна вибрати три фрукти? Як видно, вибрати три фрукти можна одним-єдиним способом: взяти ківі, апельсин та банан. З = 3! / (0! * 3!) = 1.

Питання п'яте: скільки можна вибрати хоча б один фрукт? Ця умова передбачає, що ми можемо взяти один, два або всі три фрукти. Отже, ми складаємо С1 + С2 + С3 = 3 + 3 + 1 = 7. Тобто ми маємо сім способів взяти зі столу хоча б один фрукт.