Пример 1. Набор элементов xi1, , xik из множества X={x1, , xn} называется выборкойобъема k из n элементов или

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

Набор элементов x_i ₁,…, x_ik из множества X={ x ₁, …, x_n } называется выборкой объема k из n элементов или, иначе, (n, k)-выборкой.

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

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

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

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

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P ₁= 1!. Пусть для n = k теорема верна и P_k = 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.

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

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

Рассмотрим перестановки, которые не являются подмножествами.

Пусть имеется n элементов, среди которых k ₁ элементов первого типа, k ₂ элементов второго типа и т.д., k_s элементов s -го типа, причем k ₁+ k ₂ +... + k_s = n. Упорядоченные выборки из таких n элементов по n называются перестановками с повторениями, их число обозначается C_n (k ₁, k ₂,..., k_s). Числа C_n (k ₁, k ₂,..., k _s) называются полиномиальными коэффициентами.

Теорема 2. C_n ( k ₁,..., k_s )=

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

C_n (k ₁, k ₂) =

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

C_n(k ₁,..., k_m)=

Докажем, что она верна для s = m + 1 (n = k ₁ +... + k_m + k_m ₊₁). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A – выбор k _m _{+ 1}места для элементов (m + 1)-го типа; объект B – перестановка с повторениями из (n – k_m ₊₁) элементов. Объект A можно выбрать способом, B – (k ₁,..., k _m) способами. По принципу произведения

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

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

Пример 2.

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

Решение. Буква “а” входит 3 раза (k ₁= 3), буква “м” – 2 раза (k ₂ = 2), “т” – 2 раза (k ₃ = 2), буквы “е”, ”к”, ”и” входят по одному разу, отсюда k ₃= k ₄ = k ₅ = 1.