Комбінаторика - це математична наука, грубо кажучи, про підрахунок числа способів зробити що-небудь. Незважаючи на вузькість предмета вивчення, наука ця вельми глибока. Крім того, в олімпіадних задачах комбінаторика використовується настільки часто, що її знання абсолютно необхідно кожному математику-олімпіаднику.
Основні комбінаторні формули і міркування:
1.Адитивність взаємовиключних випадків. Якщо у задачі з комбінаторики є декілька взаємовиключних випадків/варіантів вибору, загальна кількість способів дорівнює сумі кількостей способів в кожному з цих випадків.
2.Мультипликативність незалежних випадків. Якщо спосіб (кількість яких треба порахувати) повністю визначається декількома незалежними один від одного етапами вибору (на кожному етапі вибір варіантів - взаємовиключний!), То загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.
Доведення Нехай всього є k етапів. Позначимо кількість варіантів вибору на першому етапі - n1, на другому етапі - n2, на останньому - nk. На першому етапі у нас є n1 варіантів вибору, тобто утворюється n1 випадків. На другому етапі в кожному з цих випадків ми може вибрати будь який з n2 варіантів, утворивши n2 подвипадків. Таким чином, після двох етапів буде вже n1* n2 випадків. На третьому етапі в кожному з них ми можемо вибрати будь-який з n3 варіантів і після трьох етапів буде n1 * n2 * n3 випадків. Продовжуючи цей процес, ми отримуємо після всіх етапів n1 * n2 * ... * nk випадків - і це будуть вже остаточні способи. Їх кількість якраз дорівнює добутку кількостей варіантів вибору.
Знову ж, у розв’язанні задач цю властивість можна навіть не формулювати якщо впевнені, що застосували його в правильній ситуації.
Насправді, доводячи п.2, ми користуємося твердженням п.1. Наприклад, як докладніше пояснити, чому після двох етапів є n1*n2 випадків? У нас є взаємовиключні випадки - варіанти вибору на першому етапі, яких n1 штук. У кожному з них є n2 способів зробити вибір на двох етапах (на першому етапі варіант вже відомий, залишилося вибрати n2 варіантів на другому етапі). А щоб знайти загальне число способів зробити вибір на перших двох етапах, треба (відповідно до п.1) скласти n1 чисел, рівних n2, тобто помножити n1 на n2.
3.Загальне правило мультипликативности подвипадків. Якщо спосіб повністю визначається декількома, можливо залежними один від одного, етапами вибору, але кількість варіантів вибору на кожному етапі не залежить від того, як був зроблений вибір на попередніх етапах, то загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.
Доведення: Нічим не відрізняється від доведення попередньго, тому що там користувалися незалежністю від попередніх етапів вибору тільки кількость варіантів на даному етапі.
Дуже поширеною помилкою є переплутування області застосування п.1 та п.2, аж до повного нерозуміння, де і чому треба складати варіанти, а де - множити. Тому тут же проілюструємо їх відмінність на прикладах.
Приклади:
Задача 1. З міста А в місто Б веде 6 доріг, з міста Б у місто В - 4 дороги, і більше ніяких доріг з цих міст не виходить. Скількома шляхами можна проїхати з міста А в місто В?
1.Розв'язання
Розв’язання : На першому етапі нам треба вибрати дорогу, по якій ми поїдемо з А в Б, і тут у нас є 6 варіантів. На другому етапі треба вибрати дорогу, по якій ми поїдемо з Б в В, і там у нас 4 варіанти. Ці два етапи повністю визначають шлях проїзду. Вибір незалежний, тому що по якій би дорозі ми не поїхали в Б, ми зможемо потім поїхати в В за кожної з доріг. Таким чином, ми маємо справу з незалежними етапами вибору, і повинні перемножать варіанти. Всього отримуємо 6 * 4 = 24 різних шляху.
Задача 2. З глухого глухого міста Г, де зроду не було ніяких доріг, проклали 2 нові дороги в місто В з попередньої задачі. Крім того, з міста А з попередньої задачі в місто Г проклали ще 2 нові дороги. Скількома шляхами тепер можна проїхати з міста А в місто В?
Тепер займемося такими видами задач, де треба вибирати якісь предмети або елементи множин (для стандартизації, скажімо, що нам треба з n елементів вибрати k):
4. Вибір з повтореннями, з урахуванням порядку (заповнення позицій елементами множини).
Загальна задача може формулюватися так: "Є алфавіт з n букв. Скільки в цьому алфавіті" слів "які складаються з k літер?" Відповідь буде -nk.
Доведення 1 : У нас є n способів вибрати першу літеру, n способів вибрати другу літеру ... n способів вибрати k-у букву. Всього має k етапів вибору, по n варіантів на кожному. При цьому вибір незалежний (які б не були перші кілька букв, ми можемо вибрати будь-яку наступну). Тому, можна застосувати п.2 і отримати відповідь nk.
Доведення 2: (Тут покажемо, як можна не ссилатися на затвердження п.2, а відтворити його доведення прямо в розв’язанні.) У нас є n способів написати першу букву (це дає n випадків). У кожному з них ми можемо n способами приписати до першої букви другу і отримати n двобуквений слів (утворюється n подвипадків). Всього буде n * n = n2 способів написати перші дві букви. У кожному з цих n2 випадків ми можемо n способами приписати в перших двох буквах третю і отримати n трибуквених слів (знову утворюється n подсвипадків). Всього буде n2 * n = n3 способів написати перші 3 літери. І так далі, поки ми не напишемо все слово - тут число способів буде n в степені, що дорівнює довжині слова, тобто nk.
5. Вибір без повторень, з урахуванням порядку (розкладка в ряд).
Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми послідовно беремо з них k предметів і ставимо в ряд. Скільки є різних способів заповнення ряду?" Число у відповіді має своє спеціальне позначення: Ank і обчислюється за формулою
An k = n * (n-1) * (n-2) * ... * (n-k +1) або Ank = n!/(n-k)! (друга формула виходить при множенні і діленні першою на (n-k)!)
Доведення: У нас є n способів вибрати (взяти і поставити в ряд) перший предмет (назвемо це першим етапом вибору). Далі у нас є, незалежно від того, як обраний перший предмет, n-1 способів взяти другий предмет - в будь-якому випадку, це може бути який завгодно предмет, крім першого обраного. Потім є n-2 способи взяти третій предмет - він може бути який завгодно, крім перших двох обраних и так далі. Звернемо увагу, що число способів вибрати останній, k-й предмет - не n-k, а n-k +1 = n-(k-1), тому що їм може бути будь-який, крім перших k-1 обраних. Разом, ми має k етапів вибору, на кожному з яких число варіантів одно (незалежно від того, як зроблено вибір на попередніх етапах), відповідно, n, n-1 ... n-k +1. Тому, відповідно до п.2 ', ми отримуємо загальне число способів вибору k предметів n*(n-1)* ... * (n-k +1).
Вправи: Придумати доказ з повною підстановкою міркування з п.2, тобто схоже на док-во № 2 попереднього пункту.
6. Перестановки n предметів.
Мається n різних предметів. Скільки у нас способів виставити їх усі в ряд?
Зазвичай це завдання розглядають як окрему і повторюють окремо всі комбинаторні міркування (як в дов-нні 2 п.4). Але зауважимо, що це завдання - окремий випадок п.5 при k = n. Тому відповідь буде Ann = n!
7. Вибір без повторень, без урахування порядку (число сполучень).
Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми беремо з них k предметів і кидаємо в мішок. Скільки є різних способів заповнення мішка?" Число у відповіді має своє спеціальне позначення: Cnk і обчислюється за Сnk=Ank/k! або Cnk=(n*(n-1)*(n-2)*...*(n-k+1))/k! або Cnk=n!/(k!*(n-k)!) (друга і третя формули виходять при підстановці в першу формулу формул для Ank) .[2]
Доведення : Досить довести тільки першу формулу. Нехай ми спочатку вибираємо k предметів послідовно і ставимо в ряд, а потім закидаємо цей ряд у мішок. Число можливих рядів і є An k. Доведемо, що заповнень мішка рівно в k! разів менше, ніж різних рядів - тоді формула буде доведена. (Зауважимо, що один і той же ряд не може переходити в два різних заповнення мішка!) Тепер обгорнемо процес закидання ряду в мішок: нехай у мішку лежать якісь k предметів, а ми дістаємо їх і ставимо в ряд. Згідно п.6, у нас для кожного заповнення мішка буде рівно k! різних рядів. Крім того, за нашим зауваженням, з двох різних заповнень мішка не можна отримати один і той же ряд. Тому рядів рівно в k! разів більше, ніж заповнення мішка.
Взагалі кажучи, Cnk = Cnn-k для будь-якого n> = 0 і 0 <= k <= n.
Приклади застосування пп.4-7:
Задача 3. Скільки існує 6-цифрових чисел, в запису яких є хоча б одна парна цифра?
2.Розв'язання
Розв’язання : У цій задачі треба на самому початку виділити два взаємовиключних випадку: коли ми їдемо через місто Б, і коли їдемо через місто Г. Знайти кількість шляхів у першому випадку - це в точності завдання 1, і відповідь буде 6 * 4 = 24 ( по п.2). Знайти кількість шляхів у другому випадку - це завдання, аналогічна завданню 1, але з відповіддю 2 * 2 = 4. Тепер, за п.1, ці кількості шляхів треба скласти, і у відповіді виходить 24 +4 = 28 шляхів проїзду.
3.Розв'язання
Розв’язання : Розбирати випадки, скільки парних цифр і на яких місцях стоїть у нашому числі - занадто довго і противно. Скористаємося хитрим прийомом: порахувати те, що нам не потрібно. Тобто, вважати будемо числа з одних непарних цифр. Непарні цифри - це "алфавіт" з 5 "букв", а 6-значне число - "слово" з 6 "букв" цього "алфавіту". Таких слів-чисел, згідно п.4, буде рівно 56 штук. А чисел, які нас цікавлять (це всі інші) - рівно 900000-56 = 900000-15625 = 984375 (всього 6-значних чисел 900000).
4.Розв'язання
Розв’язання : Ми маємо справу з вибором 3-х з 6. Вибір відбувається без повторень (кольори повинні бути різні) і з урахуванням порядку (важливо, який колір вгорі, який внизу і який в середині). Згідно п.5, відповіддю буде число A63 = 6 * 5 * 4 = 120.
5.Розв'язання
Розв’язання: Перший професор може вибрати для подарунка 3 книги зі своїх 6, а це можна зробити C63 = 20 способами (див. п.6). Другий професор може вибрати для подарунка 3 книги зі своїх 8, вже C83= 56 способами. Обидва вибори відбуваються незалежно і однозначно визначають спосіб обміну, тому варіанти потрібно перемножувати. Відповідь: C63*C83=56*20=1120 способів.
6.Розв'язання
Розв’язання: У цьому слові є 2 однакові літери (І). Будемо тимчасово вважати їх різними: І1 і І2. За п.6 отримуємо, що тепер можна скласти 5! = 120 слів. Насправді, це в кілька разів більше, ніж потрібно. У скільки ж саме? Зрозуміло, що слова, різняться тільки перестановкою літер І1 і І2 на тих же місцях (наприклад, ЛІ 1 ЯНІ 2 і ЧИ 2 ЯНІ 1), насправді однакові, хоча ми порахували їх як різні. Всього на одних і тих же місцях можна розставити букви І1 і І2 рівно 2! = 2-ма способами, отже, кожного разу ми замість одного слова отримуємо 2 різних. Значить, ми отримали 120:2 = 60 різних слів.
7.Розв'язання
Розв’язання: Визначимо розкладку так: викладемо кульки в ряд і поставимо між ними k-1 перегородку. Те, що зліва від першої перегородки, покладемо в перший ящик, між першою і другою - у другий ... те, що праворуч від останньої - в останній, k-й ящик. Ящик буде порожнім, тільки якщо дві перегородки стоять поруч не розділені кулями, або перегородка стоїть скраю, лівіше або правіше всіх куль. Так давайте це заборонимо! Нехай на кожне з
n-1 місць між n кулями можна поставити не більше однієї з k-1 перегородок. Тобто, з n-1 місць треба буде вибрати k-1, куди ми ставимо перегородки. Звідси отримуємо відповідь: Cn-1k-1.
8.Розв'язання
Розв'язання : Якщо визначати розкладку так само, ставлячи між кулями
k-1 перегородку, то обмежень вже не буде: кульки та перегородки можна ставити в довільному порядку. Давайте вважати, що у нас розставлено в ряд n+k-1 об'єктів: n з них кульки, а інші - перегородки. Тоді розкладка буде визначатися тим, на яких місцях які об'єкти стоять. З n+k-1 місць можна вибрати n місць для куль Cn+k-1n способами, або: k-1 місце для перегородок Cn+k-1k-1 способами. Ці числа рівні і обидва є відповіддю.
Умови та розв'язки олімпіади з комбінаторики
Задача 4. За Конституцією, прапор країни складається з трьох однакових горизонтальних смуг трьох різних кольорів, причому на прапорі можуть бути тільки білий, червоний, жовтий, зелений, блакитний і чорний кольори. Скільки різних прапорів дозволяє така Конституція?
Задача 5. Один професор математики написав 6 книг, інший - 8. Кожен з хоче подарувати іншому 3 свої книги з автографом. Скількома способами вони можуть обмінятися подарунками?
Задача 6. Скільки "слів" можна отримати, переставляючи букви в слові ЛІНІЯ?
Задача 7. Є k ящиків і n> = k Однаково кульок. Скількома способами можна розкласти кульки по ящиках так, щоб жодна скринька не виявилася порожньою?