Размещения с повторениями объема k из n-множества X, или размещения с повторениями из n элементов по k, – это упорядоченные выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k,
– произвольные элементы множества X.
Каждый элемент ai может быть выбран n способами. По правилу произведения общее число размещений с повторениями из n элементов по k равно nk.
Размещения (без повторений) объема k из n-множества X, или размещения из n элементов по k, – это упорядоченные выборки вида (a1, a2,…, ak), где ai, i = 1, 2,…, k, – различные элементы множества X.
Элемент a1 может быть выбран n способами. При n ≥ 2 элемент a2 может быть выбран n – 1 способами: в качестве a2 можно взять любой элемент из (n – 1)-множества X\{a1}. По правилу произведения число упорядоченных пар различных элементов вида (a1, a2) равно n(n – 1). Аналогично (при n ≥ 3) элемент a3 может быть произвольно выбран из (n – 2)- множества X\{a1, a2}, так что число упорядоченных троек
(a1, a2, a3) равноn(n – 1)(n – 2).
n
Число размещений из n по k, n ≥ k, обозначается через
Ak .
n
Как мы видели,
A1 n . Естественно считать, что
n
A0 1
(3)
(имеется ровно одна, не содержащая ни одного элемента, т. е.
пустая выборка).
Несложно показать, что при k < n имеет место соотношение
A
n
k 1
n
(n − k ) Ak . (4)
В самом деле, упорядоченную выборку вида (a1, a2,…, ak, ak+1) можно рассматривать как упорядоченную пару, в которой первым элементом служит размещение
(a1, a2,…, ak), а вторым – ak+1. Размещение из n элементов по k
A
n
может быть составлено
k способами, элемент ak+1 может быть
произвольно выбран из (n – k)-множества X\{ a1, a2,…, ak}.
Формула (3) получается теперь по правилу произведения.
Используя формулы (3) и (4), получаем:
n
A
n
A1 n ,
2 n(n − 1) ,
3 n(n − 1)(n − 2) , … ,
и, в общем случае:
A
A
n
n
k n(n − 1) ⋅K ⋅ (n − k 1) . (5)
Предыдущую формулу можно записать следующим образом:
A
k n! . (6)
n (n − k )!
Пример.Найдем число всех отображений и число инъективных отображений из k-множества X в n-множество Y.
Перенумеруем элементы множества X, X = {a1, a2,…, ak}. Всякое отображение f из X в Y однозначно определяется упорядоченным набором элементов множества Y вида (b1, b2, …, bk), в котором bi = f(ai). Значит, число всех отображений из X в Y равно числу размещений с повторениями из n элементов по k, то есть числу nk. Таким образом, получаем
формулу:
|YX|= nk,
где через YX обозначено множество всех отображений из X в Y.
Если k > n, инъективных отображений из X в Y нет. При k ≤ n отображение f из X в Y инъективно, если в наборе (b1, b2, …, bk) все элементы различны, т. е. набор (b1, b2, …, bk) является размещением без повторений. Следовательно, число
инъективных отображений из X в Y равно числу
n
размещений
Ak .
Размещения объема n, составленные из элементов n-множества X называются перестановками элементов множества X.
Задать перестановку элементов множества X – это значит линейно упорядочить элементы этого множества. Число всех перестановок из n элементов обозначается через Pn. Используя формулу (5) при k = n, получаем:
Pn = n!. (7)
Пример.Перечислим перестановки элементов множества X = {1, 2, 3}:
123; 132; 213; 231; 312; 321.
В заключение рассмотрим перестановки с повторениями. Пусть X = {a1, a2,…, ak} – некоторое k-множество. Перестанов- кой с повторениями типа (n1, n2,…, nk) называется упорядочен- ный набор элементов множества X вида (x1, x2,…, xn), в котором элемент a1 встречается n1 раз, элемент a2 встречается n2 раз, …, элемент ak встречается nk раз. Естественно, n1 + n2 +…+ nk = n. Число перестановок типа (n1, n2,…, nk) обозначается через P(n1, n2,…, nk).
Пример.Перечислим все перестановки типа (2, 2) из элементов множества X = {a, b}:
aabb; abab; abba; baab; baba; bbaa.
Чтобы получить формулу для вычисления P(n1, n2,…, nk), воспользуемся следующей метафорой. Элементы множества X будем считать буквами, а перестановки с повторениями – словами. Для определенности будем считать, что X содержит три буквы a, b, c. Рассмотрим произвольное слово w длины n, содержащее n1 букв a, n2 букв b и n3 букв c. Подсчитаем число перестановок букв, при которых слово w не меняется. Буквы a можно произвольно переставлять на n1 местах, на которых они расположены. Это можно сделать n1! числом способов. Точно так же буквы b можно переставить n2! способами, буквы c – n3! способами. По правилу произведения число перестановок букв, при которых слово w не меняется, равно n1!n2!n3!. Таким образом, для каждого слова имеется n1!n2!n3! перестановок букв, которые его не меняют. Общее число перестановок букв равно n!. Следовательно, число слов, т. е. перестановок типа
(n1, n2, n3), равно
n! .
n1!n2!n3!
Предыдущее рассуждение легко переносится на общий
случай и приводит к следующей формуле:
P(n1
, n2
,K, nk )
n!
n1!n2!Knk !
. (8)
Пример.Пакет акций состоит из акций четырех типов: 5
акций типа A, 3 акции типа B и по одной акции типов C и D.
Сколькими способами можно распродать этот пакет, продавая по одной акции ежедневно?
Каждая распродажа однозначно определяется словом длины 10, составленном из пяти букв A, трех букв B, одной буквы C и одной буквы D (буква, стоящая на месте i, означает, что в день i была продана акция соответствующего типа).
n! .
Предыдущее рассуждение легко переносится на общий
5! ⋅3!⋅1!⋅1!