Комбинаторика. Перестановки. Решение задач

Перестановки. Формула для числа перестановок

 Перестановки из n элементов

Пусть  множество Х состоит из n элементов.

Определение. Размещение без повторений из n элементов множества X по n называется перестановкой из n элементов.

 Заметим, что в любую перестановку входят все элементы множества Х, причём ровно по одному разу. То есть перестановки одна от другой отличаются только порядком следования элементов и могут получиться одна из другой перестановкой элементов (отсюда и название).

Число всех перестановок из n элементов обозначается символом .

Так как перестановки – это частный случай размещений без повторений при , то формулу для нахождения числа  получим из формулы (2), подставляя в неё :

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

       (3)

Пример. Сколькими способами можно разместить на полке 5 книг?

Решение.  Способов размещения книг на полке существует столько, сколько существует различных перестановок из пяти элементов: способов.

Замечание. Формулы (1)-(3) запоминать не обязательно: задачи на их применение всегда можно решить с помощью правила произведения. Если у учащихся существуют проблемы с составлением комбинаторных моделей задач, то лучше сделать более узким множество используемых формул и правил (чтобы было меньше возможности ошибиться). Правда, задачи, в которых используются перестановки и формула (3), обычно решаются  без особых проблем.

Задачи

1. Ф. Сколькими способами могут встать в очередь в билетную кассу: 1) 3 человека; 2) 5 человек?

     Решение.

Различные варианты расположения п человек в очереди отли­чаются один от другого только порядком расположения людей, т. е. являются различными перестановками из п элементов.

Три человека могут встать в очередь Р3 = 3! = 6 различными способами.

     Ответ: 1) 6 способов; 2) 120 способов.

2. Т. Сколькими способами 4 человека могут размес­титься на четырехместной скамейке?

     Решение.

Количество человек равно количеству мест на скамейке, по­этому количество способов размещения равно числу перестановок из 4 элементов: Р4 = 4! = 24.

Можно рассуждать по правилу произведения: для первого че­ловека можно выбрать любое из 4 мест, для второго - любое из 3 оставшихся, для третьего - любое из 2 оставшихся, последний зай­мет 1 оставшееся место; всего есть  = 24 разных способов Размещения 4 человек на четырехместной скамейке.

     Ответ: 24 способами.

3. М.  У Вовы на обед - первое, второе, третье блюда и пирожное. Он обязательно начнет с пирожного, а все остальное съест в произвольном порядке. Найдите число возможных вариан­тов обеда.

М- задачи из уч. пособия А.Г.Мордковича

Т- под ред. С.А.Теляковского

Ф- М.В.Ткачевой

     Решение.

После пирожного Вова может выбрать любое из трех блюд, за­тем - из двух, и закончить оставшимся. Общее число возможных вариантов обеда: =6.

     Ответ: 6.

4. Ф. Сколько различных правильных (с точки зрения русского языка) фраз можно составить, изменяя порядок слов в предложении: 1) «Я пошел гулять»; 2) «Во дворе гуляет кошка»?

     Решение.

Во втором предложении предлог «во» должен всегда стоять перед существительным «дворе», к которому он относится. Поэто­му, считая пару «во дворе» за одно слово, можно найти количество различных перестановок трех условных слов: Р3 = 3! = 6. Таким образом, и в этом случае можно составить 6 правильных предложений.

     Ответ: 1) 6; 2) 6.

5.  Сколькими способами можно с помощью букв К, L, М, Н обозначить вершины четырехугольника?

      Решение.

Будем считать, что вершины четырехугольника пронумерова­ны, за каждой закреплен постоянный номер. Тогда задача сводится к подсчету числа разных способов расположения 4 букв на 4 мес­тах (вершинах), т. е. к подсчету числа различных перестановок: Р4 = 4! =24 способа.

     Ответ: 24 способа.

6. Ф. Четыре друга купили билеты в кино: на 1-е и 2-е места в первом ряду и на 1-е и 2-е места во втором ряду. Скольки­ми способами друзья могут занять эти 4 места в кинотеатре?

     Решение.

