Размещения

п.1. Размещения без повторений

Размещениe без повторений – это упорядоченная ⟨n,k⟩ – выборка без повторений,     kn. Общее количество размещений без повторений: $$ \mathrm{ A_n^k=\frac{n!}{(n-k)!} } $$

Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей без повторения символов можно составить?
По условию n = 5, k = 3. Рассматриваем размещение 5 символов по 3 позициям без повторений: \(\mathrm{ A_5^3=\frac{5!}{(5-3)!}=5\cdot 4\cdot 3 = 60 }\)
Всего 60 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции – 5 вариантов символов, на второй – 4 оставшихся, на третьей – 3 оставшихся. Итого, по правилу произведения: 5 · 4 · 3 = 60 паролей.

п.2. Размещения с повторениями

Размещение с повторением – это упорядоченная ⟨n,k⟩ – выборка с повторениями. Общее количество размещений с повторениями: $$ \mathrm{ \overline{A}_n^k=n^k } $$

Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей можно составить?
По условию n=5, k=3. Рассматриваем размещение 5 символов по 3 позициям с повторениями: \(\mathrm{ \overline{A}_5^3=5^3=125. }\)
Всего 125 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции 5 вариантов символов, на второй – 5 вариантов, и на третьей – 5 вариантов. Итого, по правилу произведения: 5 · 5 · 5 = 53 = 125 паролей.

п.3. Примеры

Пример 1. Исследуйте различие между перестановкой без повторений и размещением без повторений ⟨3,2⟩-выборок для трёх разноцветных фишек. Изобразите полученные решения.

Рассматриваем фишки: Пример 1

1) Для перестановок, ⟨3,3⟩-выборок, получаем:

Пример 1 В каждом ряду – отдельная перестановка.
Видно, как образуется факториал. Для каждой отдельной фишки – одна перестановка. Для каждой пары фишек – две перестановки: 2 · 1. Когда добавляем третью, получаем: 3 · 2 · 1
Итого: P3 = 3 · 2 · 1 = 6 перестановок.

2) Для размещений без повторений, ⟨3,2⟩-выборок, получаем:

Пример 1 В каждом ряду – отдельное размещение.
В первом столбце слева – 3 варианта по цвету.
Во втором столбце остается только 2 варианта.
Итого: \(\mathrm{A_3^2=3\cdot 2=6}\) размещений.

Пример 2. Исследуйте перестановки без повторений и размещения для ⟨4,3⟩ выборок и для ⟨4,2⟩ выборок без повторений из 4 разноцветных фишек.
Изобразите полученные решения.

Рассматриваем фишки: Пример 2

Пример 2
В каждом ряду – отдельная перестановка.
Итого: P4=4·3·2·1=24 перестановки.
Пример 2
В каждом ряду – отдельное размещение.
Итого: \(\mathrm{A_4^3=4\cdot 3\cdot 2=24}\) размещения.
Пример 2
В каждом ряду – отдельное размещение.
Итого: \(\mathrm{A_4^2=4\cdot 2=12}\) размещений.

Пример 3. Исследуйте различие между перестановкой с повторениями и размещением с повторениями. Сделайте вывод.
Перестановка с повторениями: сколько слов можно получить, переставляя буквы в слове «МАМА»? Запишите все эти слова в лексикографическом порядке.
Размещение с повторениями: сколько 4-буквенных слов можно получить, используя две буквы: «М» и «А»? Запишите все эти слова в лексикографическом порядке.


1) Для перестановки с повторениями получаем: \begin{gather*} \mathrm{ a_1=M,k_1=2,\ \ \ a_2=A,k_2=2 }\\ \mathrm{ k=k_1+k_2=2+2=4 }\\ \mathrm{ P_4(2;2)=\frac{4!}{2!\cdot 2!}=\frac{24}{2\cdot 2}=6 } \end{gather*} Все 6 слов в лексикографическом порядке:

AAMM≺AMAM≺AMMA≺MAAM≺MAMA≺MMAA

2) Для размещения с повторениями получаем: \begin{gather*} \mathrm{ n=2,\ \ \ k=4 }\\ \mathrm{ \overline{A}_2^4=2^4=16 } \end{gather*} Все 16 слов в лексикографическом порядке:

AAAA≺AAAM≺AAMA≺AAMM≺AMAA≺AMAM≺AMMA≺AMMM≺
≺MAAA≺MAAM≺MAMA≺MAMM≺MMAA≺MMAM≺MMMA≺MMMM

Вывод: вариантов для размещения с повторениями получается больше, т.к. они включают слова с одной, тремя и четырьмя «М» и «А». А в перестановки с повторениями входят только слова с двумя «М» и двумя «А».

Пример 4. В базе данных с номерами телефонов содержатся все 7-значные номера.
1) Сколько в книге номеров, в которых цифры не повторяются?
2) Сколько в книге всего номеров?
3) Сколько в книге номеров, у которых 4 последних цифры одинаковые?
4) Сколько в книге номеров, у которых 4 последних цифры одинаковые, а 3 первых цифры отличаются от 4 последних?
1) Цифр – всего 10: {0;1;2;…;9}

n=10,   k=7

Количество семизначных номеров без повторений равно количеству размещений без повторений: $$ \mathrm{ A_{10}^7=10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4=604800 } $$ 2) Количество всех семизначных номеров равно количеству размещений с повторениями: $$ \mathrm{ \overline{A}_{10}^7=10^7=10\ 000\ 000 } $$ 3) 4 последних одинаковых цифры рассматриваем как одну «склеенную» цифру;
а 7-значный номер – как 4-значный, с последней «склеенной цифрой».
Количество всех4-значных номеров равно количеству размещений с повторениями: $$ \mathrm{ \overline{A}_{10}^4=10^4=10\ 000 } $$ 4) Если 10 вариантов 4 последних цифр: {0;1;2;…;9}, тогда для каждой из 3 первых цифр остается 9 вариантов. Если 10 вариантов для 3 первых цифр, тогда для 4 последних остается 9 вариантов.
По правилу суммы и произведения общее количество таких номеров: $$ \mathrm{ N=\frac{9^3\cdot 10+10^3\cdot 9}{2}=8145 } $$ Ответ: 1) 604 800 2) 10 000 000; 3) 10 000; 4) 8145.

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