Основными понятиями комбинаторики являются: правило суммы, правило произведения, расстановки, перестановки, размещение, сочетание.
Расстановки ( n элементов) перестановки размещение сочетание перестановки перестановки с повторением размещение Размещение с повторением сочетание сочетание с повторением
Опр.: Область математики, в которой изучаются вопросы о том, сколько различных комбинаций можно составить из заданных объектов, называется комбинаторикой.
Задачи комбинаторики очень тесно связаны с задачами линейного программирования. Пример: сколько можно составить трехзначных номеров, не содержащих нуля? Решение: составляю девять однозначных номеров: 1,2,..,9. Если взять набор из 10 цифр, написать любую из 9 кроме 0, то из каждого однозначного получится 9 двузначных: 9*9=81 двухместный номер. Тогда 81*9=729 трехзначных номеров без повторения.
Опр.: Пусть имеется множество из n -элементов. Из него выбираем подмножества, состоящие из k -элементов. При этом подмножества могут отличаться как самими элементами, так и порядком расположения элементов относительно друг друга. Назовем выбор таких подмножеств k -размещением с повторениями. Обозначение:
Пример: для запирания сейфов в автоматических замках набирается секретное слово. Пусть имеется 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток можно совершить, не зная кода? Решение:. следовательно, неудачных попыток можно совершить 248831.
Большинство задач комбинаторики сводятся к решению с помощью правила суммы и правила произведения. Правило суммы. Часто все известные комбинации разбиваются на классы, причем каждая комбинация входит только в один класс. В этом случае общее число комбинаций равно сумме чисел комбинаций во всех классах.
Пример: если некоторый объект А: m -способами, а В: n -способами, то выбор либо А, либо В можно совершить m+n -способами. При этом важно, чтобы комбинации не совпадали. Если такие совпадения есть, то m+n-k – число выбора, где k- количество совпадений.
Часто при составлении комбинаций из этих элементов известно, сколькими способами можно выбрать первый элемент, и сколькими второй. При этом число выбора второго элемента не зависит от числа выбора первого. Правило произведения: Пусть первый элемент выбирается n способами, второй – m способами. Тогда пару можно выбрать m*n способами.
Обобщение: Если выбираются не пары элементов, а комбинации из общего числа элементов, то приходим к задаче вида: сколько можно составить k -множеств, если 1-й элемент € n1 ; 2-й € n2 ; … n -й € nk. При этом две расстановки считаются различными, если хотя бы на одном месте стоят различные элементы. В этой ситуации имеем n1*n2*...*nk вариантов.
Сложнее решаются задачи, в которых число выбора каждого последующего шага зависит от выбор на предыдущем шаге. Пример: сколькими способами из 28 костей домино можно выбрать 2 кости, чтобы их можно было приложить друг к другу? Решение. Это можно сделать 28 способами, при этом 7 случаев выбора дубля, остальные 21 – различные числа. В первом случае 6 способов выбора второй кости, во втором – 12. По правилу произведения имеем 7*6=42 варианта выбора в первом случае, а во втором – 21*12=252 варианта. 42+252 = 294 варианта всего. Если не учитывать порядок выбора костей, то имеем 294/2=147 способов выбора.
Размещение без повторения. Сколько можно составить размещений без повторений, если все входящие элементы различны? Имеется множество из n -элементов. Сколько из этих элементов можно составить подмножеств, состоящих из k -элементов? При этом подмножества различаются, если они отличаются хотя бы одним элементом. Получаем количество размещений:. На первом шаге имеем n- выборов, на втором – n-1, на пятом шаге – n-k+1 выбора. Количество элементов выбора:
Пример. Имеется 25 человек. Из них нужно выбрать старосту, культурга и профорга. Сколькими способами можно это сделать, если каждый человек занимал лишь одну должность? Решение: вариантов.
Опр.: Перестановки, в которые входят все элементы, но отличаются только порядком расположения. Такие перестановки называются n -перестановки без повторения. По определению, 0!=1. Пример. Сколькими способами можно разместить за столом 10 гостей? Решение: Р10=10!=3628800 вариантов.
Если некоторые переставляемые элементы одинаковы, то некоторые перестановки будут совпадать друг с другом, и общее количество перестановок получится гораздо меньше, чем предполагалось.
Числом сочетаний из n по m ( n>=k ) называется величина Пример:
Имеются предметы n различных типов. Сколько k -комбинаций можно из них сделать, если не принимать во внимание порядок комбинаций?
1. Пример: Доказательство: 2. Доказательство:
3. Доказывается методом математической индукции. 4.
Из формулы 4 выводятся соотношения: 1. 2. 3.
Slide-Share