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

Набор элементов x , …, x из множества Х = { x , …, x } называется выборкой объема m из n элементов.

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

Например, упорядоченные выборки ( x1, x5 ) и ( x5, x1 ) различные выборки объемом 2.

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

В выборках могут допускаться или не допускаться повторения элементов.

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

Число всех размещений без повторений объемом m , составленных из n различных элементов, обозначается через А и вычисляется по формуле

А = n·(n-1)· … ·(n - m + 1) = , при m ≤ n . (4.1)

Пример. Записать все размещения без повторений объемом 2, которые можно составить из элементов множества { 1, 2, 3 }.

Число таких размещений определяем по формуле (4.1) А = 3·2 = 6.

Это будут следующие размещения ( 1,2 ), ( 1,3 ), ( 2,1 ), ( 2,3 ), ( 3,1 ), ( 3,2 ).

Определение. Размещением с повторениями из m элементов называется упорядоченная выборка объемом m в которой элементы могут повторяться.

Число всех размещений с повторениями объемом m, составленных из n различных элементов, обозначается через и вычисляется по формуле

= n . (4.2)

Пример. Записать все размещения с повторениями объемом 2, которые можно составить из элементов множества { 1, 2, 3 ).

Число таких размещений определяем по формуле (4.2) Ã = 3 = 9.

Это будут следующие размещения

( 1,1 ), ( 1,2 ), ( 1,3 ), ( 2,1 ), ( 2,2 ), ( 2,3 ), ( 3,1 ), (3,2), ( 3,3 ).

Определение. Перестановкой из n элементов называется размещение без повторений объемом n.

Число всех перестановок из n элементов обозначается через Р и вычисляется по формуле

Р = n! = n·( n-1 )· … ·2·1. (4.3)

Пример. Записать все перестановки из элементов множества { 1,2,3 }.

Число перестановок определяем по формуле (4.3) Р = 2·3 = 6.

Это будут следующие перестановки

( 1,2,3 ), ( 1,3,2 ), ( 2,1,3 ), ( 2,3,1 ), ( 3,1,2 ), (3,2,1).

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

Задача сводится к тому, что из восьми разных элементов (8 этажей на которые могут выходить пассажиры) надо отобрать три разных элемента ( этажа ), т.к. на одном этаже может выйти только один пассажир.

Следовательно, это будут выборки без повторений. Причем выборки ( 2,3,5 ) и ( 3,2,5 ) считаются разными, т.к. первая выборка соответствует тому, что пассажир А вышел на втором этаже, а для второй выборки А вышел на третьем этаже.

Поэтому это будут выборки объемом три упорядоченные и без повторений, т.е. это будут размещения объемом три без повторений, составленные из восьми разных элементов. Число их вычисляется по формуле (4.1) и будет равно

А = 8·7·6 = 336.

Задача. Сколькими способами можно составить список из 25 студентов.

Число всех способов, очевидно, определяется числом всех перестановок из 25 разных элементов и вычисляется по формуле (4.3) Р = 25!

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

Число всех различных сочетаний без повторений объемом m, которые могут быть составлены из n различных элементов обозначается через С и вычисляется по формуле

С = = (4.4)

Пример. Записать все сочетания без повторений объемом два, которые можно составить из элементов множества { 1, 2, 3 }.

Согласно формуле (4.4) число всех сочетаний будет равно С = = 3.

Это будут следующие сочетания ( 1,2 ), ( 1,3 ), ( 2,3 ).

Задача. Сколькими способами можно выбрать 5 номеров из 36?

Число таких способов будет равно числу неупорядоченных выборок без повторений объемом 5, которые можно составить из 36 элементов, т.е. это будут сочетания по 5 элементов. Число их вычисляется по формуле (4.4) и будет равно

С = = 376992.

Число С обладает следующими свойствами:

1. C = C ;

2. C + C = C ;

3. ( a + b ) = , где C = C = 1.

4. 2 = . Это равенство следует из свойства 3) при a = b = 1.

Равенство 3) называется биномом Ньютона, поэтому С называются биномиальные коэффициенты.

Свойство 2) означает, что коэффициенты С в биноме степени n +1 получаются суммированием двух соседних коэффициентов в биноме n-ой степени.

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

( a + b ) = C b + C a b + C a = a

= .

