Page 182 - 4496

5 КОМБІНАТОРИКА

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

5.1 Розміщення з повтореннями

Розглянемо задачу: скільки різних 5-розрядних чисел
можна скласти з 10 цифр?
Перенумеруємо розряди:

1 2 3 4 5

У перший розряд можна поставити одну з 10 цифр.
Незалежно від того, яка цифра поставлена, в другий розряд
можна також поставити одну з 10 цифр і т.д. Всього виходить
105 різних чисел.
Для двійкової системи числення (використовуються
тільки дві цифри: 0 або 1) одержуємо 25 різних чисел. Для
системи з основою k і числом розрядів n відповідно
одержуємо:
А = kn (5.1)

n - число позицій (розрядів); k - число елементів в кожній
позиції (цифр).
У загальному вигляді задача ставиться таким чином: є k
типів предметів (кількість предметів кожного типу
необмежена) і n позицій (ящиків, купок, розрядів).
179