Четыре друга могут занять 4 разных места Р4 = 4! = 24 различ­ными способами.

     Ответ: 24 способа.

7. Т. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?

      Решение.

Под маршрутом следует понимать порядок посещения курье­ром учреждений. Пронумеруем учреждения номерами от 1 до 7, тогда маршрут будет представляться последовательностью из 7 Цифр, порядок которых может меняться. Количество маршрутов равно числу перестановок из 7 элемен­тов: Р7= 7! = 5 040.

     Ответ: 5 040 маршрутов.

8. Т. Сколько существует выражений, тождественно равных произведению abcde, которые получаются из него переста­новкой множителей?

     Решение.

Дано произведение пяти различных сомножителей abcde, поря­док которых может меняться (при перестановке множителей про­изведение не меняется).

Всего существует Р5 = 5! = 120 различных способов располо­жения пяти множителей; один из них (abcde) считаем исходным, остальные 119 выражений тождественно равны данному.

     Ответ: 119 выражений.

9. Т.  Ольга помнит, что телефон подруги оканчивает­ся цифрами 5, 7, 8, но забыла, в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется пере­брать, чтобы дозвониться подруге.

     Решение.

Три последних цифры телефонного номера могут быть распо­ложены в одном из Р3 =3! =6 возможных порядков, из которых только один верный. Ольга может сразу набрать верный вариант, может набрать его третьим, и т. д. Наибольшее число вариантов ей придется набрать, если правильный вариант окажется последним, т. е. шестым.

     Ответ: 6 вариантов.

10. Т. Сколько шестизначных чисел (без повторения цифр) можно составить из цифр: а) 1,2, 5, 6, 7, 8; б) 0, 2, 5, 6, 7, 8? Решение.

     а)  Дано 6 цифр: 1, 2, 5, 6, 7, 8, из них можно составлять разные шестизначные числа, только переставляя эти цифры местами. Коли­чество различных шестизначных чисел при этом равно Р6 = 6! = 720.

     б)  Дано 6 цифр: 0, 2, 5, 6, 7, 8, из них нужно составлять различ­ные шестизначные числа. Отличие от предыдущей задачи состоит в том, что ноль не может стоять на первом месте.

Можно напрямую применить правило произведения: на первое место можно выбрать любую из 5 цифр (кроме нуля); на второе место - любую из 5 оставшихся цифр (4 «ненулевые» и теперь счи­таем ноль); на третье место - любую из 4 оставшихся после первых двух выборов цифр, и т. д. Общее количество вариантов равно: = 600.

Можно применить метод исключения лишних вариантов. 6 цифр можно переставить Р6 = 6! = 720 различными способами. Среди этих способов будут такие, в которых на первом месте стоит ноль, что недопустимо. Подсчитаем количество этих недопусти­мых вариантов. Если на первом месте стоит ноль (он фиксирован), то на последующих пяти местах могут стоять в произвольном по­рядке «ненулевые» цифры 2, 5, 6, 7, 8. Количество различных спо­собов, которыми можно разместить 5 цифр на 5 местах, равно Р5 = 5! = 120, т. е. количество перестановок чисел, начинающихся с нуля, равно 120. Искомое количество различных шестизначных чисел в этом случае равно: Р6 - Р5 = 720 - 120 = 600.

     Ответ: а) 720; б) 600 чисел.

11. Т. Сколько среди четырехзначных чисел (без по­вторения цифр), составленных из цифр 3, 5, 7, 9,  таких, которые: а) начинаются с цифры 3;

б) кратны 15?

     Решение.

а) Из цифр 3, 5, 7, 9 составляем четырехзначные числа, начинающиеся с цифры 3.

