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

п.1. Выборки

Рассмотрим некоторое непустое конечное множество A мощностью |A| = n (т.е. состоящее из n элементов). Из этого множества всегда можно выбрать k элементов.

Важной характеристикой выборки является её упорядоченность.

Второй важной характеристикой выборки является повторение элементов.

Например:
Пусть задано множество A={a,b,c,d,e,f,g}. Его мощность |A|=7.
(a,c,d) – это ⟨7,3⟩– выборка без повторений
Если мы работаем с неупорядоченными выборками, то
(a,c,d) = (c,d,a) = (d,a,c) = ...
Если мы определяем наши выборки как упорядоченные, то
(a,c,d) ≠ (c,d,a) ≠ (d,a,c) ≠ ...
(a,a,a,g,c,d,e,e,g) – это ⟨7,9⟩– выборка с повторениями. Она также может быть упорядоченной или неупорядоченной, в зависимости от задачи.

п.2. Перестановка без повторений

Например:
1) Пусть задано множество A={a,b}, n=2
Его перестановки без повторений: (a,b) и (b,a) – итого два варианта (2!=2)
2) Для A={a,b,c}, n=3
Все перестановки без повторений:
(a,b,c),(b,c,a),(c,a,b),(b,a,c),(a,c,b),(c,b,a) – итого шесть вариантов (3!=6)
В лексикографическом порядке:

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

Например:
Сколько различных 6-тибуквенных слов можно написать из 3 букв {a,b,c}, если буква a должна повторяться 3 раза, буква b – 2 раза, буква c – 1 раз.
Пример такого слова: (a,b,a,a,b,c) – это ⟨3,6⟩ – выборка с повторениями.
По условию k₁=3, k₂=2, k₃=1, k=3+2+1=6 $$ \mathrm{ P_6(3,2,1)=\frac{6!}{3!\ 2!\ 1!}=\frac{720}{6\cdot 2\cdot 1}=60 } $$ Всего – 60 слов.

п.4. Примеры

Пример 1. Сколько 4-значных чисел можно составить из 4-х карточек с цифрами 0,1,3,5?
У нас только 4 карточки – значит, исследуем перестановки без повторений для ⟨4,4⟩-выборки. Таких перестановок P₄ = 4! = 24.
Кроме того, нужно учесть, что число не может начинаться с 0. Отложим карточку «0» в сторону, и посчитаем, сколько перестановок без повторений у выборки (1,3,5), т.е. у ⟨3,3⟩- выборки: P₃ = 3! = 6.
Получаем искомое число вариантов: N = P₄ – P₃ = 24 – 6 = 18
Ответ: 18.

Пример 2. У Маши четыре вазы. Сколькими способами Маша может расставить их по углам комнаты, если вазы разноцветные: белая, голубая, розовая и красная? Сколько способов останется, если все вазы - совершенно одинаковые?
1) Для разноцветных ваз рассматриваем ⟨4,4⟩-выборку вида (a,b,c,d). Количество перестановок без повторений P₄ = 4! = 24.
2) Для одинаковых ваз рассматриваем ⟨4,4⟩-выборку вида (a,a,a,a). В выборке один элемент, который повторяется 4 раза. Количество перестановок с повторениями: \(\mathrm{P_4(4)=\frac{4!}{4!}}\). Для одинаковых ваз есть только 1 вариант.
Ответ: 24; 1.

Пример 3. Сколькими способами можно разместить на полке 7 книг? Если среди книг – один трёхтомник, тома которого нужно ставить рядом (в любом порядке), сколько способов размещения останется?
1) Для 7 книг рассматриваем ⟨7,7⟩-выборку. Количество перестановок без повторений P₇ = 7! = 5040.
2) Для трёхтомника рассматриваем ⟨3,3⟩-выборку. Расставить 3 тома можно P₃ = 3! = 6 способами. Теперь рассматриваем трёхтомник как одно целое: получатся, что нужно расставить 5 книг, т.е. посчитать перестановки без повторений для ⟨5,5⟩-выборки: P₅ = 5! = 120 вариантов. Общее количество расстановок ищем по правилу произведения: N = P₃ · P₅ = 720.
Ответ: 5040; 720.

Пример 4. Сколько различных слов можно составить, переставляя буквы слова «МАТЕМАТИКА»? Сколько слов останется, если потребовать, чтобы три буквы «А» не стояли рядом?
1) По условию рассматриваем перестановки с повторениями.

$$ \mathrm{ P_{10}(2;3;2;1;1;1)=\frac{10!}{2!\ \cdot\ 3!\ \cdot\ 2!}=\frac{3628800}{2\ \cdot\ 6\ \cdot\ 2}=151200 } $$ 2) Найдем количество слов с тремя «А» подряд. Условие для перестановок с повторениями изменится так:

$$ \mathrm{ P_{8}(2;1;2;1;1;1)=\frac{8!}{2!\ \cdot\ 2!}=\frac{40320}{2\ \cdot\ 2}=10080 } $$ Исключим слова с тремя «А» подряд из общего набора.
Останется N = 151200 – 10080 = 141120 слов.
Ответ: 151200 слов; 141120 слов.