Комбинаторика. Размещения

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

• Комбинаторика – раздел дискретной математики,
позволяющий найти, сколькими способами можно
выбрать нужные наборы, состоящие из элементов
заданного множества.
• Сколько различных двухзначных чисел можно
составить из множества {1,2,3}?
1 2, 1 3, 2 1, 2 3, 3 1, 3 2
• ИЛИ
• Сколькими способами можно выбрать 2 числа для
получения различных двухзначных чисел из
множества {1,2,3}?

2. Размещения

• Если мы имеем множество, состоящее из n
элементов, сколькими способами можно выбрать из
этого множества k элементов (отличающихся
самими элементами либо их расположением)?
• Количество способов, которыми мы сможем выбрать
данные размещения (кортежи), обозначается как
Аnk
• Множество {1,2,3}. Сколькими способами можно
выбрать два разных числа, чтобы получить
различные двухзначные числа? Первое число можно
выбрать 3 способами. Второе число 2 способами.

3. Размещения.

• Тогда в нашем примере Аnk =3х2=6
• Первым числом может быть 1, 2 или 3. Таким
образом, первое число можно выбрать 3-мя
способами.
• Второе число можно выбрать 2-мя способами. Если
выбрали первым числом 1, то второе число может
быть 2 или 3.
Выбрать или разместить k-элементов из n–элементов
можно Аnk способами.
Аnk = n! / (n – k )!

4. Перестановки.

• Пусть у нас есть n элементов, и будем строить
различные наборы из этих n элементов. Наборы
будут различаться только порядком элементов ( во
все наборы входят одни и те же элементы). Такие
наборы будем называть перестановками. Количество
различных перестановок (наборов) будем обозначать
Pn. .
Pn = n!
Пример. Имеем множество {1,2,3}. Сколько различных
перестановок (различных трехзначных чисел) можно
составить из данного множества?
123, 132, 213, 231, 312, 321

5. Сочетания.

• Сочетаниями называются наборы из k элементов,
выбранные из n исходных элементов. Каждый набор
из k элементов отличается один от другого составом
входящим в него элементов. Выбрать различных k
элементов из n исходных элементов можно Сnk
способами.
Сnk = Аnk / Pk = n! / ((n – k )!k!)
• Пример. Какие сочетания двух элементов можно
составить из {1, 2, 3}.
12, 13, 23.
• Сnk = 3! / ((3-2)!2!) = 3х2 / 2 = 3

6. Комбинации с повторениями

• В приведенных выше размещениях, перестановках,
сочетаниях каждый элемент может входить только
один раз в рассматриваемую комбинацию (набор).
Если же некоторые элементы могут повторяться, то
рассматриваются комбинации с повторяющими
элементами, и правила подсчета будут отличаться от
приведенных.
• Например, сколько номеров машин можно составить
из четырех цифр? Множество из которого
выбираются цифры {0,1,2,3,4,5,6,7,8,9}.

7. Размещения с повторениями

• Размещение с повторение будем обозначать, как
Аnk = nk
В приведенном примере количество номеров будет
равно
А104 = 104 Предполагаем, что
существует номер 0000, а если нет то 10000 -1.

8. Перестановка с повторениями.

• Если имеется некоторое число состоящее из цифр
1,2,3 , в котором цифра 1 повторяется n1 раз, а
цифра 2 повторяется n2 раз, цифра 3 повторяется n3
раз, то получаем число длиной n1 + n2 + n3. То
количество различных чисел длиной n1 + n2 + n3, с
таким составом чисел будет равно
P(n1 , n2 , n3) = (n1 + n2 + n3)! / (n1! n2! n3!)
Пример 1122, 1212, 1221, 2112, 2121, 2211
4!/ (2! х2!) = 4х3х2 /(2 х 2) =6

9. Сочетания с повторениями

• Имеются n видов предметов, сколько различных
наборов состоящих из к предметов можно
составить?
• В магазине имеются красные, черные, зеленые
карандаши (3 вида). Сколько различных наборов из
трех карандашей можно составить (набор из 3
предметов)?
ккк, ччч, ссс, ккс, ккч,ксс, кчч, ксч, ччс, ссч
Сk n= Ckn +k-1
Ckn +k-1= C33 +3-1 = 5х4 / 2 =10

10. Сочетания с повторениями

• В магазине имеются красные, черные, зеленые
карандаши (3 вида). Сколько различных наборов из
двух карандашей можно составить (набор из 2
предметов)?
кк, чч, сс, кс, кч, сч
Сk n= Ckn +k-1
Ckn +k-1= C23 +2-1 = 4х3 / 2 =6