Доклад
Элементы комбинаторики
Комбинаторика (Комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году, опубликовал свой труд «Рассуждения о комбинаторном искусстве».
Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.
Примеры комбинаторных конфигураций и задач.
Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются:
· Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n -элементного множества.
· Перестановкой из n элементов (например чисел 1,2,…, n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.
· Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
· Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
· Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.
|
|
Примерами комбинаторных задач являются:
1. Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения?
2. Сколько существует функций 
из m -элементного множества в n -элементное, удовлетворяющих заданным ограничениям?
3. Сколько существует различных перестановок из 52 игральных карт?
Ответ: 52! (52 факториал), то есть, 80658175170943878571660636856403766975289505440883277824000000000000 или примерно 8,0658 × 1067.
4. При игре в кости бросаются две кости, и выпавшие очки складываются; сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати?
Решение: Каждый возможный исход соответствует функции 
(аргумент функции — это номер кости, значение — очки на верхней грани). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.
Разделы комбинаторики
Перечислительная комбинаторика
Перечислительная комбинаторика (или исчисляющая комбинаторика) рассматривает задачи о перечислении или подсчёте количества различных конфигураций (например,перестановок) образуемых элементами конечных множеств, на которые могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
Количество конфигураций, образованных несколькими манипуляциями над множеством, подсчитывается согласно правилам сложенияи умножения.
Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.