Фиксируем цифру 3 на первом месте; тогда на трех оставшихся местах в произвольном порядке могут располагаться цифры 5, 7 9 Общее количество вариантов их расположения равно Р₃= 3!=6. Столько и будет разных четырехзначных чисел, составленных из данных цифр и начинающихся с цифры 3.

     б) Заметим, что сумма данных цифр 3 + 5 + 7 + 9 = 24 делится на 3, следовательно, любое четырехзначное число, составленное из этих цифр, делится на 3. Для того, чтобы некоторые из этих чисел делились на 15, необходимо, чтобы они заканчивались цифрой 5.

Фиксируем цифру 5 на последнем месте; остальные 3 цифры можно разместить на трех местах перед 5 Рз = 3! = 6 различными способами. Столько и будет разных четырехзначных чисел, состав­ленных из данных цифр, которые делятся на 15.

     Ответ: а) 6 чисел; б) 6 чисел.

12. Т. Найдите сумму цифр всех четырехзначных чи­сел, которые можно составить из цифр 1, 3, 5, 7 (без их повторе­ния).

     Решение.

Каждое четырехзначное число, составленное из цифр 1, 3, 5, 7 (без повторения), имеет сумму цифр, равную 1+3 + 5 + 7=16.

Из этих цифр можно составить Р4 = 4! = 24 различных числа, отличающихся только порядком цифр. Сумма цифр всех этих чисел будет равна

16  = 384.

     Ответ: 384.

13. Т. Семь мальчиков, в число которых входят Олег и Игорь, становятся в ряд. Найдите число возможных комбинаций, если:

     а)  Олег должен находиться в конце ряда;

     б)  Олег должен находиться в начале ряда, а Игорь - в конце ряда;

     в)  Олег и Игорь должны стоять рядом.
     Решение.

     а) Всего 7 мальчиков на 7 местах, но один элемент фиксирован, не переставляется (Олег находится в конце ряда). Число возмож­ных комбинаций при этом равно числу перестановок 6 мальчиков, стоящих перед Олегом: Р6=6!=720.

пару как единый элемент, переставляемый с другими пятью эле­ментами. Число возможных комбинаций тогда будет Р6 = 6! = 720.

Пусть теперь Олег и Игорь стоят рядом в порядке ИО. Тогда получим еще Р6 = 6! = 720 других комбинаций.

Общее число комбинаций, в которых Олег и Игорь стоят рядом (в любом порядке) равно 720 + 720 = 1 440.

     Ответ: а) 720; б) 120; в) 1 440 комбинаций.

14. М. Одиннадцать футболистов строятся перед нача­лом матча. Первым становится капитан, вторым - вратарь, а ос­тальные - случайным образом. Сколько существует способов по­строения?

     Решение.

После капитана и вратаря третий игрок может выбрать любое из 9 оставшихся мест, следующий - из 8, и т. д. Общее число спо­собов построения по правилу произведения равно:

1 =362 880, или Р₉= 9! = 362 880.

     Ответ: 362 880.

15. М. Сколькими способами можно обозначить вер­шины куба буквами А, В, С, D, E, F, G, K?

     Решение.

Для первой вершины можно выбрать любую из 8 букв, для вто­рой - любую из 7 оставшихся, и т. д. Общее число способов по правилу произведения равно=40 320, или Р8 = 8!

     Ответ: 40 320.

16. Т. В расписании на понедельник шесть уроков: ал­гебра, геометрия, биология, история, физкультура, химия. Сколь­кими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли рядом?

     Решение.

Всего 6 уроков, из них два урока математики должны стоять  рядом.

«Склеиваем» два элемента (алгебра и геометрия) сначала в по­рядке АГ, затем в порядке ГА. При каждом варианте «склеивания» получаем Р5 = 5! = 120 вариантов расписания. Общее число способов составить расписание равно120 (AГ) +120 (ГА) = 240.

     Ответ: 240 способов.

17. Т. Сколько существует перестановок букв слова «конус», в которых буквы  К, О, Н стоят рядом?

     Решение.

