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