Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




Тридцать три буквы русского алфавита принято располагать от А до Я. Можно расположить в обратном порядке: от Я до А. Каждое расположение тридцати трех букв в определенном порядке называется их перестановкой. Количество всех таких перестановок выражается тридцатисемизначным числом.

Перестановки можно образовывать из элементов любого конечного множества.

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

Множество из трех элементов: А, Б, В – шестью способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Установленный в конечном множестве порядок элементов называют перестановкой.

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

Вычислять удобно последовательно, пользуясь рекуррентной формулой:

. (1)

Докажем ее. Пусть требуется упорядочить множество из n элементов. Какой-то из этих элементов придется поставить на последнее, n-е место. Этот элемент можно выбрать n различными способами. Если он уже выбран, то останется n-1 элемент. Ими придется занять первые n-1 мест. Это можно сделать способами (по смыслу ). Всего получается способов упорядочить множество из n элементов, т.е. .

По формуле (1) последовательно получаем:

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

Из формулы (1) вытекает, что (число перестановок из n элементов) равно произведению первых n натуральных чисел:

. (2)

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

n! (3)

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

.

Пример: Сколькими способами можно составить список из 9 студентов?

=362880.

Формула (3) применима для подсчета числа перестановок элементов множеств, т.е. когда элементы совокупности различные. Если же некоторые объекты в перестановках повторяются, то применяется формула для числа перестановок с повторениями.

Число перестановок элементов из такой совокупности будет меньше, чем из множества, где число элементов то же.

Пример: все перестановки для набора чисел (5,1,5): 515, 551, 155; все перестановки для набора чисел (5,1,2): 512, 521, 125, 152, 215, 251. В первом и втором наборах по три элемента, но там, где элементы повторяются, число перестановок меньше. Следовательно, число перестановок зависит от количества повторяющихся элементов.

В общем виде задача формулируется так: имеется n элементов, которые разбиты на k различных групп с одинаковыми элементами в первой группе, одинаковыми элементами во второй группе и одинаковыми элементами в последней, k-й группе. Сколько различных перестановок из n элементов, разбитых на k групп можно составить?

Теорема. Число различных перестановок с повторениями определяется по формуле:

. (4)

 

Пример: разобьем набор чисел предыдущего примера (5,1,5) на группы: =2 – количество 5-ок и =1 – количество 1-ниц. Тогда по формуле (4): =3.

Задачи.

1. Сколько различных трехцветных флагов с тремя горизонтальными полосами можно получить, если использовать красный, белый, синий цвета?

2. Сколькими способами можно составить список из 9 студентов?

3. В пассажирском поезде 14 вагонов. Сколькими способами можно распределить по вагонам 14 проводников, если за каждым вагоном закрепляется один проводник?

4. Найти значение выражения:

а) 8! +9!; б) ; в) .

5.Сократить дробь:

а) ; б) ; в) .

6. Из цифр 0,1,2,3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел?

7. Из цифр 1,2,3,4,5 составлены всевозможные пятизначные числа без повторения цифр. Выясните, сколько среди этих пятизначных чисел таких, которые:

а) начинаются цифрой 3;

б) не начинаются с цифры 5;

в) начинаются с 54;

г) не начинаются с 543.

8. Определить, сколько различных слов можно составить из слова «литература».

 

 




Поделиться с друзьями:


Дата добавления: 2014-11-29; Просмотров: 633; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.