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

Принцип умножения.

(Правило умножения. Правило произведения.)

При образовании последовательностей элементов из совокупностей с повторяющимися элементами, например, при составлении слов (в них буквы могут повторяться и от перестановки букв смысл слова изменяется), при образовании телефонных номеров, или решая такую задачу как выпуск номерных знаков автомобилей (в номерах цифры также могут повторяться и важен порядок расположения цифр,188 и 818-разные номера) уже недостаточно понятия множества, так как в множествах элементы не повторяются и их порядок расположения не играет роли. Для таких совокупностей используется другое понятие, отличное от понятия множества. Чаще всего используется для этих целей термин кортеж. Это слово заимствовано из французского языка и означает буквально торжественное шествие. В русском языке также существуют такие понятия как кортеж автомобилей, свадебный кортеж. В кортежах автомобилей могут принимать участие автомашины одинаковых марок. Считая автомобили одной и той же марки неразличимыми, получаем, что в этом кортеже один и тот же элемент повторяется несколько раз. Остановимся на понятии кортеж в математическом смысле. Пусть имеется несколько конечных множеств Х_{1 , …,} Х_{k ,} состоящих соответственно из n₁, …, n_k элементов. Будем теперь последовательно отбирать из этих множеств их элементы: из множества Х₁ отберём случайным образом элемент a₁,а из множества Х₂ отберём элемент a₂ и так далее до отбора элемента a_k из множества Х_k. Полученная последовательность отобранных элементов, расположенная в порядке их отбора (a₁, a₂,…, a_k) называется кортежем длины k, составленнымиз элементов множеств Х_{1 , …,} Х_k. Элементы a₁, a₂,…, a_k называются компонентами, или координатами кортежа.. Наряду со словом кортеж в математике применяют термины «конечная последовательность», «размещение», «вектор», «слово» и т.д..

Два кортежа называют равными в том и только в том случае, когда они имеют одинаковую длину, а на соответствующих местах стоят одни и те же элементы. Допускается, что множества Х_{1 , …,} Х_k могут иметь общие элементы и в кортежах координаты могут повторяться. Например, кортеж может иметь вид: (6,6,2,2,3,6,2,4,3,6). Возможен также случай, когда все множества Х_{1 , …,} Х_k совпадают. Тогда считают, что располагают одним множеством Х, извлечённые элементы из которого после записи в кортеж возвращают в исходное множество.

Кортежами являются номера телефонов, составленные из множества Х ={0,1,2,3,4,5,6,7,8,9}, записи слов, образованные из букв соответствующего языка, предложения, составленные из слов, населенные пункты, компонентами которых можно считать дома или коттеджи одинаковой или различной архитектуры.

Правило произведения основывается на следующих рассуждениях. Пусть имеются конечные множества Х_{1 , …,} Х_k, состоящие соответственно из n₁, …, n_k элементов. Подсчитаем, сколько кортежей можно составить из элементов эти множеств. Сначала найдём число кортежей длиной 1, составленных из элементов множества Х₁. Очевидно, что их будет n₁. К каждому из этих кортежей припишем справа по очереди все элементы множества Х₂. Получится n₂ кортежей длины 2, у которых первой координатой является элемент a₁, n₂ кортежей длины 2 с первой координатой a₂, и так далее до кортежа с первой координатой a_n1. Всего получается n₁ n₂ кортежей длины 2. Приписывая по очереди к этим кортежам все элементы множества Х₃ получим n₁ n₂ n₃ кортежей длины 3. Продолжая этот процесс получим n₁ n₂ … n_k кортежей длины k. Основываясь на этом можно сформулировать правило, получившее название правила произведения.

Если элемент a₁ можно выбрать n₁ способами, следующий за ним элемент a₂ можно выбрать n₂ способами и так далее до элемента а_k, который можно отобрать n_k способами, то кортеж (a₁,a₂,…, a_k) можно составить n₁ n₂ … n_k способами.

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

Пусть множества Х_{1 , …,} Х_k, из элементов которых составляются кортежи, могут иметь общие элементы. В частности, указанные множества могут совпадать с одним и тем же множеством Х, содержащим n элементов. Кортежи длины k, составленные из элементов n -множества Х, называют размещениями с повторениями из n элементов по k, а их число обозначают

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

Примеры:

1.В 1838г. изобретатель электрического телеграфа Морзе предложил для передачи сообщений по телеграфу использовать коды, состоящие из точек и тире, для представления букв, цифр и знаков препинания. Из одной точки и из одного тире можно построить два кортежа длиной один, кортеж длиной два можно составить четырьмя способами и используя далее формулу для размещений с повторениями получим.:

Длина кортежа k	Число кортежей	Состав кортежей
	21=2	•; –.
	22=4	• –;–•.
	23=8	••–;•–•;–••;– – –;•••;–•–;•– –;– –•.
	24=16	••••; •••–; ••–•; •–••; –•••; ••– –; •–•–; •– –•; – –••;–•–•;••– –; – –•–; – – –•;–•– –;•– – –;– – – –.

Кортежам точек и тире, содержащих не более четырёх знаков, можно поставить в соответствие 30 букв: 2+4+8+16. Для передачи сообщений с использованием русского алфавита (33 буквы), а также цифр и знаков препинания следует присоединить кортежи длиной пять. Тогда получится 62 кортежа: 2¹ +2² +2³+2⁴ +2⁵=62.