2.1. Методика вивчення елементів комбінаторики

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

У науці та практиці часто зустрічаються задачі, розв'язуючи які доводиться складати різні комбінації з кінцевого числа елементів і підраховувати кількість комбінацій. Такі завдання отримали назву комбінаторних завдань, а розділ математики, в якому розглядаються подібні завдання, називають комбінаторика. Слово «комбінаторика» походить від латинського слова combinare, яке означає «сполучати, поєднувати». Методи комбінаторики знаходять широке застосування у фізиці, хімії, біології, економіці, теорії ймовірностей та інших галузях знань [10].

Наведемо приклади деяких комбінаторних задач.

1) Скількома способами можна розташувати в електричному ланцюзі 7 різних приладів?

2) Скільки словників треба видати, щоб можна було безпосередньо виконувати переклади з будь-якого з 5 мов: російської, англійської, французької, німецької, італійської, на будь-який інший з цих 5 мов?

3) Вова точно пам'ятає, що у формулі азотної кислоти поспіль йдуть літери H, N, O і що є один нижній індекс — чи то двійка, чи то трійка. Скільки є варіантів, у яких індекс стоїть не на другому місці?

4) Скільки різних типів гамет може дати гібрид, гетерозиготний по 3 незалежним ознаками?

5) Перерахувати всі тризначні числа, у запису яких зустрічаються тільки цифри 1 і 2.

6) Три друга — Антон, Борис і Віктор — придбали два квитки на футбольний матч. Скільки різних варіантів відвідування футбольного матчу для трьох друзів?

Таким чином, розрізняють такі типи комбінаторних завдань:

· завдання, в яких потрібно перерахувати всі рішення (приклад 5).

· завдання, що складаються у вимозі виділити з усіх можливих рішень таке, яке задовольняє заданому додатковій вимозі (приклад 3).

· завдання, в яких потрібно підрахувати число рішень (приклад 1, 2, 6, 4) [25].

Процес навичок підрахунку комбінаторних об'єктів можна розчленувати на три етапи в залежності від часу навчання та методів підрахунку:

- підрахунок методом безпосереднього перебору;

- підрахунок з використанням комбінаторних принципів;

- підрахунок з використанням формул комбінаторики [41].

Кожен з цих етапів готує основу для формування навичок наступних етапів. Тому на початковому етапі з учнями потрібно обов'язково розглянути безформульні методи розв’язування задач [26].

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

Перебір всіх можливих варіантів

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

Приклад 1. З групи тенісистів, до якої входять чотири людини — Антонов, Григор'єв, Сергієв і Федоров, тренер виділяє пару для участі у змаганнях. Скільки існує варіантів вибору такої пари?

Складемо спочатку всі пари, в які входить Антонов (для стислості будемо писати перші літери прізвищ). Отримаємо три пари: АГ, АС, АФ.

Випишемо тепер пари, в які входить Григор'єв, але не входить Антонов. Таких пар дві: ГС, ГФ.

Далі складемо пари, в які входить Сергієв, але не входить Антонов і Григор'єв. Така пара тільки одна: СФ.

Інших варіантів складання пар немає, так як всі пари, в які входить Федоров, вже складені.

Отже, ми отримали 6 пар: АГ, АС, АФ, ГС, ГФ, СФ. Значить, всього існує 6 варіантів вибору тренером пари тенісистів з даної групи.

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

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

Приклад 2. Три друга — Антон, Борис і Віктор — придбали два квитки на футбольний матч на 1-е і 2-е місця першого ряду стадіону. Скільки у друзів є варіантів зайняти ці два місця на стадіоні?

Якщо на матч підуть Антон і Борис, то вони можуть зайняти місця двома способами: 1-е місце - Антон, 2-е - Борис, або навпаки. Аналогічно Антон і Віктор, Борис і Віктор. Таким чином, ми отримали 6 варіантів: АБ, БА, АВ, ВА, БВ, СБ [38].

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

Завдання для учнів:

1. Перерахувати знайомі види чотирикутників.

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

3. Скільки двозначних чисел можна скласти, використовуючи цифри 1, 2, 3, за умови, що цифра в числі не може повторюватися? (Перебір з обмеженням).

4. (Усно) Важливий чи ні порядок у наступних вибірках (комбінаціях):

а) капітан волейбольної команди та його заступник;

б) три ноти в акорді;

в) «шість людей залишаться прибирати клас!»;

г) дві серії для перегляду з нового багатосерійного фільму.

5. Придумайте самі чотири різні ситуації, у двох з яких порядок вибору важливий, а в двох — ні.

6. Стадіон має 4 входи: A, B, C, D. Вкажіть всі можливі способи, якими відвідувач може увійти через один вхід, а вийти через інший. Скільки таких способів?

7. У магазині продають кепки трьох кольорів: білі, червоні і сині. Кіра і Олена купують собі по одній кепці. Скільки існує різних варіантів покупок для цих дівчаток? Перерахуйте їх [30].

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

Задача 1. У місті N є два університети — політехнічний та економічний. Абітурієнту подобаються три факультети в політехнічному університеті та два — в економічному. Скільки можливостей має студент для вступу в університет?

Розв’язання: позначимо буквою А множину факультетів, які обрав студент в політехнічному університеті, а буквою В — в економічному. Тоді А={m, n, k}, B={p, s}. Оскільки ці множини не мають спільних елементів, то загалом абітурієнт має 3 + 2 = 5 можливостей вступати в університет. Описану ситуацію можна узагальнити у вигляді твердження, яке називається правилом суми.

Якщо елемент деякої множини А можна вибрати m способами, а елемент множини В — n способами. То елемент з множини А або з множини В можна вибрати m+ n способами.

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

Задача 2. Родина з чотирьох осіб планує літній відпочинок. Діти обрали чотири міста — Одесу, Євпаторію, Ялту, Феодосію. Батьки визначилися з базами відпочинку так: в Одесі — 1, у Євпаторії — 3, в Ялті — 2, в Феодосії — 2. Скільки можливостей вибору літнього відпочинку має родина?

Розв’язання: оскільки всі бази відпочинку різні, то для розв’язання задачі досить знайти суму елементів усіх множин, про які йдеться: 1 + 3 + 2 + 2 = 8. Отже, родина може обирати варіант відпочинку з 8 можливих.

Задача 3. Від пункту А до пункту В ведуть три стежки, а від В до С — 2. Скількома маршрутами можна пройти від А до С?

Розв’язання: щоб пройти від А до В, треба вибрати одну з трьох стежок: 1, 2 або 3(мал. 1). Після цього треба вибрати одну з двох інших стежок: 4 або 5. Усього від А до С ведуть шість маршрутів, або 2 ∙ 3= 6. Усі ці маршрути можна позначити за допомогою пар:

(1; 4), (1; 5), (2; 4), (2; 5), (3; 4), (3; 5).

Мал. 2.1.

Узагальнимо описану ситуацію. Якщо перший компонент пари можна вибрати m способами, а другий — n способами, то таку пару можна вибрати mn способами. Це — правило добутку, але його часто називають основним правилом комбінаторики. Потрібно звернути увагу на те, що йдеться про впорядковані пари, складені з різних компонентів [46].

Правило добутку поширюється і на впорядковані трійки, четвірки та будь-які інші впорядковані скінченні множини. Зокрема, якщо перший компонент впорядкованої трійки можна вибрати m способами, другий — n способами, а третій — k способами, то таку впорядковану трійку можна обрати mnk способами. Наприклад, якщо їдальня на обід приготувала 2 перші страви — борщ (б) і суп (с), 3 другі — котлети (к), вареники (в), голубці (г) і 2 десертні тістечка (т) і морозиво 9 (м), то всього з трьох страв їдальня може запропонувати 12 різних наборів, або 2 ∙ 3 ∙ 2 = 12.

