Перестановки. Размещения. Сочетания

Пусть есть некоторое конечное множество элементов U={a1, a2, ..., an}. Рассмотрим набор элементов Перестановки. Размещения. Сочетания - student2.ru , Перестановки. Размещения. Сочетания - student2.ru где ÎU, j = 1, 2, ..., r.

Этот набор называется выборкой объема r из n элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т.е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.

Принцип суммы: если card A = m, card B = n и AÇB = Æ , то card A È B = =m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

Принцип произведения: если card A=m, card B=n, то card (A´B)=m+n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m×n способами.

Пример 1. A = 10 {различных шоколадок}, B = 5 { различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в этом случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

Пример 2. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?

Пусть m – число возможностей для выпадения четного числа на одной кости, n – число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных и двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок.

Определение. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

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

Перестановки. Упорядоченные выборки, объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается Pn.

Теорема. P = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P1 = 1!. Пусть для n = k теорема верна и Pk = k!, покажем, что она тогда верна и для n = k+1. Рассмотрим (k+1)- й элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B – упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор A и B можно осуществить k!(k+1) = (k+1)! способами. Совместный выбор A и B есть упорядоченная выборка из k + 1 элементов по k + 1.

Пример 3. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10!

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n - 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n´(n - 1) способами. Затем выбираем третий элемент, для его выбора останется n - 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n - 1)(n - r) ... 1.

Размещения. Упорядоченные выборки объемом m из n элементов (m < n), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается Перестановки. Размещения. Сочетания - student2.ru .

Теорема. Перестановки. Размещения. Сочетания - student2.ru = Перестановки. Размещения. Сочетания - student2.ru

Обозначим x = Перестановки. Размещения. Сочетания - student2.ru . Тогда оставшиеся (n – m) элементов можно упорядочить (n – m)! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n – m)! способами, то совместный выбор “A и B” можно осуществить x ×(n – m)! способами, а выбор “A и B” есть перестановки и Pn = n! Отсюда x = Перестановки. Размещения. Сочетания - student2.ru = Перестановки. Размещения. Сочетания - student2.ru

Рассуждая иначе: первый элемент выбираем n способами, второй – (n – 1) способами и т.д. , m–й элемент выбираем (n – m + 1) способом. По принципу произведения вновь имеем: n(n – 1)...(n – m +1), что совпадает с Перестановки. Размещения. Сочетания - student2.ru .

Пример 4. Группа из 15 человек выиграла 3 различных книги. Сколькими способами можно распределить эти книги среди группы?

Имеем Перестановки. Размещения. Сочетания - student2.ru = 15 ×14 ×13 = 2730.

Сочетания. Неупорядоченные выборки объемом m из n элементов (m < n) называются сочетаниями. Их число обозначается Перестановки. Размещения. Сочетания - student2.ru .

Теорема. Перестановки. Размещения. Сочетания - student2.ru

Доказательство. Очевидно, Перестановки. Размещения. Сочетания - student2.ru Действительно, объект A – неупорядоченная выборка из n элементов по m, их число Перестановки. Размещения. Сочетания - student2.ru . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “порядок“ в выборке). Совместный выбор “A и B“ – упорядоченная выборка.

Пример 5. Группа из 15 человек выиграла 3 одинаковых книги. Сколькими способами можно распределить эти книги?

Перестановки. Размещения. Сочетания - student2.ru

Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.

Размещения с повторениями. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается Перестановки. Размещения. Сочетания - student2.ru (n).

Теорема. Перестановки. Размещения. Сочетания - student2.ru (n) = nm.

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m -й элемент также может быть выбран n способами. По принципу произведения получаем nm .

Пример 6. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?

Здесь n = 10, m = 4 и ответом будет 104.

Пример 7. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов?

Это есть выборка, объемом m из двух элементов.Ответ:2m

Перестановки с повторениями. Пусть имеется n элементов, среди которых k1 элементов первого типа, k2 элементов второго типа и т.д., ks элементов s-го типа, причем k1 + k2 + ... + ks = n. Упорядоченные выборки из таких n элементов по n называются перестановками с повторениями, их число обозначается Cn(k1, k2, ..., ks). Числа Cn(k1, k2, ..., ks) называются полиномиальными коэффициентами.