Дано 5 букв, из которых три буквы должны стоять рядом. Три буквы К, О, Н могут стоять рядом одним из Р3 = 3! = 6 спо­собов. Для каждого способа «склеивания» букв К, О, Н получаем Р3 = 3! = 6 способов перестановки букв, «склейка», У, С. Общее число различных перестановок букв слова «конус», в которых буквы К, О, Н стоят рядом, равно 6 • 6 = 36 перестано­вок- анаграмм.

     Ответ: 36 анаграмм.

18. Т. Сколькими способами 5 мальчиков и 5 девочек могут занять в театре в одном ряду места с 1 по 10? Сколькими способами они могут это сделать, если мальчики будут сидеть на нечетных местах, а девочки - на четных?

     Решение.

Каждый вариант расположения мальчиков может сочетаться с каждым из вариантов расположения девочек, поэтому по правилу произведения общее число способов рассадить детей в этом случае равно 12020= 14400.

      Ответ: 3 628 800 способов; 14 400 способов.

19. Т. Пять мальчиков и четыре девочки хотят сесть на девятиместную скамейку так, чтобы каждая девочка сидела между двумя мальчиками. Сколькими способами они могут это сделать?

     Решение.

По условию задачи мальчики и девочки должны чередоваться, т. е. девочки могут сидеть только на четных местах, а мальчики -только на нечетных. Поэтому меняться местами девочки могут только с девочками, а мальчики - только с мальчиками. Четырех девочек можно рассадить на четырех четных местах Р4 = 4! = 24 способами, а пятерых мальчиков на пяти нечетных местах Р5 = 5! = 120 способами.

Каждый способ размещения девочек может сочетаться с каж­дым способом размещения мальчиков, поэтому по правилу произ­ведения общее число способов равно: Р420 = 2 880 способов.

     Ответ: 2 880 способов.

20. Ф.  Разложить на простые множители числа 30 и 210. Сколькими способами можно записать в виде произведения про­дых множителей число: 1) 30; 2) 210?

     Решение.

Разложим данные числа на простые множители:

30 = 2;              210 = 2.

1)Число 30 можно записать в виде произведения простых мно­жителей

Р₃ = 3! = 6 разными способами (переставляя множители).

2)Число 210 можно записать в виде произведения простых
множителей Р₄ = 4! = 24 разными способами.

     Ответ: 1) 6 способов; 2) 24 способа.

21. Ф. Сколько различных четных четырехзначных чи­сел с неповторяющимися цифрами можно записать, используя цифры 1, 2, 3, 5?

     Решение.

Чтобы число было четным, оно должно заканчиваться четной цифрой, т. е. 2. Зафиксируем двойку на последнем месте, осталь­ные три цифры должны стоять перед ней в произвольном порядке. Количество различных перестановок из 3 цифр равно P3 = 3! = 6; следовательно, различных четных четырехзначных чисел будет также 6 (к каждой перестановке из трех цифр добавляется цифра 2).

     Ответ: 6 чисел.

22. Ф. Сколько различных нечетных пятизначных чи­сел, в которых нет одинаковых цифр, можно записать с помощью Цифр 1,2, 4, 6, 8?

     Решение.

Чтобы составленное число было нечетным, необходимо, чтобы оно оканчивалось нечетной цифрой, т. е. единицей. Остальные 4 Цифры можно переставлять местами, располагая каждую пере­становку перед единицей.

Общее число нечетных пятизначных чисел равно числу пере­становок: Р4 = 4! =24.

23. Ф. Сколько различных шестизначных чисел с не­повторяющимися цифрами можно записать с помощью цифр 1; 2 3, 4, 5, 6, если: 1) число должно начинаться с 56; 2) цифры 5 и 6 в числе должны стоять рядом?

     Решение.

Две цифры 5 и 6 фиксируем в начале числа и дописываем к ним различные перестановки из 4 оставшихся цифр; количество различных шестизначных чисел равно: Р4 = 4! = 24.

Условно будем считать пару 56 одной цифрой и перестав­лять ее с четырьмя остальными цифрами; получим Р5 = 5! = 120 различных чисел из 5 цифр, среди которых одна условная, двойная.

