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

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

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

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

\(\{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 різних дій, причому що першу дію можна виконати n1 способами, другу — n2, ..., k-ту дію — nk. Тоді цю дію можна виконати такою кількістю дій: n1 + n2 + ... + nk.


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

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


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

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

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

(вид першої страви, вид другої страви),

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

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

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

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

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

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

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

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

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

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

Доведення. Задати певну підмножину 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-елементної множини.

Задача 4.
  1. У класі навчається 29 учнів. Скількома способами їх можна розташувати у шеренгу по одному?
  2. Скільки є варіантів завершення спортивного змагання (тобто визначення 1, 2 і 3 місць) серед 13 учасників?
  3. Скільки є варіантів формування туристичної групи з 9 чоловік учнів класу, у якому навчається 25 учнів?

Відповідь у термінах означення 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)!}.$$ Доведення.

Примітка. Для того, щоб доведені твердження справджувалися при 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 вимагало комбінаторних міркувань у явному вигляді.

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

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


Теорема 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}\).

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

0
\(C^0_1\)\(C^1_1\)
\(C^0_2\)\(C^1_2\)\(C^2_2\)
\(C^0_3\)\(C^1_3\)\(C^2_3\)\(C^3_3\)
\(C^0_4\)\(C^1_4\)\(C^2_4\)\(C^3_4\)\(C^4_4\)
\(C^0_5\)\(C^1_5\)\(C^2_5\)\(C^3_5\)\(C^4_5\)\(C^5_5\)
........................................................................

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

1
11
121
1331
14641
15101051

Теорема 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~~разів}.$$ Якщо виконати всі дії множення, використовуючи розподільний закон, то отримаємо суму доданків вигляду an ‒ jb j. При утворенні кожного такого доданка беруть участь як співмножники а або b у кожній з дужок правої частини останньої рівності. Доданок an ‒ jb j виникає, якщо вибрати j разів співмножник b з n дужок, що можна зробити \(C^j_n\) способами.

Наслідок 1. Подавши (1 ± 1)n сумою доданків за допомогою біномної формули Ньютона, маємо: $$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 кількість різних перестановок з повторенням n1 разів першого значення, n2 разів другого значення, ..., nk разів k-го значення позначають так: P(n1, n2, ..., nk).

Якщо всі значенняі елементів послідовності різні, то ця кількість дорівнює (n1 + n2 + ... + nk)!. Інакше це значення потрібно поділити на добуток кількостей перестановок значень. Маємо: $$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 неявно використано рекурентні співвідношення:

Так само, як і неявно використано метод математичної індукції. Повністю коректне (з сучасної точки зору) доведення вимагає явного використання. Очислення елементів (не одного, а наприклад, 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?

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

які доречні відповідно у початковій школі й у 5 класі.

Розглянемо 3-ій рівень розв'язання цієї задачі, вивівши формулу для кількості різних n-цифрових чисел, записаних за допомогою n0 нулів, n1 одиниць, n2 двійок, ... , n9 дев'яток при

n = n0 + n1 + n2 + ... + n9.

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

m = n1 + 2 ∙ n2 + 3 ∙ n3 + ... + 9 ∙ n9.

На перший погляд, задачу 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. Тоді:

с(1, 1) = с(1, 2) = с(1, 3) = с(1, 4) = с(1, 5) = с(1, 6) = с(1, 7) = с(1, 8) = с(1, 9) = 1,

с(1, 10) = с(1, 11) = с(1, 12) = ... = 0,

с(n, m) = с(n ‒ 1, m) + с(n ‒ 1, m ‒ 1) + с(n ‒ 1, m ‒ 2) + ... + с(n ‒ 1, max (1, m ‒ 9).

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

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

n\m 12315678910
1111111111 0
2123456789 9
313610152128364554
4141020355684120165219
515153570126210330495714
616215612625246279212872001
7172884210462924171630035004
8183612033079217163432643511439
9190451654951287300364351287024309
101105522071520025005114402431048619
1111166286100130038008194484375892377
121127836413654368123763182475582167959
1311391455182061881856450388125970293929
14114105560238085682713277520203490497419
1511512068030601162838760116280319770817189
16116136816387615504542641705444903141307503
17117153969484520349746132451577354712042974
18118171114059852633410094734610410815753124549
19119190133073153364913459648070015622754686824
20120210154088554250417710065780022200756906899

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

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


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


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

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

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

Маємо:
початкові значення: l2 = k1 + k2; m2 = k1k2;
рекурентні співвідношення: lj + 1 = lj + kj + 1; mj + 1 = mj + kj + 1lj при j ≥ 2.
При такому розв'язанні кількість виконуваних дій пропорційна n, а не n2, як при розгляді кожної пари.

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


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

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

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

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

Маємо: | A1 | = 47, | A2 | = 35, | A1A2 | = 23 — згідно з умовою задачі,

| A1A2 | = | A1 \ A2 | + | A1A2 | + | A2 \ A1 |
| A1A2 | = | A1 | ‒ | A1A2 | + | A1A2 | + | A2 | ‒ | A1A2 |
| A1A2 | = | A1 | + | A2 | ‒ | A1A2 | = 47 + 35 ‒ 23 = 59.

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


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

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

  1. Кількість працівників готелю, що розмовляють хоча б однією з мов — анґлійською або німецькою — дорівнює сумі кількостей:
    • тих, хто розмовляє лише англійською;
    • тих, хто розмовляє і англійською, і німецькою;
    • тих, хто розмовляє лише німецькою.
  2. Кількість тих, хто розмовляє лише англійською, дорівнює різниці кількостей тих, хто розмовляє англійською, і тих, хто розмовляє і англійською, і німецькою. А кількість тих, хто розмовляє лише німецькою, дорівнює різниці кількостей тих, хто розмовляє німецькою, і тих, хто розмовляє і англійською, і німецькою.
  3. Після зведення подібних доданків отримуємо суму кількостей тих, хто розмовляє англійською, і тих, хто розмовляє німецькою, без кількості тих, хто розмовляє і англійською, і німецькою.

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


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

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

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

| A1A2 ∪ ... ∪ An | = | A1 | + | A2 | + ... + | An |
‒ | A1A2 | ‒ | A1A3 | ‒ ... ‒ | A1An | ‒ | A2A3 | ‒ | A2A4 | ‒ ... ‒ | An ‒ 1An |
+ | A1A2A3| + | A1A2A4| + ... + | An ‒ 2An ‒ 1An |
‒ | A1A2A3A4| ‒ | A1A2A3A5| ‒ ... ‒ | An ‒ 3An ‒ 2An ‒ 1An | + ...
+ (‒1)n ‒ 1 | A1A2 ∩ ... ∩ An ‒ 1An |,
де:

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

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

Задача 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. Маємо:

\(\cases{n_2+1=5\cr n_3+1=7}\) або \(\cases{n_2+1=7\cr n_3+1=5}\).

Відповідь. 24 ∙ 36 або 26 ∙ 34.

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


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

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


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

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


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

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

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


Текст упорядкував Олександр Рудик з використанням матеріалів посібника:
Рудик О.Б. Початки авлгебри, аналізу, аналітичної геометрії і теорії ймовірностей.
— Тернопіль: Навчальна книга – Богдан, 2005, 416 с.