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

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

Размещения с повторениями - student2.ru =mk (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), т.е. 24=16.

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

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

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

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

Например, множество Х={а, в, с} имеет 23=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.

Pm=m!

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

Кортежи длины m, в которые входит m1 раз элемент а1, m2 раз элемент а2, …, mk раз элемент аk (m1+m2+…+mk=m), называют перестановками с повторениями состава (m1, m2, …, mk). Их число выражается формулой: Размещения с повторениями - student2.ru .

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

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

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

Наши рекомендации