Материал: Вища математика для економістів - Навчальний посібник ( Барковський В.В.)


2.5. елементи комбінаторики

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

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

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

Більшість комбінаторних задач розв'язуються з використанням двох основних правил правила суми та правила добутку.

Правило суми: якщо деякий об'єкт А можна обрати т спосо­бами, а об'єкт В п способами (незалежно від вибору А), тоді вибір або А або В можна зробити т + п способами.

Наприклад, якщо з двох цехів, в яких працюють 40 та 45 праців­ників, треба обрати одного на профспілкову конференцію, тоді це можна зробити 85 способами (обрати з одного цеху 40 способів, з другого 45 способів).

Правило добутку: якщо об'єкт А можна обрати m способами і після такого вибору об'єкт В обрати n способами, тоді обрання пари (А, В) у заданому порядку можна зробити mn способами.

Наприклад, якщо з двох класів, в яких навчаються 29 та 31 учнів, треба направити на міську математичну олімпіаду будь-яких два учня, по одному з кожного класу, тоді можливих комбінацій буде 29 • 31 = 899.

Деякі комбінації зустрічаються частіше за інші і мають свої назви: розміщення, перестановки та сполучення.

В комбінаториці доведені формули, які дозволяють знаходити кількість цих основних комбінацій. Ці формули разом з правилами комбінаторики дозволяють знаходити кількість будь-яких комбінацій.

Ознайомимось з основними комбінаціями комбінаторики.

Означення. Комбінації, які взяті з n різних елементів в кількості k (k < n) елементів і які відрізняються між собою хоча б одним еле­ментом або розташовані у різному порядку називають розміщення­ми без повторень, їх кількість позначають Л^п або An(k) і знахо­дять за формулою

лк n!

 

де n! = 1 • 2 • 3    • n.

Наприклад, якщо у навчальному плані 10 дисциплін і на кожен день можна планувати 4 різних дисципліни, то розклад занять на кожний день можна скласти

 

A40 = — =      = 7 • 8 • 9 • 10 = 5040 способами.

Означення. Різноманітні комбінації з n елементів в кількості k елементів (k < n), що відрізняються між собою хоча б одним елемен­том без врахування їх порядку, називають сполученням з n еле­ментів k, їх кількість позначають Ck або Cn (k) і знаходять за формулою

 

Подпись: П!СІ =(п к)Ш'

(2)

 

 

■ Приклад 15. На підприємстві працюють 15 співробітників, троє з них не мають відповідної кваліфікації. Скільки можна скласти списків:

по 8 співробітників;

по 6 кваліфікованих співробітників;

по 9 співробітників, два з яких не мають відповідної кваліфі­кації?

^> Розв'язання:

при складанні списку 8 працівників з 15 нас нецікавить їх по­рядок, тому кількість таких списків буде

с = ІЯ = 9 •10-И-12 •13-и-15 = з іііз     = 6435. 15   7!- 8!       1-2 • 3 • 4 • 5 • 6 • 7

при складанні списків 6 кваліфікованих співробітників їх треба обирати з 12 кваліфікованих (15 3) співробітників, порядок співробітників у кожному списку не враховується, тому кількість таких списків буде

 

Подпись: ,6    12!    7 • 8 • 9-10 • 11-12
у12
= ^_ = ■ ~ — = 924. 6!- 6!     1-2 • 3 • 4 • 5 • 6

 

с) для складання списків з 9 працівників, 2 з яких не мають відпо­відної кваліфікації, треба обирати 7 співробітників з 12 кваліфікова­них та 2 співробітника з 3 не кваліфікованих. Кількість потрібних списків згідно із правилом добутку буде

„7^2    12!    3!    8 • 910 4Ы2 12 • 3 С12 С3 = _     =—:—:—:—:—~        :—:— = 2376.

5Ь 7! 1! 2!     1 2 • 3 • 4 • 5    !• 2

 

Ф Означення. Комбінації з п елементів, в які входять усі п еле­ментів і відрізняються лише порядком елементів називають переста­новками із п елементів, їх кількість позначають Р і знаходять за формулою

Рп = п! (3)

Відмітимо, що між кількостями основних комбінацій комбінатори­ки існує зв'язок вигляду

 

с: = —, (4)

рк

Ст = Сп~т. (5)

 

Запитання для самоперевірки

Що вивчає комбінаторика та які її основні правила?

Які комбінації називають розміщеннями, сполученнями, пере­становками? За якими формулами знаходять кількості цих комбі­націй?

 

Вправи до розділу 2.5

Скільки п'ятизначних чисел можна скласти з використанням п'яти різних цифр?

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

Скільки існує способів для розміщення 12 гостей за столом, де стоять 12 стільців?

З 7 кандидатів обирають президента та віце-президента. Скільки може бути різних комбінацій обрання?

Скількома способами з 10 осіб можна обрати комісію у складі 4 осіб.