Зміст шкільного курсу комбінаторики

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

• Множини А і B називають рівнопотужними, якщо можна встановити взаємно однозначну відповідність між їхніми елементами. Це записують таким чином: | A | = | B |.

• Множину А називають зліченною, якщо вона рівно­потужна підмножині ряду натуральних чисел. Якщо множина не є зліченною, то її називають незліченою.

• Кажуть, що множина А скінченна і має n елементів, де n — натуральне число, якщо вона рівно­потужна множині натуральних чисел у межах від 1 до n включно. | A | = n — скорочений запис цього твердження. Якщо множина не є скінченною, то називають її нескінченною.

• Послідовність елементів множини А, що мають індекси у множини В, — це відображення з множини В у множину А, визначене на всій множині В. Якщо множину В не. описано, то вважають, що В — ряд натуральних чисел або множина послідовних натуральних чисел від 1 до певного натурального n: {1, 2, 3, ... , (n ‒ 1), n}. У першому випадку кажуть про нескінченну послідовність, у другому — про скінченну послідовність, що має n членів. При цьому k-им членом послідовності називають образ натурального k для відповідного відображення. Його позначають як a_k, де замість літери а можна записати будь-яку іншу.

• Упорядкувати зліченну множину А, тобто занумерувати натуральними числами елементи А, означає задати таку послідовність, всі члени якої різні, а кожен елемент А с членом цієї послідовності.

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

Традиційними є такі позначення:

\(\{a_k\}^n_{k=1}\) — для послідовності з n елементів;

\(\{a_k\}^{+\infty}_{k=1}\) — для нескінченної послідовності;

\(\{a_k\}\) — для довільної послідовності.

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