Описаній ситуації відповідає діаграма на малюнку 2. Такі діаграми називають деревами.

Мал. 2.2.

Щоб розв’язувати складніші задачі на визначення ймовірностей подій, корисно навчитись обчислювати раціональним способом кількість різних вибірок з даної множини елементів. Нехай дано множину з m елементів — a, b, …, k. Вибираючи тим чи іншим способом елементи з цієї множини, можна утворити різні вибірки, тобто підмножини даної множини або впорядковані підмножини. Залежно від того, чим відрізняється одна вибірка від інших, їх називають по-різному [33].

Вибірки, які відрізняються одна від одної або елементами, або порядком їх розміщення, називають розміщеннями.

Наприклад, з 3 елементів a, b, c можна утворити такі розміщення по 2 елементи:

ab, ac, ba, bc, ca, cb.

Вважають, що існує 6 різних розміщень з 3 елементів по 2. Число розміщень з m елементів по n позначають Тому можна записати: = 6. У разі завжди n ≤ m.

Як обчислити при різних натуральних значеннях m та n? Нехай маємо множину з m елементів. Перший елемент можна вибрати m способами: взяти будь-який з m елементів. Другий елемент, щоб за першим, доведеться вибирати з решти m – 1 елементів, тобто m – 1 способами. Тому впорядковані пари двох перших елементів можна вибрати m(m – 1) способами. Третій елемент, щоб записати його після другого, доведеться вибирати з решти m – 2 елементів. Якщо за кожною з m(m – 1) різних пар даних елементів записати m – 2 способами третій елемент, то утвориться m(m – 1)( m – 2) різних упорядкованих трійок елементів. Аналогічно можна вибрати m(m – 1)( m – 2)( m – 3) упорядкованих четвірок і т.д. Продовжуючи такі міркування, доходимо висновку, що для будь-яких натуральних чисел m та n = m(m – 1)( m – 2)( m – 3) … (m – (n – 1)).

Управій частині рівності — n множників, тому результат можна сформулювати у вигляді такого правила: кількість розміщень з m елементів по n дорівнює добутку n послідовних натуральних чисел, найбільше з яких m.

Наприклад: = 5 ∙ 4∙ 3 = 60.

Задача 4. Скількома способами збори з 20 осіб можуть обрати голову та секретаря?

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

= 20 ∙ 19 = 380.

Відповідь: 380 способами.

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

Розміщення з m елементів по m називаються перестановками. Кількість перестановок з n елементів позначають символом Наприклад, з трьох елементів a, b, c можна утворити 6 різних перестановок:

abc, acb, bac, bca, cab, cba.

Отже, = 6. А взагалі кількість перестановок з m елементів дорівнює кількості розміщень з m елементів по m, тобто завжди

= m(m – 1)( m – 2) ∙ … ∙ 3 ∙ 2 ∙ 1.

Завжди = m!. Наприклад,

= 6! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.

Задача 5. Скількома способами можна скласти список із 10 прізвищ?

Розв’язання: = 10! = 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3 628 800.

Відповідь: 628 800 способами.

Вибірки, які відрізняються одна від одної принаймі одним елементом, а не порядком їх розміщення, називають комбінаціями. Кількість комбінацій з m елементів по n позначають . Тут також n ≤ m. Наприклад, із чотирьох елементів a, b, c, d по три можна скласти 4 комбінації:

abc, abd, acd, bcd.

Якщо з кожної комбінації з m елементів по n зробити перестановок, то дістанемо розміщень. Тому ∙ = , звідки

= .

Якщо помножемо чисельник і знаменник здобутого дробу на (m – n)!, то дістанемо формулу для обчислення з m елементів по n:

= .

Наприклад, = = = 15.

Потрібно звернути увагу на те, що = 1, = m.

Задача 6. Скількома способами з 25 учнів можна вибрати на збори два делегати?

Розв’язання: тут m = 25, n = 2 і порядок немає значення, тому

= = 300.

Відповідь: 300 способами.