1) Перестановки без повторений.
Определение 3: Пусть - конечное множество из элементов. Перестановками из элементов множества называются все размещения из элементов множества . Обозначается: .
Согласно определению:
.
Таким образом: .
Доказательство. Рассмотрим произвольное множество из элементов. Построим всевозможные расстановки из этих элементов. На первое место расстановки можно поставить любой из элементов ( способов выбора первого элемента). После того, как первый элемент выбран и независимо как он выбран, второй элемент можно выбрать способом. Для выбора третьего элемента остается способа и т.д. Последний элемент выбирается соответственно одним способом. Тогда, в силу комбинаторного принципа умножения, количество таких расстановок будет равно:
Пример: Сколькими способами трое друзей могут занять в кинотеатре места с номерами 1, 2 и 3.
Решение. Количество искомых способов будет равно числу перестановок без повторений из трех элементов: способов. При необходимости эти способы можно перебрать.
|
|
Перестановки букв некоторого слова называют анаграммами. Открытые еще в ІІІ веке до нашей эры греческим грамматиком Ликофроном анаграммы до сих пор привлекают внимание языковедов, поэтов и любителей словесности. Мастера словесных игр помимо эрудиции и большого запаса слов знают много секретов, связанных с комбинаторными навыками, один из которых – анаграммы. Часто требуется среди всех перестановок выбрать те, которые обладают определенным свойством. Например, среди анаграмм слова «крот», которых всего , только одна, не считая самого слова «крот», имеет смысл в русском языке – «корт».
Кроме линейных перестановок, можно рассматривать перестановки круговые (или циклические). В этом случае перестановки, переходящие друг в друга при вращении, считаются одинаковыми и не должны засчитываться. Число круговых перестановок из различных элементов равно
Пример: Сколькими способами 7 детей могут стать в хоровод?
Решение. Число линейных перестановок 7 детей будет равно . Если хоровод уже сформирован, тогда для него существует 7 круговых перестановок, переходящих друг в друга при повороте. Эти перестановки не должны быть засчитаны, поэтому круговых перестановок из 7 элементов будет .
2) Перестановки с повторениями.
Перестановки с повторениями используются в тех задачах, в которых речь идёт не о единичных объектах, а о видах, классах, сортах элементов. Понятно, что внутри каждого вида элементы повторяются.
Пусть имеются предметы различных типов:
.
Сколькими способами можно переставить местами элемент первого вида, элементов второго вида,..., элементов последнего вида?
|
|
Число элементов в каждой перестановке равно: .
Перестановки элементов внутри вида не меняет перестановку. Она изменится только в случае межвидовых перестановок. Если бы все элементы были бы различными, то число всех перестановок равнялось бы . Но в силу того, что есть повторяющиеся объекты, получится меньшее число перестановок.
Теорема 3: Число различных перестановок с повторениями находится по формуле:
, где .
Замечание: В комбинаторике если не нужно засчитывать какое-то число способов, то на это число делят, т.е. выполняется действие обратное умножению.
Поэтому в знаменателе дроби стоят числа (число перестановок элементов первого вида, которые не нужно засчитывать), (число перестановок элементов второго вида) и т. д. Перестановки элементов первого типа, второго типа и т.д. можно делать независимо друг от друга, поэтому по правилу умножения элементы данной перестановки можно переставлять способами. Значит, число различных перестановок с повторениями будет равно указанному числу.
Например, перестановки букв в словах мама, математика, анаграммы – есть перестановки с повторениями.