Тема: "Перестановки"

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

• Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.

Рассмотрим задачу:

• Пусть имеются три книги. Обозначим их буквами а, в и с. Эти книги можно расставить на полке по разному.
• Если первой поставить книгу а, то возможны такие расположения книг: авс, асв .
• Если первой поставить книгу в , то возможны следующие варианты: вас, вса.
• Если первой поставить книгу с, по получим такие расположения: сва, сав .
• Получили 6 вариантов расположения книг на полке.

Каждое из таких расположений называют перестановкой из трех элементов.

• Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке.

• Число перестановок из n элементов обозначают символом Р n
• (читается Р из n) .

Второй способ решения:

• Для того, чтобы найти число перестановок из трёх элементов, можно не выписывать эти перестановки, а воспользоваться правилом умножения.

• Будем рассуждать так:
• На первое место можно поставить любой из трёх элементов;
• На второе место можно поставить любой из двух оставшихся элементов;
• На третье место можно поставить последний третий элемент.
• Значит, число перестановок из трех элементов равно 3 · 2 · 1, т.е. 6. (вариантов)

Задача 1.

• Сколькими способами могут быть расставлены 8 участниц финального забега на 8 беговых дорожках?

Решение.

• Существует Р 8 всевозможных перестановок из 8 элементов, т.е.
• Р 8 = 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1= 40 320 (способов)
• Ответ: 40 320 способов .

Задача 2.

• В семье - 6 человек , и за столом в кухне стоят 6 стульев . В семье решили каждый вечер, ужиная, рассаживаться на эти 6 стульев по новому.
• Сколько дней члены семьи смогут делать это без повторений?
• (т.е. нас интересует сколько всего существует различных способов их размещения на стульях).

Будем рассуждать так:

• Будем считать, что в семье бабушка, дедушка, мама, папа, дочь и сын.
• Предположим, что первой усаживается бабушка. У неё есть 6 вариантов выбора стула.

• Вторым садится дедушка. У него есть 5 вариантов выбора стула из оставшихся.

• Третьим садится мама и выбирает стул из 4 оставшихся.

• У папы будет уже 3 варианта, у дочки – 2, ну а сын сядет на единственный незанятый стул.
• По правилу умножения получаем:

6 · 5 · 4 · 3 · 2 · 1 = 720 различных способов размещения.

Таким образом,

в « игру с рассаживаниями»

семья может играть 720 дней,

т.е. почти 2 года.

Ответ : 720 .

Задача 3.

• Десять разных писем раскладывают по одному в десять конвертов. Сколько существует способов такого раскладывания?

• Предложенная ситуация отличается от предыдущей тем, что там были люди и стулья, а здесь письма и конверты.
• Однако и здесь, и там требуется узнать, сколькими способами можно разместить n предметов на n местах.

• Решение.

• Повторяя предыдущее решение, получаем, что всего имеется

10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 3 628 800 способов раскладывания писем по конвертам.

Более 3,5 миллионов!!!

• Как мы видим, условия задач разные, а решения одинаковы.
• Поэтому удобно ввести одинаковые обозначения для таких решений.

• Определение: Произведение первых подряд идущих n натуральных чисел обозначают n !
• n! = 1· 2· 3· …· (n-2)(n-1)n

Таким образом, число всевозможных перестановок из n элементов вычисляется по формуле Р n = n!

• Задача 1.

• Сколькими способами могут быть расставлены 8 участниц финального забега на восьми беговых дорожках?

• Решение.

• Т.к. число способов равно числу перестановок из 8 элементов, то по формуле числа перестановок находим, что
• Р 8 = 8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40 320

• Значит, существует 40 320 способов расстановки участниц забега на восьми беговых дорожках.

Несколько первых значений для n!

• 1! = 1
• 2! = 1 · 2 = 2
• 3! = 1 · 2 · 3 = 6
• 4! = 1 · 2 · 3 · 4 = 24
• 5! = 4! · 5 = 120
• 6! = 5! · 6 = 720 и т.д.

Задача 4.

• Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0 ,2,4,6?

• Решение.

Из цифр 0,2,4,6 можно получить Р 4 перестановок. Но из этого числа надо исключить те перестановки, которые начинаются с нуля, т.к. натуральное число не может начинаться с цифры 0. Число перестановок с нулем в начале равно трём, т.е. Р 3 . Значит, искомое число четырехзначных чисел равно

• Получаем:

Задача 5.

• Имеется 9 различных книг, четыре из которых - учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

• Решение.

• Сначала рассмотрим учебники как одну книгу. Тогда на полке надо расставить не 9 , а 6 книг. Это можно сделать Р 6 способами. В каждой из полученных комбинаций можно выполнить Р 4 перестановок учебников. Значит, искомое число способов разложения книг на полке равно произведению Р 6 · Р 4 = 6! · 4! = 720 · 24 = 17 280.

Задача 6.

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

а)Сколько существует способов построения?

б) Сколько существует способов построения, если первым стоит капитан, а остальные в произвольном порядке?

Решение.

• а) К В . . . . . . . . .
• Т.к. капитан и вратарь занимают постоянные первые два места, то всевозможных перестановок будет Р 9 = 9!= 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1= 362 880 (способов).
• б)т.к. только капитан занимает постоянное место, то всевозможных перестановок будет Р 10 = 10! = 3 628 800 (способов)

Задача 7.

• Сколькими способами можно обозначить вершины куба буквами

A,B,C,D,E , F,G,K ?

Задача 8.

• В гостинице семь одноместных номеров, и семеро гостей желают в них разместиться, причем трое заранее зарезервировали конкретные номера.
• Найдите число способов расселения семи гостей по семи номерам.

Задача 9.

• а) На дверях четырех одинаковых кабинетов надо повесить таблички с фамилиями четырех заместителей директора. Сколькими способами можно это сделать?

• б) В 9 классе в среду 5 уроков: алгебра, геометрия, физкультура, русский язык, английский язык.
• Сколько можно составить вариантов расписания на этот день?
• Сколько можно составить вариантов расписания, если алгебра и геометрия стоят вместе?

• в) Сколькими способами четыре вора могут разбежаться по одному на все четыре стороны?

• г)Адъютант должен развести пять копий приказа генерала по пяти полкам. Сколькими способами он может выбрать маршрут доставки копий приказа?

Ответы:

• 1. №7. 40320 способов.
• 2. №8. 24 способа.
• 3.№9. а) 24
• б) 120
• в) 24
• г) 120.

Домашнее задание:

• Изучить п. 31
• Решить № 734, №737, №742.