Если считать условной цифрой пару 65, то получим еще Р5 = 5! = = 120 различных чисел.

Общее количество различных шестизначных чисел, в которых циф­ры 5 и 6 стоят рядом (в любом порядке), равно 120 + 120 = 240 чисел. (Варианты 56 и 65 несовместны, не могут реализоваться одно­временно; применяем комбинаторное правило суммы.)

     Ответ: 1) 24 числа; 2) 240 чисел.

24. Ф. Сколько различных четных четырехзначных чи­сел, в записи которых нет одинаковых цифр, можно составить из цифр 1,2,3,4?

     Решение.

Четное число должно оканчиваться четной цифрой. Фиксируем на последнем месте цифру 2, тогда 3 предшест­вующие цифры можно переставить Р3 = 3! = 6 различными спосо­бами; получим 6 чисел с двойкой на конце. Фиксируем на последнем месте цифру 4, получим Р3 = 3! = 6 различных перестановок трех предшествующих цифр и 6 чисел, оканчивающихся цифрой 4.

Общее количество четных четырехзначных чисел будет 6 + 6  = 12 различных чисел.

     Ответ: 12 чисел.

Замечание. Общее количество вариантов мы находим, пользуясь комбинаторным правилом суммы (6 вариантов чисел, оканчивающихся двойкой, 6 вариантов чисел, оканчивающихся четверкой; способы построения чисел с двойкой и с четверкой на конце являются взаимоисключающими, несовместными, поэтому общее количество вариантов равно сумме числа вариантов с двой­кой на конце и числа вариантов с 4 на конце). Запись 6 + 6 = 12 лучше отражает основания наших действий, чем запись Р.

25. Ф. Сколькими способами можно записать в виде  произведения простых множителей число 1) 12; 2) 24; 3) 120?

      Решение.

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

     1) Число 12 разлагается на три простых множителя, два из ко­торых одинаковы: 12 = .

Если бы все множители были различны, то их можно было бы переставить в произведении Р3 = 3! = 6 различными способами. Чтобы перечислить эти способы, условно «различим» две двойки, подчеркнем одну из них: 12 = 2.

Тогда возможны следующие 6 вариантов разложения на жители:

Но на самом деле подчеркивание цифр не имеет в математике никакого значения, поэтому полученные 6 перестановок в обычной записи имеют вид:

т. е. фактически мы получили не 6, а 3 различные перестановки Количество перестановок уменьшилось в два раза за счет того, что мы не должны учитывать перестановки двух двоек между собой.

Обозначим Р_х искомое число перестановок из трех элементов среди которых два одинаковых; тогда полученный нами результат можно записать так: Рз = Р_хНо 2 - это количество разных перестановок из двух элементов, т. е. 2 =  = 2!  = Р₂, поэтому Р3, = Р_х  Р₂ , отсюда Р_х =.  (это формула для числа перестановок с повто­рениями).

Можно рассуждать иначе, основываясь только на комбинатор­ном правиле произведения.

Чтобы составить произведение из трех множителей, сначала выберем место для множителя 3; это можно сделать одним из трех способов. После этого оба оставшихся места заполняем двойками; это можно сделать 1 способом. По правилу произведения общее число способов равно: 3-1 =3.

2)Число 24 разлагается на четыре простых множителя, из ко­торых три - одинаковые: 24=

 Отсюда

Чтобы составить произведение из четырех множителей, снача­ла выберем место для множителя 3; это можно сделать одним из четырех способов. После этого все три оставшихся места заполним двойками; это можно сделать 1 способом (двойки неразличимы между собой, поэтому просто пишем на каждое свободное место по двойке). По правилу произведения получим 41=4  различных за­писи произведения.

3) Число 120 разлагается на 5 простых множителей (2,2,2,3,5), из которых три- одинаковые. В этом случае , Р_х=20.

     Второй способ. Составляя произведение из пяти множи­телей, сначала выберем место для пятерки (5 способов), затем для тройки (4 способа), а оставшиеся 3 места заполним двойками (1 способ); по правилу произведения 5 • 4 • 1 = 20.

     Ответ: 1) 3; 2) 4; 3) 20.

