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

п.1. Выборки

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

Выборка (кортеж) – набор из k элементов из некоторого множества n элементов. Назовём её ⟨n,k⟩  – выборка.

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

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

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

Если элементы в выборке не повторяются, она называется выборкой без повторений.
В отличие от множества, элементы в выборке могут повторяться; в этом случае она называется выборкой с повторениями. При этом может оказаться, что k > n – количество элекментов выборки больше мощности исходного множества.

Например:
Пусть задано множество 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. Перестановка без повторений

Перестановка без повторений – это упорядоченная ⟨n,n⟩– выборка без повторений.
Общее количество перестановок без повторений:
$P_n=n!$
Лексикографический порядок – способ упорядочения перестановок, основанный на сравнении. Меньшей считается та перестановка, у которой на первом месте стоит меньший элемент. Если оба первых элементов равны, сравниваются вторые элементы; и т.д. Отношение лексикографического «меньше» обозначается ≺
Читается «меньше» или «предшествует».

Например:
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)
В лексикографическом порядке:

(a,b,c)≺(a,c,b)≺(b,a,c)≺(b,c,a)≺(c,a,b)≺(c,b,a)

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

Перестановка с повторениями – это упорядоченная⟨n,k⟩ – выборка с повторениями, в которой элемент a1 повторяется k1 раз, элемент a2 повторяется k2 раз, и так далее, до последнего элемента as, который повторяется ks раз (s ≤ n). При этом
k = k1 + k2 + ... + ks.
Общее количество перестановок с повторениями: $$ \mathrm{ P_k(k_1,k_2,...,k_s)=\frac{k!}{k_1!k_2!...k_s!} } $$

Например:
Сколько различных 6-тибуквенных слов можно написать из 3 букв {a,b,c}, если буква a должна повторяться 3 раза, буква b – 2 раза, буква c – 1 раз.
Пример такого слова: (a,b,a,a,b,c) – это ⟨3,6⟩ – выборка с повторениями.
По условию k1=3, k2=2, k3=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⟩-выборки. Таких перестановок P4 = 4! = 24.
Кроме того, нужно учесть, что число не может начинаться с 0. Отложим карточку «0» в сторону, и посчитаем, сколько перестановок без повторений у выборки (1,3,5), т.е. у ⟨3,3⟩- выборки: P3 = 3! = 6.
Получаем искомое число вариантов: N = P4 – P3 = 24 – 6 = 18
Ответ: 18.

Пример 2. У Маши четыре вазы. Сколькими способами Маша может расставить их по углам комнаты, если вазы разноцветные: белая, голубая, розовая и красная? Сколько способов останется, если все вазы - совершенно одинаковые?
1) Для разноцветных ваз рассматриваем ⟨4,4⟩-выборку вида (a,b,c,d). Количество перестановок без повторений P4 = 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⟩-выборку. Количество перестановок без повторений P7 = 7! = 5040.
2) Для трёхтомника рассматриваем ⟨3,3⟩-выборку. Расставить 3 тома можно P3 = 3! = 6 способами. Теперь рассматриваем трёхтомник как одно целое: получатся, что нужно расставить 5 книг, т.е. посчитать перестановки без повторений для ⟨5,5⟩-выборки: P5 = 5! = 120 вариантов. Общее количество расстановок ищем по правилу произведения: N = P3 · P5 = 720.
Ответ: 5040; 720.

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

a1=M, k1=2,    a2=A, k2=3,    a3=T, k3=2,   
a4=E, k4=1,    a5=И, k5=1,    a6=K, k6=1,   
k = k1 + k2 + ... + k6 = 2+3+2+1+1+1 = 10

$$ \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) Найдем количество слов с тремя «А» подряд. Условие для перестановок с повторениями изменится так:

a1=M, k1=2,    a2="AAA", k2=1,    a3=T, k3=2,   
a4=E, k4=1,    a5=И, k5=1,    a6=K, k6=1,   
k = k1 + k2 + ... + k6 = 2+1+2+1+1+1 = 8

$$ \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 слов.

Рейтинг пользователей

за неделю
  • за неделю
  • один месяц
  • три месяца
    Регистрация
    Войти с помощью
    Необходимо принять пользовательское соглашение
    Войти
    Войти с помощью
    Восстановление пароля
    Пожаловаться
    Задать вопрос