Комбинаторика

расстановки,
перестановки,
размещение,
сочетание.

различных комбинаций можно составить из заданных объектов, называется комбинаторикой.

можно составить трехзначных номеров, не содержащих нуля?
Решение: составляю девять однозначных

номеров: 1,2,..,9. Если взять набор из 10 цифр, написать любую из 9 кроме 0, то из каждого однозначного получится 9 двузначных: 9*9=81 двухместный номер. Тогда 81*9=729 трехзначных номеров без повторения.

выбираем подмножества, состоящие из k-элементов. При этом подмножества могут отличаться

как самими элементами, так и порядком расположения элементов относительно друг друга. Назовем выбор таких подмножеств k-размещением с повторениями. Обозначение:

Пусть имеется 12 букв, а секретное слово состоит из 5

букв. Сколько неудачных попыток можно совершить, не зная кода?
Решение: . следовательно, неудачных попыток можно совершить 248831.

правила суммы и правила произведения.
Правило суммы. Часто все известные комбинации

разбиваются на классы, причем каждая комбинация входит только в один класс. В этом случае общее число комбинаций равно сумме чисел комбинаций во всех классах.

А, либо В можно совершить 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 выбора. Количество элементов выбора:

и профорга. Сколькими способами можно это сделать, если каждый человек

занимал лишь одну должность?
Решение: вариантов.

отличаются только порядком расположения. Такие перестановки называются n-перестановки без повторения.

По определению, 0!=1.
Пример. Сколькими способами можно разместить за столом 10 гостей?
Решение: Р10=10!=3628800 вариантов.

будут совпадать друг с другом, и общее количество перестановок получится

гораздо меньше, чем предполагалось.

из них сделать, если не принимать во внимание порядок комбинаций?