Історична довідка. Хоча сліди знань з комбінаторики знайдено у писемних джерелах давніх Індії та Китаю, вважають, що комбінаторика виникла у ХVІ столітті. У житті тогочасних панівних верств суспільства велике місце займали азартні ігри. У карти та кістки вигравали і програвали золото й діаманти, палаци та маєтки, породисті коні та дорогі прикраси. Тому спочатку комбінаторні задачі стосувалися переважно азартних ігор. Цікавило, наскільки часто можна викинути певне число очок, кидаючи дві або три кістки, або отримати двох королів у картковій грі. Такі питання стали рушійною силою розвитку комбінаторики й теорії ймовірностей. Частіше під час багатогодинних ігор помічали певні закономірності (наприклад, що певні комбінації карт чи кісток з'являються частіше за інших), про які гравці повідомляли математикам. А останні пояснювали ці спостереження. Одним з перших зайнявся підрахунком числа різних комбінацій при грі в кістки італійський математик Нікколо Тарталья (бл. 1499‒1557). Подальший розвиток комбінаторики пов'язано з іменами Блеза Паскаля (1623‒1662), П'єра Ферма (1601‒1665), Якоба Бернуллі (1654‒1705), Готфріда Вільгельма Лейбниця (1646‒1716) і Леонарда Ейлера (1707‒1783). Довгий час здавалося, що комбінаторика лежить поза основним руслом розвитку математики. Ситуація істотно змінилася після розквіту дискретної математики та появи електронних обчислювальних машин. З цього моменту комбінаторика переживає період бурхливого розвитку, а її методи широко застосовують при вирішенні різноманітних задач, що мають практичне значення.

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

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

Задача 1. Скільки існує способів взяти з притулку пса при наявності трьох притулків, у яких є відповідно 6, 12 і 32 собаки?

Розв'язання. Зауважимо: вибирають одного пса (всі вони дуже різні! — див. світлини), а не притулок, тому кількість варіантів дорівнює такій сумі: 6 + 12 + 32 = 50.

Розв'язання задачі 1 ілюструє використання такого правила.

Комбінаторне правило додавання. Нехай потрібно виконати деяку дію. яка полягає у виконанні лише однієї з k різних дій, причому що першу дію можна виконати n₁ способами, другу — n₂, ..., k-ту дію — n_k. Тоді цю дію можна виконати такою кількістю дій: n₁ + n₂ + ... + n_k.

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

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

Задача 2. У їдальні є:

• 2 види першої страви;
• 3 види другої страви.

Скількома способами можна у цьому випадку замовити обід з першої та другої страв?

Розв'язання. Шукана кількість дорівнює кількості всіх можливих (упорядкованих) пар такого вигляду:

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

Шукана кількість варіантів дорівнює 2 ∙ 3 = 6.

Розв'язання задачі 2 ілюструє використання наступного правила.

Комбінаторне правило множення. Нехай потрібно виконати деяку дію. яка полягає у послідовному виконанні k таких елементарних дій, що першу дію можна виконати n₁ способами, другу — n₂ способами незалежно від результату першої дії, ..., k-ту дію — n_k способами незалежно від результату виконання всіх попередніх елементарних дій. Тоді цю дію можна виконати такою кількістю дій: n₁ ∙ n₂ ∙ ... ∙ n_k.

Примітка. Бездоганне доведення обох комбінаторних правил для довільної кількості доданків чи множників вимагає застосування принципу математичної індукції.

Задача 3. На таці є 4 груші, 7 слив і 8 абрикосів. Скількома способами можна взяти з цієї таці 2 різних види фруктів, якщо всі фрукти вважати різними?

Розв'язання. З двох певних видів фруктів пару можна вибрати такими кількостями способів:

• груша і слива — 4 ∙ 7 = 28;
• груша і абрикос — 4 ∙ 8 = 32;
• слива і абрикос — 7 ∙ 8 = 56.

Шукана кількість дорівнює такій сумі: 28 + 32 + 56 = 116.

Розв'язання задачі 3 містить розбиття на часткові випадки й послідовне використання комбінаторних правил множення та додавання. Слова: "якщо всі фрукти вважати різними" істотні для однозначного тлумачення умови задачі. Без них можливе тлумачення умови, при якому шуканою кількістю буде 3. У такому випадку перед розв'язуванням задачі потрібно уточнити умову.

Теорема 1. Кількість всіх підмножин n-елементної множини доорівнює 2ⁿ.

Доведення. Задати певну підмножину n-елементної множини означає для кожною з n елементів визначити, чи належить він до цієї множини. Кожну з таких n дій можна здійснити двома способами, а тому, згідно з комбінаторним правилом множення, загальна кількість всіх підмножии n-елементної множини дорівнює такому: $$\underbrace{2\cdot 2\cdot 2 \cdots 2}_{n~~разів} = 2^n.$$

Як бачимо, доведення навіть простих тверджень вимагає уміння уявляти й описувати схему перебору. В останньому випадку — перебору підмножин n-елементної множини за допомогою (як сказали б учні на уроці інформатики) n вкладених циклів, у межах кожного з яких лічильник тактів набуває одного з двох значень. До належного (ґрунтовного) вивчення комбінаторики доцільно змоделювати й описати (учням!) схеми перебору підмножин, перестановок, розміщень і комбінацій множин з малою (до 4) кількістю елементів. І це можуть бути не абстрактні літери чи цифри, а конкретні фігури, вирізані з кольорового картону. Або однокласники у школі чи одногрупники у дитячому садку! В останньому випадку емоційне пожвавлення від гри буде лише на користь. Інакше кажучи, сформулювати відповідне завдання можна, не виходячи за межі побутової лексики й у межах повсякденної діяльності 5-річної дитини. І його розв'язання також не виходить за ці межі.

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

Формулювання й дотримання схеми перебору вимагає зосередження уваги протягом кількох хвилин. Починати тренування такої зосередженості доцільно не з комбінаторних задач, а з чогось простішого. Наприклад, з визначення перетину, об'єднання, різниці й симетричної різниці двох множин з невеликою кількістю елементів: цифр, літер, картонних фігур тощо. Досвід показує, що при першому зіткненні з такими задачами навіть при наявності надрукованих чи написаних означень дій з множинами учні та студенти часто роблять помилки виключно із-за неуважності. Про такі вправи знають методисти з початкової та дошкільної освіти. Щонайменше, в ІПО КУ імені Бориса Грінченка. На жаль, такі вправи не є обов'язковими згідно з державними навчальними програмами. На це має бути добра воля вчителя початкових класів на прохання вчителя старших класів.

Означення 1. Запровадимо такі поняття й позначення.

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

Розміщення (без повторень) елементів з n по k можна означити і як послідовність довжини k з різних елементів n-елементної множини.

Відповідь у термінах означення 1 така: \(P_{29}\), \(A^3_{13}\) і \(C^9_{25}\). Для отримання відповіді у вигляді чисел або хоча б алгоритмів потрібно використати наступне твердження.

Теорема 2. $$P_n = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n \stackrel{\rm def}{=} n!,$$ $$A^k_n = {n!\over (n-k)!},$$ $$C^k_n = {n!\over k! (n-k)!}.$$ Доведення.

• Для взаємно однозначного відображення множини в себе першому елементу відповідає один з n елементів, другому — один з (n ‒ 1)-го (тих, які залишились) і далі. Згідно з комбінаторним правилом множення, кількість таких перестановок дорівнює добутку n ∙ (n ‒ 1) ∙ (n ‒ 2) ∙ 2 ∙ 1. Цей добуток позначають n! (читати "ен-факторіал").
• При виборі впорядкованої підмножини з k елементів на першому місці може опинитися один з n елементів, на другому — один з (n ‒ 1)-го (тих, які залишились), ... , на k-му — один з (n ‒ k + 1)-го. Згідно з комбінаторним правилом множення кількість всіх розміщень дорівнює добутку всіх таких чисел. Для завершення достатньо помножити і поділити цей добуток на (n ‒ k)!.
• Для доведення останньої формули скористаємося комбінаторними міркуваннями, які пов'язують відомі величини з невідомою. Вибрати упорядковану підмножину одним з \(A^k_n\) способів означає вибрати неупорядковану підмножину одним з \(C^k_n\) способів та упорядкувати її одним з P_k способів. Згідно з комбінаторним правилом множення маємо: \(A^k_n = C^k_n\cdot P_k\), тобто $$ {n!\over (n-k)!} = C^k_n \cdot k!,$$ що й потрібно було довести.

Примітка. Для того, щоб доведені твердження справджувалися при k = 0 або при k = n, домовилися вважати, що 0! = 1.

Відповідь до задачі 4:

1. \(P_{29}\) = 29! = 8841761993739701954543616000000;
2. \(A^3_{13}\) = 13!/10! = 13 ∙ 12 ∙ 11 = 1716;
3. \(C^9_{25}\) = 25!/(9! ∙ 16!) = (25 ∙ 24 ∙ 23 ∙ 22 ∙ 21 ∙ 20 ∙ 19 ∙ 18 ∙ 17)/(1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9) = 362880.

Останнє число без застосування обчислювальної техніки можна обчислити, виконуючи по черзі ділення і множення:
25 / 1 ∙ 24 / 2 ∙ 23 / 3 ∙ 22 / 4 ∙ 21 / 5 ∙ 20 / 6 ∙ 19 / 7 ∙ 18 / 8 ∙ 17 / 9.
Діючи аналогічно для інших значень k, n, завжди будемо отримувати проміжний результат у вигляді цілого числа, яке не перевищує кінцевий результат.

Доведення останньої рівності теореми 2 вимагало комбінаторних міркувань у явному вигляді.

Мета вивчення комбінаторики полягає не у запам'ято­вуванні означень, формул для окремих типових завдань, а у розвитку уміння:

• свідомо і правильно застосовувати математичну теорію, у тому числі комбінаторні правила додавання й множення;
• описувати схеми перебору (варіантів), пов'язаних з умовами комбінаторних задач;
• встановлювати взаємно-однозначну відповідність між елементами, переліченими різними схемами перебору — як при доведенні останнього твердження теореми 2 або у доведеннях наступних теорем 3, 4;
• складати та розв'язувати рекурентні співвідношення (про це див. далі);
• висловлювати комбінаторні міркування стисло й доступно для інших.

Ці цінності учні повинні усвідомити як орієнтири для успішного навчання.

Теорема 3. \(C^k_n = C^{n-k}_n.\)

Доведення. Існує взаємно однозначна відповідність між k-елемент­ними підмножи­нами n-елемент­ної множини та їхніми (n ‒ k)-елемент­ними доповнен­нями до n-еле­мент­ної множини. Тому їхні кількості однакові.

Теорема 4. При 0 < k < n справджується рівність: $$C^k_n = C^{k-1}_{n-1} + C^k_{n-1}.$$ Доведення. Нехай а — один з елементів n-елементної множини A. Кількість всіх k-елементних підмножин цієї множини дорівнює сумі кількості k-елементних підмножин, що містять цей елемент, і кількості k-елементних підмножин, які не містять цього елемента. Перші підмножини уворюються об'єднанням {а} з (k ‒ 1)-елементними підмножинами (n ‒ 1)-елементної множини A\{а}, кількість яких дорівнює \(C^{k-1}_{n-1}\). Решту множин утворено способом вибору k елементної підмножини (n ‒ 1)-елементної множини A\{а}, тому кількість останніх дорівнює \(C^k_{n-1}\).

Таблицю, подану нижче, називають трикутником Паскаля.

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

Теорема 5. Для довільного натурального n та довільних числах а та b справджується така рівність: $$(a+b)^n = C^0_n a^n + C^1_n a^{n-1} b + C^2_n a^{n-2} b^2+\cdots +C^{n-1}_n a b^{n-1} +C^n_n b^n,$$ яку називають біномною формулою Ньютона.

Доведення. $$(a+b)^n = \underbrace{(a+b)\cdot (a+b)\cdot (a+b)\cdots (a+b)}_{n~~разів}.$$ Якщо виконати всі дії множення, використовуючи розподільний закон, то отримаємо суму доданків вигляду a^{n ‒ j}b ^j. При утворенні кожного такого доданка беруть участь як співмножники а або b у кожній з дужок правої частини останньої рівності. Доданок a^{n ‒ j}b ^j виникає, якщо вибрати j разів співмножник b з n дужок, що можна зробити \(C^j_n\) способами.

Наслідок 1. Подавши (1 ± 1)ⁿ сумою доданків за допомогою біномної формули Ньютона, маємо: $$C^0_n + C^1_n + C^2_n + C^3_n + \cdots +C^{n-1}_n + C^n_n = 2^n,$$ $$C^0_n - C^1_n + C^2_n - C^3_n +\cdots + (-1)^{n-1} C^{n-1}_n + (-1)^n C^n_n = 0.$$ Перша рівність має прозоре комбінаторне тлумачення: кількість всіх підмножин n-елементної множини дорівнює сумі за індексом k у межах під 0 до n включно кількостей k-елементних підмножин.

Означення 2. Перестановкою з повторенням називають скінченну послідовність, у якій значення елементів можуть збігатися. При загальній кількості значень k кількість різних перестановок з повторенням n₁ разів першого значення, n₂ разів другого значення, ..., n_k разів k-го значення позначають так: P(n₁, n₂, ..., n_k).

Якщо всі значенняі елементів послідовності різні, то ця кількість дорівнює (n₁ + n₂ + ... + n_k)!. Інакше це значення потрібно поділити на добуток кількостей перестановок значень. Маємо: $$P(n_1, n_2, ..., n_k) ={(n_1 + n_2 + \cdots + n_k)! \over n_1! \cdot n_2! \cdot \cdots \cdot n_k!}.$$ Наприклад, перестановкою цифр числа 122333 можна отримати таку кількість різних чисел: $${(1 + 2 + 3)!\over 1! \cdot 2! \cdot 3!} = 60,$$ включаючи й саме число 122333.

Рекурентне співвідношення — це співвідношення (зазвичай рівність), яке виражає значення елемента деякої послідовності (з натуральними індексами) через значення елементів цієї послідовності з меншими індексами.

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

Ефективні алгоритми розв'язання задач з комбінаторики щодо пошуку кількості чи певного розташування зазвичай пов'язані з рекурентними співвідношеннями.

У доведенні теореми 2 неявно використано рекурентні співвідношення:

• P_n = n ∙ P_{n ‒ 1} при P₁ = 1;
• \(A^k_n = n \cdot A^{k-1}_{n-1}\) при \(A^1_n = n\).

Так само, як і неявно використано метод математичної індукції. Повністю коректне (з сучасної точки зору) доведення вимагає явного використання. Очислення елементів (не одного, а наприклад, 10-го рядка) трикутника Паскаля на основі доведеного у теоремі 4 рекурентного співвідношення: $$C^k_n = C^{k-1}_{n-1} + C^k_{n-1}$$ при початкових значеннях \(C^0_n = C^n_n = 1\) ефективніше, ніж використання явної формули з факторіалами.

У 1999 році у місті Києві за ініціативи працівників Київського університету імені Тараса Шевченка було проведено Всеукраїнську конференцію "Актуальні проблеми вивчення природничо-математичних дисциплін у загально-освітніх навчальних закладах України". Ініціатори намагалися донести до відома широкого загалу думку про хибність шляху змін природничо-математичної освіти у школі, обраного Міністерством освіти й підтриманого Академією педагогічних наук та педагогічними університетами. Цікаво, що позиція викладачів математики Київського міжрегіонального інституту удосконалення вчителів імені Бориса Грінченка, попередньо обговорена і підтримана на семінарі методистів районних методичних центрів і голів методичних об'єднань вчителів математики міста Києва і Київської області, збігалася з позицією викладачів КУ ім. Т. Шевченка. Під час секційної доповіді один з викладачів вишу наголошував на неохідності розв'язування учнями повноцінних комбінаторних задач. І назвав, як конкретний приклад, наступну задачу 5. Пікантність ситуації полягала у тому, що тоді у 5 класі використовували підручник з математики за авторством провідного працівника Міністерства (того, якого критикували серед інших), який містив саме цю задачу (!) для конкретних малих значень параметрів n = 5, m = 3. Це правда. Як і те, що повноцінного продовження у старших класах цієї задачі не було.

Задача 5. Скільки існує n-цифрових натуральних чисел, сума цифр кожного з яких дорівнює m?

Розв’язання. Ми не будемо тут розглядати часткові розв'язання:

• явний перебір, наприклад, при n = 2;
• явні перебори можливих наборів цифр та їхніх розташувань, наприклад, при n = 5, m = 3,

На першому місці може стояти одна з (n ‒ n₀) цифр, відмінних від 0, на другому одна з (n ‒ 1), що залишаться, на третьому одна з (n ‒ 2). що залишаться, і так далі. Якщо всі цифри вважати різними, то утворені таким чином послідовності різні, а їхня кількість дорівнює (n ‒ n₀) ∙ (n ‒ 1)!. Останнє число є добутком шуканої кількості й кількостей перестановок множин з n₀, n₁, n₂, ..., n₉ елементів. Отже, шукана кількість дорівнює значенню такого виразу: $${(n-n_0)\cdot (n-1)!\over n_0!\cdot n_1!\cdot n_2!\cdots n_9!}$$ Кількість різних її цифроних чисел, сума цифр кожного з яких дорівнює m, є сумою доданків такого вигляду за всіма послідовностями невід’ємних цілих чисел \(\{n_j\}_{j=0}^9\), для яких маємо:

На перший погляд, задачу 4 розв'язано. Проаналізуємо, наскільки ефективно. Розглянемо випадки m = 3, n = 5 і m = 6, n = 8. Числа 3 і 6 подамо відповідно сумою 5 і 8 цифр. Подання впорядкуємо за спаданням найбільшого числа, яке можна записати за допомогою цих цифр. Такі подання — своєрідна форма запису послідовностей чисел \(\{n_j\}_{j=0}^9\), узгоджених з умовою задачі.

3 + 0 + 0 + 0 + 0 = 2 + 1 + 0 + 0 + 0 = 1 + 1 + 1 + 0 + 0 = 3,

6 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 5 + 1 + 0 + 0 + 0 + 0 + 0 + 0 =
4 + 2 + 0 + 0 + 0 + 0 + 0 + 0 = 4 + 1 + 1 + 0 + 0 + 0 + 0 + 0 =
3 + 3 + 0 + 0 + 0 + 0 + 0 + 0 = 3 + 2 + 1 + 0 + 0 + 0 + 0 + 0 =
3 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = 2 + 2 + 2 + 0 + 0 + 0 + 0 + 0 =
2 + 2 + 1 + 1 + 0 + 0 + 0 + 0 = 2 + 1 + 1 + 1 + 1 + 0 + 0 + 0 =
1 + 1 + 1 + 1 + 1 + 1 + 0 + 0 = 6.

Без запису у знаменнику 0! і 1! відповідь для першого випадку така: $$ 1 + {2\cdot 4!\over 3!} + {3\cdot 4!\over 2!\cdot 3!} = 1 + 8 + 6 = 15.$$ — існує 15 п'ятицифрових чисел, сума цифр кожною з яких дорівнює 3. Для другого випадку відповідь така: $$1 + 2\cdot {2\cdot 7!\over 6!} + {2\cdot 7!\over 6!\cdot 2!} + {3\cdot 7!\over 5!\cdot 2!} + {3\cdot 7!\over 5!} + {3\cdot 7!\over 5!\cdot 3!} + {4\cdot 7!\over 4!\cdot 3!} + {4\cdot 7!\over 4!\cdot 2!\cdot 2!} + {5\cdot 7!\over 3!\cdot 4!} + {6\cdot 7!\over 2!\cdot 6!} =$$ $$= 1 + 28 + 7 + 63 + 126 + 21 + 140 + 210 + 175 + 21 = 792.$$ Таким чином, існує 792 восьмицифрових числа, сума цифр кожного з яких дорівнює 6.

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

Але той, хто знайомий з гаслом пошуку ефективного розв'язку комбінаторної задачі, одразу почне пошук рекурентного співідношення. І доволі швидко отримає таке розв'язання.

Теорема 6. Позначимо через с(n, m) кількість n-цифрових чисел, сума цифр кожного з яких дорівнює m. Тоді:

Доведення. Безпосередньою перевіркою можна пересвідчитися в істинності перших двох наборів рівностей для початкового значення n = 1. Доведемо рекурентне співвідношення. Будь-яке n-цифрове число можна отримати шляхом дописування до (n ‒ 1)-цифрового числа праворуч (у розряд одиниць) однієї з цифр. При цьому сума цифр числа зростає на величину дописуваної цифри. Таким чином, у рекурентному співвідношенні перший доданок ліворуч від знаку рівності відповідає дописуванню 0, другий — дописуванню 1, третій — дописуванню 2 і таке інше.

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

• перший рядок містить величини m: 1, 2, 3, ... , 10;
• перший стовпчик містить величини n: 1, 2, 3, ... , 20;
• решта елементів таблиці — відповідні величини c(n, m);
• у другому стовпчику c(n, 1) = 1;
• при n > 1 маємо безпосередній наслідок доведеного рекурентного співвідношення при m ≤ 10:
  с(n, m) = с(n ‒ 1, m) + с(n, m ‒ 1).

Теорема 7. У позначеннях теореми 6:

• при m > 9n маємо: c(n, m) = 0;
• при m ≤ 9n маємо: c(n, m) = c (n, 9n ‒ m + 1).

Доведення. Перше твердження теореми є наслідком того, що сума цифр n-цифрового числа не перевищує 9n. Доведемо друге твердження, поставивши кожному n-цифровому числу х із сумою цифр m у взаємно однозначну відповідність n-цифрове число $$10\underbrace{99...99}_{~~~~n-1\\дев'ятка} - x$$ сума цифр якого дорівнює 9n ‒ m + 1. При цьому перша (відмінна від 0) цифра і₁ числа х замінюється на 10 ‒ і₁, а кожна з наступних цифр і_j, що перебувають у межах від 0 до 9 включно, замінюється на 9 ‒ і_j (в тих самих межах) при j = 2, 3, ..., n. З існування взаємно однозначної відповідності й випливає рівність кількостей.

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

Змінимо (параметризуємо) умову задачі 3.

Задача 3′. На таці є n видів фруктів у кількостях k₁, k₂, ... , k_n. Скількома способами можна взяти з цієї таці 2 різних види фруктів, якщо всі фрукти вважати різними?

Розв'язання′. Запровадимо такі позначення:

• m_j — шукана кількість при n = j;
• l_j = k₁ + k₂ + ... + k_j

Про таке можна не говорити при першому знайомстві з комбінаторикою. Але про це необхідно говорити у 8-9 класах.

У посібниках з комбінаторики трапляються також завдання на застосування формули включень-виключень. Наприклад, наступну задачу 6 можна зустріти у посібниках різних авторів.

Задача 6. У готелі 47 працівників розмовляють анґлійською, 35 — німецькою, 23 — обома цими мовами. Скільки працівників цього готелю розмовляють хоча б однією з цих мов?

Роз'язання. Запровадимо такі позначення:

• A₁ — множина тих працівників готелю, які розмовляють анґлійською;
• A₂ — множина тих працівників готелю, які розмовляють німецькою.

Ці множини можна зобразити кругами Ейлера.

Маємо: | A₁ | = 47, | A₂ | = 35, | A₁ ∩ A₂ | = 23 — згідно з умовою задачі,

| A₁ ∪ A₂ | = | A₁ \ A₂ | + | A₁ ∩ A₂ | + | A₂ \ A₁ |
| A₁ ∪ A₂ | = | A₁ | ‒ | A₁ ∩ A₂ | + | A₁ ∩ A₂ | + | A₂ | ‒ | A₁ ∩ A₂ |
| A₁ ∪ A₂ | = | A₁ | + | A₂ | ‒ | A₁ ∩ A₂ | = 47 + 35 ‒ 23 = 59.

Відповідь. 59 працівників готелю розмовляють анґлійською або німецькою.

У записі розв'язання використано такі традиційні позначення:

• A ∪ B — для об'єднання множин A, B — множини всі тих елементів, які належать хоча б одній з множин A, B;
• A ∩ B — для перетину множин A, B — множини всі тих елементів, які належать одночасно обом множинам A, B;
• A \ B — для різниці множин A, B — множини всі тих елементів, які належать A і не належать B;

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

При зміні умови останньої задачі у сторону збільшення кількості мов проявиться нетехнологічність поданого способу розв'язання:

• щодо виведення формул чи альтернативи — запису висловлювань;
• щодо унаочнення кругами Ейлера (починаючи з 4 мов);
• щодо позначення (запису) множин.

Наступна теорема узагальнює рівність, виділену жирним шрифтом у розв'язанні задачі 6, і робить розв'язання та його запис технологічними. Назва "формула включень-виключень" вказує на те, що для обліку загальної кількості певні множини буде включено у облік (див. доданки зі знаком "+"), а інші буде виключено з обліку (див. доданки зі знаком "‒") з метою компенсувати багатократний облік.

Теорема 8 [формула включень-виключень]. Для довільного натурального n ≥ 2 і для довільних скінченних множин A₁, A₂, ... , A_n справджується така рівність:

• спочату здійснено додавання за всіма множинами;
• потім — віднімання за всіма неупорядкованими парами різних множин, кількість яких дорівнює \(C_n^2\);
• потім — додавання за всіма неупорядкованими трійками різних множин (при n ≥ 3), кількість яких дорівнює \(C_n^3\);
• потім — віднімання за всіма неупорядкованими четвірками різних множин (при n ≥ 4), кількість яких дорівнює \(C_n^4\) ...

В останньому рядку записано кількість елементів перетину всіх множин з точністю до знаку. Кількість усіх членів правої частини рівності дорівнює кількості непорожніх підмножин n-елементної множини, тобто 2^{n ‒ 1}.

Доведення (методом математичної індукції за кількістю множин n).

• База індукції. При n = 2 формула набуває вигляду:
  | A₁ ∪ A₂ | = | A₁ | + | A₂ | ‒ | A₁ ∩ A₂ |,

  що вже доведено у розв'язанні задачі 6.

• Припущення індукції. Припустимо, що формула формула включень-виключень справджується при певному натуральному n = k.

• Крок індукції. Маємо:

  | A₁ ∪ A₂ ∪ ... ∪ A_k ∪ A_{k + 1} | = | (A₁ ∪ A₂ ∪ ... ∪ A_k) ∪ A_{k + 1} |
  = | (A₁ ∪ A₂ ∪ ... ∪ A_k) | + | A_{k + 1} | ‒ | (A₁ ∪ A₂ ∪ ... ∪ A_k) ∩ A_{k + 1} |
  = | (A₁ ∪ A₂ ∪ ... ∪ A_k) | + | A_{k + 1} | ‒ | (A₁ ∩ A_{k + 1}) ∪ (A₂ ∩ A_{k + 1}) ∪ ... ∪ (A_k ∩ A_{k + 1}) |.

  У першому і третьому доданках останнього рядка в об'єднанні беруть участь по k множин. Для кожного з цих доданків згідно з припущенням індукції можна застосувати формулу включень-виключень. У результаті буде отримано всі складові для формули включень-виключень при n = k + 1 з потрібними знаками:

  • з першого доданку — всі скадові, у записі яких немає A_{k + 1};
  • з третього доданку — всі скадові, у записі яких є A_{k + 1} і є перетин щонайменше 2 множин.

Задача 7. З працівників готелю 47 розмовляють анґлійською, 35 — німецькою, 20 — французькою, 23 — анґлійською і німецькою, 12 — анґлійською і французькою, 11 — німецькою і французькою, 5 — анґлійською, німецькою і французькою. Скільки працівників цього готелю розмовляють хоча б однією з цих мов?

Роз'язання. Згідно з формулою включень-включень шукана кількість дорівнює: 47 + 35 + 20 ‒ 23 ‒ 12 ‒ 11 + 5 = 61.

Задача 8. Скільки є натуральних чисел, які не перевищують 1000 і не кратні кожному з таких чисел: 4, 10, 14, 35?

Роз'язання. Кількість натуральних чисел, які не перевищують натуральне N і кратні натуральному k, дорівнює [N/k] — цілій частині відношення N/k. Натуральне число кратне кільком натуральним числам тоді й лише тоді, коли воно кратне їхньому найменшому спільному кратному (НСК). Згідно з формулою включень-включень кількість натуральних чисел, які не перевищують 1000 і кратні хоча б одному з чисел: 4, 10, 14, 35, дорівнює значенню такого виразу:

+ [1000/4] + [1000/10] + [1000/14] + [1000/35]
‒ [1000/НСК(4,10)] ‒ [1000/НСК(4,14)] ‒ [1000/НСК(4,35)] ‒ [1000/НСК(10,14)] ‒ [1000/НСК(10,35)] ‒ [1000/НСК(14,35)]
+ [1000/НСК(4,10,14)] + [1000/НСК(4,10,35)] + [1000/НСК(4,14,35)] + [1000/НСК(10,14,35)]
‒ [1000/НСК(4,10,14,35)].

Після обчислення НСК маємо:

+ [1000/4] + [1000/10] + [1000/14] + [1000/35]
‒ [1000/20] ‒ [1000/28] ‒ [1000/140] ‒ [1000/70] ‒ [1000/70] ‒ [1000/70]
+ [1000/140] + [1000/140] + [1000/140] + [1000/70]
‒ [1000/140],

тобто 250 + 100 + 71 + 28 ‒ 50 ‒ 35 ‒ 7 ‒ 14 ‒ 14 ‒ 14 + 7 + 7 + 7 + 14 ‒ 7 = 343.

А шукана кількість дорівнює 1000 ‒ 343 = 657.

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

Теорема 9. Нехай канонічне розкладення на прості множники натурального числа m має такий вигляд: $$m = a^{n_a}\cdot b^{n_b}\cdots c^{n_c}.$$ Тоді кількість всіх різних натуральних дільників m дорівнює: $$(n_а+1)\cdot (n_b+1)\cdots (n_c+1).$$ Доведення. Всі натуральні дільники m вичерпуються числами такого вигляду: $$a^{j_a}\cdot b^{j_b}\cdots c^{j_c},$$ де \(0 \leq j_a \leq n_a\), \(0 \leq j_b \leq n_b\), ..., \(0 \leq j_c \leq n_c\). Кількість всіх різних добутків збігається з кількістю всіх різних можливих наборів (\(j_a,~j_b,~...,~j_c\)), що задовольняють нерівності, тобто дорівнює добутку збільшених на 1 степенів простих чисел.

Задача 9. Знайти всі натуральні числа, що діляться на 6 і мають 35 різних натуральних дільників.

Розв'язання. 6 = 2 ∙ 3, тому шукане число ділиться на прості числа 2 ї 3. Нехай \(2^{n_2}\cdot 3^{n_3}\cdot r^{n_r}\cdots s^{n_s}\) — канонічне розкладення на прості множники шуканого числа. Тоді, згідно з доведеною теоремою 9 та умовою задачі, маємо: $$(n_2+1)\cdot (n_3+1)\cdot (n_r+1)\cdots (n_s+1) = 5\cdot 7.$$ В останній рівності ліворуч перші два множники більші, ніж 1, а праворуч — добуток двох простих чисел. Отже, шукане число не має простих дільників, відмінних від 2 чи 3. Маємо:

Відповідь. 2⁴ ∙ 3⁶ або 2⁶ ∙ 3⁴.

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

Невід'ємною частиною змісту навчання є сукупність навчальних завдань і завдань для перевірки набутих компетентностей. При виборі збірників завдань доцільно надавати перевагу таким, які меншою кількістю задач покривають всю теорію і ключові прийоми розв'язування задач. Далі подано два таких джерела, за якими автору поталанило працювати з учнями Українського фізико-математичного ліцею Київського національного університету імені Тараса Шевченка. Першого достатньо для поглибленого рівня вивчення математики. Другий збірник призначено для студентів вишів. Зміст завдань §2 його розділу 1 не виходить за межі понять і прийомів, передбачених навчальними програмами для загально освітніх навчальних закладів. Хоча містить умови доволі складних комбінаторних задач. Цей посібник корисний для індивідуальної чи гурткової роботи з тими, хто прагне ґрунтовно опанувати комбінаторикою.

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

1. Вишенський В.А., Перестюк М.О., Самоленко А.М. Збірник задач з математики. — Київ, Либідь, 1993, 344 с. — див. у §5 умови й відповіді.

2. Дороговцев А.Я., Сільвестров Д.С., Скороход А.В., Ядренко М.Й. Теорія ймовірностей. Збірник задач. За загальною редакцією члена-корреспондента АН УРСР Скорохода А.В. — Київ, Вища школа, 1976, 384 с. — див. у §2 розділу 1 умови й відповіді.

Переглянувши у навчальних матеріалах умови складних задач, вчитель, якого навчали комбінаториці поверхнево, може задуматися: "Чи зможу я навчити учнів комбінаторному мисленню, якщо я сам своєчасно цьому не навчився?". Це правда, що у такому випадку деякі складні задачі можуть виявитися непідйомними для нього. Але від учителя ніхто не вимагає уміння розв'язувати задачі! Його завдання полягає в організації навчання:

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

Зміст цитованих вище джерел задач свого часу було успішно апробовано на учнях Республіканської заочної фізико-математичної школи при КДУ ім. Т.Г.Шевченка. Не у формі саме цих збірників, а маленьких посібників маже кишенькового формату з циклу "Бібліотека фізико-математичної школи". Набуті таким чином знання дозволяли випускникам провінційних шкіл з філологічним ухилом бути на рівні випускників фізико-математичної школи-інтернату "Феофанія" (тепер УФМЛ КНУ імені Тараса Шевченка) чи спеціалізованої школи № 145 м. Києва (тепер природничо-науковий ліцей № 145). А тоді ці школи надсилали (і цілком заслужено) свої команди на Республіканську олімпіаду з математики! Це була справді ефективна дистанційна освіта.

При наявності таких цих джерел з відповідями немає проблем у виконанні перших 4 перелічених вище завдань учителя. А при виконанні останнього менш досвідчений учитель може виявитися навіть кращим порадником, бо сам нещодавно долав схожі проблеми. У нього більше шансів зрозуміти причину невдач і пояснити іншими словами те саме. Та без уміння аналізувати й досконалого володіння словом годі сподіватися на гарний результат. І не лише щодо комбінаторики. Інакше кажучи, діяти потрібно як досвідчений (і, можливо, цинічний) політик, для якого немає поганих і хороших подій. Всі події такий політик поділяє на такі, які використав, і такі, які не використав.