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

Выясним, сколько всего подмножеств имеет множество с .

Теорема. Число всех подмножеств множества из элементов равно т.е.

Доказательство: Перенумеруем элементы множества и для каждого подмножества построим последовательность длины из нулей и единиц по следующему правилу: на - ом месте пишем 1, если элемент и пишем 0, если . Итак каждому подмножеству будет соответствовать своя последовательность из нулей и единиц. Например, пустому множеству соответствует последовательность из одних нулей, а самому множеству – последовательность из одних единиц. Ясно, что справедливо и обратное утверждение: каждой последовательности из множества последовательностей длины из нулей и единиц соответствует одно подмножество . Таким образом, между множествами и установлено взаимно однозначное соответствие. Следовательно, эти множества эквивалентны и как конечные множества имеют одинаковое количество элементов, т.е . Но . Теорема доказана.

Следствие. Справедливо равенство

поскольку число - элементных подмножеств множества из элементов, то сумма в левой части есть число всех подмножеств.

Определение. Упорядоченные - ки (кортежи длины ), содержащие все элементы множества называются перестановками этого множества. Другими словами, перестановки – это комбинации или соединения из элементов, содержащие все элементы, и которые считаются различными, если отличаются порядком элементов.

Пример 4.3: Пользуясь определением составить все перестановки множества

Решение: Всего шесть перестановок.

Теорема. Если через обозначить число всех перестановок множества , то .

Доказательство: Будем последовательно выбирать элементы множества и размещать их в определённом порядке на местах. На первое место можно поставить любой из элементов. После того как заполнено первое место, на второе место можно поставить любой из оставшихся элементов и т.д. По принципу умножения все мест можно заполнить и получить в результате перестановку способами. Теорема доказана.

Определение. Перестановки - элементных подмножеств множества называются размещениями из элементов по элементов. Другими словами, размещения из элементов по - это комбинации или соединения, содержащие различных элементов, и которые считаются различными, если отличаются либо своими элементами, либо порядком элементов.

Пример 4.4: Пользуясь определением составить все размещения из 3 по 2 для множества .

Решение: Выписываем все двухэлементные подмножества и для каждого из них – все перестановки. Получаем искомые размещения всего шесть размещений.

Теорема. Если через обозначить число всех размещений из по элементов множества , то .

Доказательство: В соответствии с определением размещений рассмотрим действие из двух этапов, приводящее в результате к получению размещения из по . Первый этап: образование - элементного подмножества, , второй этап: образование перестановки в полученном на первом этапе - элементном подмножестве, Тогда, согласно принципу умножения, имеем Теорема доказана.

Пример 4.5: Сколькими способами можно рассадить 4 учащихся на 25 местах?

Решение: Искомое число способов равно .

Определение: Упорядоченные - ки, содержащие раз элемент , причём называются перестановками с повторением.

Пример 4.6: Для множества составить все перестановки с повторением, если .

Решение: Пользуясь определением, получаем три перестановки с повторением .

Теорема: Если обозначить через число всех перестановок с повторением, то

Доказательство: Рассмотрим действие из этапа. Первый этап: образование перестановки с повторением ; второй этап: в полученной перестановке с повторением заменим все элементы разными элементами из множества и произведём перестановку их, . Третий этап: в перестановке с повторением заменим все элементы разными из оставшихся элементов множества и произведём перестановку их, Последний - ый этап: в перестановке с повторением заменим все элементы разными из оставшихся элементов множества и произведем перестановку их, . В результате описанного действия получатся все перестановки из различных элементов, т.е. таких перестановок. Теперь, согласно принципу умножения, имеем

откуда

Теорема доказана.

Пример 4.7: Сколько различных слов можно получить, переставляя буквы слова «математика»?

Решение: Искомые слова представляют собой перестановки с повторением ( – количество букв в слове) из элементов-букв множества причём . Следовательно, их число равно .

Дата добавления: 2015-10-28