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

Кортеж длины k, составленный из элементов m-множества Х, называют размещением с повторениями изm элементов по k, а число таких кортежей обозначают .

=m^k (1)

Например, из 4-множества Х={a, b, c, d} можно составить 16 кортежей длины 2:

(a,a), (a,b), (a,c), (a,d),

(b,a), (b,b), (b,c), (b,d),

(c,a), (c,b), (c,c), (c,d),

(d,a), (d,b), (d,c), (d,d), т.е. 2⁴=16.

Задача.Найти число подмножеств m-множества Х.

Решение. Перенумеруем это множество: Х={х₁; х₂; ...,х_m}. Каждое подмножество можно „зашифровать” с помощью кортежа длины m из нулей и единиц (если элемент с данным номером входит в подмножество, пишем 1, если нет, пишем 0). Например, 5-множество Х={х₁; х₂; х₃, х₄, х₅}. Тогда кортеж (0; 1; 1; 0; 1) шифрует подмножество

{х₂; х₃, х₅}, кортеж (0; 0; 0; 0; 0) шифрует пустое подмножество, (1; 1; 1; 1; 1) – все множество Х. Потому найти число подмножеств m-множества Х – это все равно, что найти число кортежей длины m, составленных из элементов 2-множества {0;1}. По формуле (1) оно равно 2^m.

Число подмножеств m-множества Х равно 2^m.

Например, множество Х={а, в, с} имеет 2³=8 подмножеств: Ø, {а}, {в}, {с}, {а, в}, {а, с}, {в, с}, {а, в, с}.

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

Конечное множество Х называется упорядоченным, если его элементы перенумерованы некоторым образом (в отличие от кортежа в нем элементы не повторяются!).

Например, кортеж (а; б; а, с; д; а) не является упорядоченным множеством; (а; б; в; г; д; е) – является.

Одно и то же множество можно упорядочить различными способами. Например, множество школьников в классе можно упорядочить по росту, весу, алфавиту и.т.д.

Задача. Сколькими способами можно упорядочить m-множество Х?

Решение. Каждое упорядочение заключается в том, что какой-то элемент получает номер 1, какой-то -№ 2, и т.д., последний - № m.

№ 1 может получить любой из элементов множества Х, следовательно, выбор первого элемента можно сделать m способами.

№ 2 уже можно выбрать (m-1) способами.

№ 3 можно выбрать (m-2) способами и т.д.

Последний элемент можно выбрать только одним способом. Значит общее число способов упорядочения равно m^.(m-1)^.(m-2)^. … ^.1.

! Произведение первых m натуральных чисел в математике называют «m-факториал» и обозначают m!

Например, 4!=1^.2^.3^.4=24

Таким образом, число различных упорядочений m-множества Х равно m!

Различные упорядочения m-множестваназывают перестановками без повторений из m элементов. Число таких перестановок обозначают Р_m.

P_m=m!

В задаче 2 нужно было найти число перестановок, составленных из 6 элементов, т.е. Р₆=6!=720.

Кортежи длины m, в которые входит m₁ раз элемент а₁, m₂ раз элемент а₂, …, m_k раз элемент а_k (m₁₊m_2+…+m_k=m), называют перестановками с повторениями состава (m_1, m_2, …, m_k). Их число выражается формулой: .

Пример. Сколькими способами можно переставить буквы в слове математика?

Решение. В это слово входят две буквы «м», три буквы «а», две буквы «т» и по одному разу буквы «е», «и», «к». Число перестановок равно:

.