Теорема. Cn(k1, ..., ks)= Перестановки. Размещения. Сочетания - student2.ru

Доказательство проведем по индукции по s, т. е. по числу типов элементов. При s = 1 утверждение становится тривиальным: k1 = n, все элементы одного типа и Cn(n) = 1. В качестве базы индукции возьмем s = 2, n = k1 + k2. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k1 (или k2): выбираем k1 место, куда помещаем элементы первого типа.

Cn(k1,k2) = Перестановки. Размещения. Сочетания - student2.ru

Пусть формула верна для s = m , т.е. n = k1 + ... + km и

Cn(k1, ..., km)= Перестановки. Размещения. Сочетания - student2.ru

Докажем, что она верна для s = m + 1 (n = k1 +... + km + km+1). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A – выбор k m + 1 места для элементов (m + 1)-го типа; объект B – перестановка с повторениями из (n – km+1) элементов. Объект A можно выбрать Перестановки. Размещения. Сочетания - student2.ru способом, B – Перестановки. Размещения. Сочетания - student2.ru (k1, ..., km) способами. По принципу произведения

Перестановки. Размещения. Сочетания - student2.ru

Перестановки. Размещения. Сочетания - student2.ru

и мы получили требуемую формулу.

Замечание. Числа Перестановки. Размещения. Сочетания - student2.ru называются биноминальными коэффициентами. Из этой формулы следует, что Перестановки. Размещения. Сочетания - student2.ru

Пример 8. Сколько различных слов можно получить, переставляя буквы в слове “математика”?

Решение. Буква “а” входит 3 раза (k 1= 3), буква “м” – 2 раза (k2 = 2), “т” – 2 раза (k3 = 2), буквы “е”, ”к”, ”и” входят по одному разу, отсюда k3 = k4 = k5 = 1.

C10 (3, 2, , 2, 1, 1, 1) = Перестановки. Размещения. Сочетания - student2.ru =151200.

Сочетания с повторениями. Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число ³ m´n ) называется сочетанием с повторением. Число сочетаний с повторениями обозначается Перестановки. Размещения. Сочетания - student2.ru (n).

Теорема. Перестановки. Размещения. Сочетания - student2.ru (n) = Перестановки. Размещения. Сочетания - student2.ru .

Доказательство. Пусть в выборку вошло m1 элементов первого типа, m2 элементов второго типа, ...mn – n-го типа. Причем каждое 0 £ m i£ m и m1+m2+ ...+ mn= =m. Сопоставим этой выборке вектор следующего вида: Перестановки. Размещения. Сочетания - student2.ru Очевидно, между множеством неупорядоченных выборок с повторениями и множеством векторов {bn} существует биекция (докажите это!). Следовательно, Перестановки. Размещения. Сочетания - student2.ru (n) равно числу векторов bn. “ Длина вектора” bn равна числу 0 и 1, или m+ +n–1. Число векторов равно числу способов, которыми m единиц можно поставить на m + n - 1 мест, а это будет Перестановки. Размещения. Сочетания - student2.ru .

Пример 9. В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать ? (Предполагается, что пирожных каждого вида ³ 4).

Число способов будет Перестановки. Размещения. Сочетания - student2.ru

Пример10. Пусть V = {a, b, c}. Объем выборки m = 2. Перечислить перестановки, размещения, сочетания, размещения с повторениями, сочетания с повторениями.

1. Перестановки: {abc, bac, bca, acb, cab, cba}. P3=3!=6.

2. Размещения: {(ab), (bc), (ac), (ba), (cb), (ca)}. Перестановки. Размещения. Сочетания - student2.ru

3. Сочетания: {(ab), (ac), (bc)}. Перестановки. Размещения. Сочетания - student2.ru

4. Размещения с повторениями: {(ab), (bc), (ac), (ba), (cb), (ca), (aa), (bb), (cc)}. Перестановки. Размещения. Сочетания - student2.ru (3)= 32 = 9.

5. Сочетания с повторениями: {(ab), (bc), (ca), (aa), (bb), (cc)}. Перестановки. Размещения. Сочетания - student2.ru

Наши рекомендации