26. Ф. Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) белым, черным или зеле­ным?

     Решение.

Перестановки из 6 элементов, среди которых три - одинаковые:

Иначе: для закраски белым цветом можно выбрать одну из 6 клеток, черным - из 5, зеленым - из 4; три оставшиеся клетки за­крашиваем красным цветом. Общее число способов:  6 • 5 • 4 • 1 = 120.

     Ответ: 120 способов.

27.Т.  Пешеход должен пройти один квартал на север и три квартала на запад. Выпишите все возможные маршруты пе­шехода.

     Решение.

Будем обозначать каждый маршрут последовательностью из 4 букв: трех букв з и одной с. Каждая буква показывает, в каком направлении пешеход проходит очередной квартал. Выбрать мар­шрут - это значит выбрать для буквы с одно место из четырех воз­можных. Поэтому возможны следующие маршруты:

           С     З     З    З

           З     С     З    З

           З     З     С    З

           З     З     З    С

Количество различных маршрутов равно Р4 =   

Иначе: выбираем одно место из 4 для буквы с; количество ва­риантов равно = 4.

     Ответ: 4 маршрута.

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

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

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

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

     Решение.

     а)  Для первой таблички можно выбрать любой из 4 кабинетов,
Для второй - любой из трех оставшихся, для третьей - любой из двух оставшихся, для четвертой - один оставшийся; по правилу
произведения общее число способов равно: 4 • 3 • 2 • 1 = 24, или Р4 = 4! = 24.

     б)  На первый урок ставим любой из пяти предметов, на вто­рой - из четырех, и т. д. Общее число вариантов расписания по правилу произведения равно: = 120, или Р5 = 5! = 120.

     в)  Обозначим 4 стороны как  С, Ю, В, 3. Первый вор выбирает любую из четырех сторон, второй - из трех, третий - из двух, общее число способов равно: = 24, или Р4 = 4! = 24.

     г) Под маршрутом будем понимать последовательность, посещения полков. Первым можно

 посетить любой из 5 полков, после этого - любой из 4 оставшихся, и т. д. Общее число возможных маршрутов равно: = 120, или Р5 = 5! = 120.

     Ответ: а) 24; б) 120; в) 24; г) 120.

Литература

1.     Афанасьев В.В. Теория вероятностей в примерах и задачах, - Ярославль: ЯГПУ , 1994.

2.     Баврин И. И. Высшая математика: Учебник для студентов химико-математических специальностей педагогических вузов-2-е издание, переработанное. - М.:Просвещение, 1993.

3.     Бунимович Е. А., Булычёв В.А. Вероятность и статистика. 5-9 классы: Пособие для общеобразовательных учебных заведений, - М.:Дрофа , 2005.

4.     Виленкин Н. Я. и другие. Алгебра и математический анализ для 10 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики. - М.:Просвещение,1992.

5.     Виленкин Н. Я. и другие. Алгебра и математический анализ для 11 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики - М.:Просвещение, 1990.

6.     Глейзер Г.И. История математики в школе: 9-10 класс. Пособие для учителей. - М.: Просвещение 1983.

7.     Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Математика 9:Алгебра. Функции. Анализ данных - М.: Дрофа, 2000.

8.     Колягин и другие. Алгебра и начала анализа 11 класс. Математика в школе - 2002 - №4 - с.43,44,46.

9.     Люпшкас В.С. Факультативные курсы по математике: теория вероятностей: Учебное пособие для 9-11 классов.- М.,1991.

10.  Макарычев Ю.Н., Миндюк Н.Г. Элементы статистики и теории вероятностей: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.

11.  Мордкович А.Г., Семенов П.В. Алгебра и начала анализа 10 класс: Учебник для общеобразовательных учреждений (профильный уровень) – М.: Мнемозина, 2005.

12. Ткачева М.В., Федорова Н.Е. Элементы статистики и  вероятность: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.