- •Мирон Маланюк, Василь Кравчук Метод математичної індукції та елементи комбінаторики
- •Передмова редактора
- •§1. Метод математичної індукції
- •§2. Прості задачі комбінаторного типу
- •§3. Загальні правила комбінаторики
- •§4. Основні поняття комбінаторики
- •4.1. Перестановки
- •4.2. Розміщення
- •4.3. Комбінації
- •4.4. Деякі комбінаторні тотожності
- •§5. Сполуки з повторенням елементів
- •5.1. Перестановки з повтореннями
- •5.2. Комбінації з повтореннями
- •5.3. Розміщення з повтореннями
- •§6. Приклади розв’язування комбінаторних задач
- •§7. Формула бінома Ньютона
- •Заключне зауваження
- •Задачі для самостійного розв’язування Завдання і
- •Обов’язкові задачі
- •Додаткові задачі
- •Завдання 2 Обов’язкові задачі
- •Додаткові задачі
- •Задачі для підготовки до математичних олімпіад
- •Відповіді та вказівки до задач математичних олімпіад
- •Список рекомендованої літератури
- •§1. Метод математичної індукції 8
5.1. Перестановки з повтореннями
Нехай маємо множину, яка складається з елементів a, b, c, d, …, l. Перестановки, в яких елемент aповторюєтьсяразів, елементbповторюєтьсяразів, елементисіd— відповідноіразів, і т. д., а останній елементlповторюєтьсяразів, називаютьперестановкамиз повтореннями.Кількість усіх можливих таких перестановок позначають символом Наприклад, перестановками з повтореннями, у яких елементаповторюється 2 рази, а елементb— 3 рази, є
ааbbb аbаbb аbbаb аbbbа bааbb
bаbаb bаbbа bbааb bbаbа bbbаа.
Таких перестановок є 10. Тому 10.
Справджується така теорема.
Теорема 4.Кількість різних перестановок з повтореннями, у яких елементиа,b,c,d, …,lповторюються відповідно,,,, …,разів, визначається формулою:
Доведення цієї теореми неважко провести, узагальнюючи спосіб розв’язування попередньої задачі, пов’язаної зі словом математика. Зробіть це самостійно.
Задача. Скільки шестицифрових чисел можна записати, користуючись цифрами 1, 2, 3, якщо у кожному з чисел цифра 1 повинна повторюватися 2 рази, цифра 2 — 3 рази, цифра 3 — 1 раз?
■ Шукана кількість шестицифрових чисел дорівнює■
5.2. Комбінації з повтореннями
Розв’яжемо таку задачу. У крамниці продаються листівки. До послуг покупців є 15 різних видів листівок. Студентці потрібно привітати зі святом своїх рідних і друзів, а для цього необхідно придбати 12 листівок. Звичайно, можна закупити всі 12 однакових листівок, можна також придбати по декілька однакових листівок, а можна закупити і всі різні листівки. Скільки існує різних способів здійснення такої покупки?
■ Позначимо кількість цих способів символомДля спрощення міркувань кожній конкретній можливості здійснення покупки поставимо у відповідність 14 вертикальних рисок (умовних перегородок між наборами однакових листівок) і 12 знаків + за таким правилом. Перед першою рискою запишемо стільки знаків +, скільки листівок першого виду виявилося у покупці. Між першою і другою рисками — стільки знаків + , скільки було куплено листівок другого виду. І так далі, нарешті, після 14-ї риски відповідною кількістю знаків + позначимо кількість куплених листівок останнього 15-го виду. Якщо яких-небудь листівок не вибрали зовсім, то між відповідними рисками не ставитимемо нічого. Наприклад, покупці з п’яти листівок 2-го виду та семи листівок 5-го виду відповідатиме символ++++++++++++. Очевидно, що й навпаки, будь-якій такій послідовності з 14 рисок та 12 знаків + відповідатиме певна можлива схема покупки листівок. Для розв’язання задачі, отже, необхідно з’ясувати, скількома способами можна утворити описані символи, у яких вертикальні риски повторюються 14 разів, а знаки + — 12 разів. Очевидно, що кількість таких способів дорівнює■
Узагальнимо тепер спосіб розв’язування цієї задачі. Припустимо, що нам задано набір з nрізних елементів. З’ясуємо, скількома способами можна підібратиkелементів, кожний із яких є одним з елементів заданого набору. Такі множини називаютькомбінаціями з повтореннями ізданих n елементів по k елементів, а їхню кількість позначають символомНаприклад, комбінаціями з повтореннями із двох елементіваіbпо три елементи є:ааа,ааb,аbb,bbb. Отже,Зрозуміло, що приусікомбінацій без повторень входять до складу комбінацій з повтореннями
Сформулюємо таку теорему:
Теорема 5. Кількість різних комбінацій з повтореннями ізnелементів поkвизначається формулою:
■ Аби порахувати кількість комбінацій з повтореннями із nелементіва1,а2, …,аnпоk, встановимо таку взаємно-однозначну відповідність. Кожній конкретній комбінації з повтореннями із елементіва1,а2, …,аnпоkпоставимо у відповідність послідовність ізn– 1 нуля таk одиниць таким чином, щоб: перед першим нулем стояло стільки одиниць, скільки разів у даній комбінації зустрічається елемента1; між першим і другим нулями впишемо стільки одиниць, скільки разів зустрічається елемента2; між другим і третім нулями впишемо стільки одиниць, скільки разів зустрічається елемента3, і т. д. Після останнього (n– 1)-го нуля запишемо стільки одиниць, скільки разів зустрічається елементаn(якщо якийсь елемент не зустрічається зовсім, то на відповідному йому місці не записуємо нічого). Кількість таких послідовностей виражається числомщо дорівнює кількості перестановок з повтореннями, у яких 1 повторюється kразів, а 0 —п– 1 разів. Отже,■
Задача. Скількома способами можна розподілити 30 зошитів між чотирма учнями?
■ Нехай при деякому розподілі першому учневі дісталося n1, другому — n2,третьому —n3а четвертому —n4зошитів. Цей розподіл можна схематично зобразити так:
де n1 +n2 +n3 +n4 30.Тепер очевидно, що кількість можливих розподілів дорівнює кількості комбінацій з повтореннями із 4 елементів по 30, тобто числу■