Равенство 2) называется соотношением Паскаля. На этом свойстве основан треугольник Паскаля, изображенный на рис.4.1 и 4.2.

С

С С 1

\ + ∕ 1 1

С С С \ + ∕

\ + ∕ \ + ∕ \ 1 2 1

С С С С \ + ∕ \ + ∕

\ + ∕ \ + ∕ \ + ∕ 1 3 3 1

С С С С С \ + ∕ \ + ∕ \ + ∕

··················································· 1 4 6 4 1

Рис.4.1 Рис.4.2

С помощью бинома Ньютона можно получать различные формулы.

Пример 1. Подставим в бином Ньютона значения a = 1, b = -1. Тогда получим

= 0.

Следовательно, суммы биномиальных коэффициентов, стоящих на четных и нечетных местах, равны между собой, и каждая равна 2 .

Подставим теперь в бином Ньютона значения a = 1, b = i. Тогда получим

.

По формуле Муавра имеем , где .

В данном случае .

Тогда получим .

Левая часть в этом выражении состоит из вещественной части и мнимой. Вещественная часть это знакопеременная сумма слагаемых с четными индексами Мнимая часть это аналогичная сумма для нечетных индексов . Тогда получим следующие формулы

.

Пример 2. Обозначим через S (n) = 1 + 2 . Тогда для , используя бином Ньютона, можно получить следующую формулу

.

Определение. Сочетаниями с повторениями называются неупорядоченные выборки объема m, в которых элементы могут повторяться.

Число всех сочетаний с повторениями объемом m , которые можно составить из n различных элементов обозначается и вычисляется по формуле

= . (4.5)

Пример. Записать все сочетания с повторениями объема 2, которые можно составить из элементов множества { 1, 2, 3 }.

Согласно формуле (4.5) число таких сочетаний равно = = = 6.

Это будут следующие сочетания ( 1,1 ), ( 1,2 ), ( 1,3 ), ( 2,2 ), ( 2,3 ), ( 3,3 ).

Задача. Найти число различных случаев выпадения цифр при бросании двух одинаковых игральных костей.

Число таких случаев будет равно числу всех сочетаний с повторениями объемом 2, которые можно составить из шести разных элементов ( 6 граней кубика ), т.е.

= = = 21.

Определение. Задачами на сочетания с повторениями длины n из m видов называются задачи, сводящиеся к нахождению числа целочисленных решений уравнений вида

x + x + … + x = n, x z. (4.6)

Утверждение. Число целочисленных решений уравнения (4.6) равно

С . (4.7)

Задача. В буфете продаются пирожные пяти видов. Сколькими способами можно купить 12 пирожных?

Ясно, что любой способ покупки пирожных должен удовлетворять уравнению (4.6) при n = 12, где x - число пирожных i – го вида. Следовательно, число всех способов покупки пирожных равно числу всех целочисленных решений данного уравнения, и будет вычисляться по формуле (4.7). Оно будет равно

С = С = = 1820.

Определение. Разбиением множества М мощности n на k подмножеств { }, называется разбиение для которого выполняются условия , т.е. , при i ≠ j, причем - упорядоченный набор подмножеств.

Число таких разбиений обозначается через

и вычисляется по формуле

(4.8)

Задача. В студенческой группе, состоящей из 25 человек, при выборке старосты за предложенную кандидатуру проголосовали 12, против – 10, воздержались – 3. Сколькими способами могло быть проведено такое голосование?

В данной задаче множество М мощности 25 разбивается на три не пересекающихся упорядоченных подмножества мощности 12, 10 и 3. Сумма мощностей этих подмно-жеств равна мощности М. Следовательно, искомое число способов голосования будет равно R( 12, 10, 3 ) . Тогда по формуле (4.8) получим

R( 12, 10, 3 ) = = 1487285800.

Замечание. Если при разбиении множества М на k непересекающихся подмно-жеств, которые являются неупорядоченными наборами, то число всевозможных таких разбиений обозначается через

.

Задача. Сколькими способами из группы в 25 человек можно сформировать 5

каолиций по 5 человек.

Пусть m - число каолиций по i человек, где i = 1, …, 25. Тогда по условию задачи n = = 25, m = 5, m = 0, i { 1,2,…,25 }\ {5}, и, следовательно, искомое число способов будет равно

.