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

↑

▷ Содержание

Стр 1 из 3Следующая ⇒

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

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

Тридцать три буквы русского алфавита принято располагать в таком порядке:

А, Б, В, Г, Д, Е, Ё, Ж, З, И, Й, К, Л, М, Н, О, П, Р, С, Т, У, Ф, Х, Ц, Ч, Ш, Щ, Ъ, Ы, Ь, Э, Ю, Я.

При этом порядке расположения букв буква А является первой, Б - второй, В - третьей и т.д. вплоть до последней тридцать третьей буквы Я. Можно те же буквы расположить в обратном порядке: первой буквой считать букву Я, второй - Ю и т.д. вплоть до последней тридцать третьей буквы А. Каждое расположение наших тридцати трёх букв в определённом порядке называется их перестановкой. Различных перестановок тридцати трёх букв очень много: их число - тридцатисемизначное!

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

 Возьмём множество из двух элементов, для примера, из двух букв А и Б. Ясно, что их можно расположить по порядку двумя способами:

АБ или БА.

Три буквы А, Б и В можно расположить по порядку шестью способами:

АБВ; АВБ; БАВ; БВА; ВАБ; ВБА.

Определение: В комбинаторике установленный в конечном множестве порядок называют перестановкой его элементов.

Число перестановок из n элементов обозначают через . Мы нашли, что

=1,  = 2,  = 6

Например, 11 гостей можно рассадить по 11 местам за столом 39916800 способами.

Вообще  (число перестановок из n элементов) равно произведению первых n натуральных чисел:

Для произведения первых n натуральных чисел принято специальное обозначение: n! (читается «n-факториал»). Пользуясь этим обозначением, формулу (2) можно записать в виде:

Например 8!=1·2·3·4·5·6·7·8 ,но можно записать так 8!= 7!·8 или так

8!= 6! ·7·8 или 8!= 5! ·6·7·8 или 8!= 4! 5 ·6·7·8 в зависимости от того,что надо дальше делать.            ·

Для дальнейшего удобно считать, что пустое множество можно упорядочить только одним способом, т.е. Тогда формулой  можно пользоваться и при n=1:

.        

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии