ОСНОВНІ ПРАВИЛА КОМБІНАТОРИКИ
Комбінаторика – розділ математики, присвячений розв’язуванню задач вибору та розташування елементів деякої скінченної множини відповідно до заданих правил.
Розглянемо два основних правила, за допомогою яких розв’язується багато задач із комбінаторики.
Приклад 1. У місті N є два університети – політехнічний і економічний. Абітурієнту подобаються три факультети в політехнічному університеті і два – в економічному. Скільки можливостей має абітурієнт для вступу в університет?
Розв’язання. Позначимо буквою А множину факультетів, які обрав абітурієнт в полі технічному університеті, а буквою В – в економічному. Тоді А = {т, n, k}, В = {p, s}. Оскільки ці множини не мають спільних елементів, то загалом абітурієнт має 3 + 2 = 5 можливостей вступати до університету.
Описану ситуацію можна узагальнити у вигляді твердження, яке називається правилом суми.
Якщо елемент деякої множини А можна вибрати m способами, а елемент множини В – n способами, то елемент із множини А або ж із множини В можна вибрати m + n способами.
Правило суми поширюється і на більшу кількість множин.
Приклад 2. Від пункту А до пункту В ведуть три стежки, а від В до С – дві. Скількома маршрутами можна пройти від пункту А до пункту С?
Розв’язання. Щоб пройти від пункту А до пункту В, треба вибрати одну з трьох стежок: 1, 2 або 3. Після того слід вибрати одну з двох інших стежок: 4 чи 5.
Усього від пункту А до пункту С ведуть 6 маршрутів, бо 3 ∙ 2 = 6.
Усі ці маршрути можна позначити за допомогою пар: (1; 4), (1; 5), (2; 4), (2; 5), (3; 4), (3; 5).
Узагальнимо описану ситуацію.
Якщо перший компонент пари можна вибрати т способами, а другий – п способами, то таку пару можна вибрати тп способами.
Це – правило добутку, його часто називають основним правилом комбінаторики. Зверніть увагу: ідеться про впорядковані пари, складені з різних компонентів.
Приклад 3. Скільки різних поїздів можна скласти з 6 вагонів, якщо кожний з вагонів можна поставити на будь-якому місці?
Розв’язання. Першим можна поставити будь-який із 6 вагонів. Маємо 6 виборів. Другий вагон можна вибрати з решти 5 вагонів. Тому за правилом множення два перших вагони можна вибрати 6 · 5 способами. Третій вагон можна вибрати з 4 вагонів, що залишились. Тому три перших вагони можна вибрати 6 · 5 · 4 способами. Продовжуючи подібні міркування, приходимо до відповіді: усього можна скласти 6 · 5 · 4 · 3 · 2 · 1 = 720 різних поїздів.
Добуток усіх натуральних чисел від 1 до n називають n-факторіалом і позначають n!
Домовились вважати, що 1! = 1 і 0! = 1.
Перейдемо да задач з вашого підручника:
ДОМАШНЄ ЗАВДАННЯ : опрацювати п.21, виконати в зошиті №21.4, 21.7
Коментарі
Дописати коментар