Комбинаторика. Размещения. Решение задач

Размещения. Формула для числа размещений

1) Размещения с повторениями

Если все элементы кортежа принадлежат одному и тому же множеству Х, то говорят о кортеже из элементов множества Х.

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

Определение. Кортеж длины k, составленный из элементов множества Х, называется размещением с повторениями из n элементов по k (в кортеже его элементы могут повторяться).

Число всех размещений с повторениями из n элементов по k зависит от n и от k (а не от природы множества Х). Это число обозначается . Формула для его нахождения выводится с помощью правила произведения:

(1)

Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр?

Решение. Х = {1, 3, 5, 7, 9}, .

Трёхзначное число - это кортеж длины 3, составленный из элементов множества X, причем цифры в числе могут повторяться. Значит, этих чисел будет столько, сколько существует размещений с повторениями из 5 элементов по 3:

.

Заметим, что эту задачу можно было решить и с помощью правила произведения, которое работало бы и в том случае, если в условии поменять нечётные цифры на чётные. А вот понятие размещений и формула (1) в этом случае не сработали бы!

Замечание. Если повторения допускаются, то длина кортежа k может быть больше числа элементов множества Х.

2) Размещения без повторений

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

Определение. Кортеж длины k, в котором все элементы различны, составленный из элементов множества Х, называется размещением без повторений из n элементов по k (в кортеже элементы не повторяются!).

Так как повторения в кортеже не допускаются, то теперь k должно быть не больше n.

Найдём - число всех размещений без повторений из n элементов по k.

Для выбора элемента имеется n возможностей. После выбора элемента , элемент можно выбрать -м способом и так далее. Тогда

(2)

Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр так, чтобы цифры в каждом числе не повторялись?

Решение. Х = {1, 3, 5, 7, 9}, .

Трёхзначное число - это кортеж длины 3 без повторений, составленный из элементов множества X. Значит, этих чисел будет столько, сколько существует размещений без повторений из 5 элементов по 3:

.

Задачи

1. Ф. Из трех стаканов сока - ананасового (а), брусничного (б) и виноградного (в) - Иван решил последовательно выпить два. Перечислить все варианты, которыми это можно сделать.

Решение.

Это задача о выборе двух элементов из трех с учетом порядка выбора. Перечислим эти варианты:

аб, ба, ва,

ав, бв, вб.

Если учащимся известна формула для числа размещений, то количество вариантов равно: А вариантов.

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

2.Ф. Сколькими способами могут быть заняты первое, второе и третье места (по одному человеку на место) на соревнованиях, в которых участвуют: 1) 5 человек; 2) 6 человек?

Решение.

Это задача о выборе трех элементов из 5 или 6 с учетом порядка выбора.

1)По правилу произведения 5 • 4 • 3 = 60 способов.

2)По правилу произведения = 120 способов. Если учащиеся знают формулу для числа размещений, то получаем соответственно:

A

A

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

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

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

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

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

Решение.

Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номеров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элементов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:

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

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

4. Т. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?

Решение.

Из 30 элементов выбираем 2, причем порядок выбора имеет значение. Количество способов выбора равно A = 30 • 29 = 870 способов.

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

5. Т. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?

Решение.

Выбор из 8 по 3 с учетом порядка: A = 336 способов.

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

6. Т. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?

Решение.

Выбираем из 7 запасных путей 4 пути для размещения на них поездов; порядок выбора имеет значение: A= 840 способов.

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

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

Решение.

Выбираем из 7 разноцветных материалов 3 полосы для флага; порядок выбора имеет значение (флаги из трех одинаковых цветов, расположенных в разном порядке, - разные).

A= 210 способов.

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

8. Т. На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4x100 м на первом, втором, третьем и четвертом этапах?

Решение.

Выбор из 12 по 4 с учетом порядка: A= 11 880 способов.

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

9. М. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?

Решение.

Выбираем 3 призеров из 15 участников конкурса с учетом порядка (кому какая премия):

A= 2 730 способов.

10. Т. Сколькими способами 6 студентов, сдающих эк. замен, могут занять места в аудитории, в которой стоит 20 одноместных столов?

Решение.

Выбираем 6 столов для студентов из 20 имеющихся: порядок выбора учитывается (кто сидит у окна, кто около преподавателя и т. п.):

А= 27 907 200 способов.

Ответ: 27 907 200 способов.

11. Т. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?

Решение.

а) Выбираем 2 места для фотографий из 6 свободных мест в альбоме: А= 30 способов.

б) Выбираем 4 места для фотографий из А= 360 способов.

в) Выбираем 6 мест из 6 (делаем всевозможные перестановки из 6 фотографий):

А= 6! = 720 способов.

Ответ: а) 30 способов; б) 360 способов; в) 720 способов.

12. М. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?

Решение.

Выбираем 5 букв для обозначения точек из 26 букв в алфавите; порядок выбора имеет значение (какую точку какой буквой обозначим): А= 7 893 600 способов.

Ответ: 7 893 600 способов.

13. Т. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4,

6,8?

Решение.

а) Выбираем 4 цифры из 5 данных; порядок выбора имеет значение: А= 120 чисел.

б) Выбираем 4 цифры из 5, но на первое место нельзя выбирать ноль.

Используем метод исключения лишних элементов: если на первое место выбран ноль, то после этого выбираем еще на 3 места цифры из 4 оставшихся, получаем А = 24 «нулевых» комбинаций, которые недопустимы.

Количество четырехзначных чисел, которые можно составить из данных 5 чисел, равно:

А = 120 - 24 = 96 чисел.

Можно рассуждать, непосредственно используя правило произведения: первый выбор - 4 варианта, второй выбор - 4 варианта (включая ноль), третий выбор - 3 варианта, четвертый выбор -2 варианта. Всего 4 • 4 • 3 • 2 = 96 чисел.

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

14. Т. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:

а) не встречаются цифры 6 и 7;

б) цифра 8 является последней?

Решение.

а) Выбираем 3 цифры из 7 (без 6 и без 7) с учетом порядка выбора; число вариантов: А == 210 чисел.

б) Фиксируем цифру 8 на последнем месте; на остальные два места перед ней можно выбрать любые 2 цифры из 8 оставшихся ( с учетом порядка выбора). Количество вариантов: А = 56 чисел.

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

15. М. Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?

Решение.

Выбираем из 10 цифр семь, причем первый выбор делается из 9 цифр (без нуля). Используя метод исключения лишних вариантов, получаем: АА 544 320 номеров.

Ответ: 544 320 телефонных номеров.

16. Т. Сколько различных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5, таких, которые являются: а) четными; б) кратными 5?

Решение.

Выбираем 3 цифры из 5 данных, причем:

а) последней цифрой должна быть 2 или 4; количество вариантов А (фиксирована 2) + А (фиксирована 4) = = 24 числа;

б) последней цифрой должна быть 5; количество вариантов равно А (фиксирована 5) = = 12 чисел.

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

17. Т. Номер машины в некотором городе состоит из двух различных букв, взятых из набора М, Н, К, Т, С, и трех различных цифр. Сколько машин можно обеспечить такими номерами?

Решение.

Выбираем (без повторений) 2 буквы из 5 и 3 цифры из 10; порядок выбора учитывается (номера 012 КТ и 102 ТК - разные). Количество способов: выбор букв: А = 20; выбор цифр: А = 720.

Каждый вариант выбора букв может сочетаться с каждым вариантом выбора цифр, поэтому по правилу произведения общее число способов равно: А720 = 14 400 способов.

Ответ: 14 400 способов.

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

Решение.

Поскольку каждая пара команд сыграла между собой по две игры (на своем и на чужом поле), то выбор пары осуществляется с учетом порядка, т. е. составляются всевозможные размещения из n по 2. По условию задачи А n = , n = 6.

Ответ: 6 команд.

19. Т. Из группы туристов требуется выбрать дежурного и его помощника. Если туристов было бы на одного больше, то возможностей выбора было бы в 1,25 раза больше. Сколько туристов в группе?

Решение.

Выбор пары из совокупности с учетом порядка (размещения). По условию задачи: По условию задачи А(n - 1) , n+1=1,25; 4(n+1)=5(n-1); n=9

Ответ: 9 туристов.

20. Ф. Сколькими способами четыре пассажира -Алексеев, Смирнов, Федоров и Харитонов - могут разместиться в Девяти вагонах поезда, если:

а) все они хотят ехать в разных вагонах;

б) Алексеев и Смирнов хотят ехать в одном вагоне, а Федоров и Харитонов - в других вагонах, причем различных?

Решение.

Вагоны поезда пронумерованы; осуществляется выбор 4 из 9 вагонов для размещения пассажиров; порядок выбора имеет значение (каждому пассажиру сообщаем номер вагона).

б) Двое едут в одном вагоне, а двое - в других, причем различных. «Склеиваем» два элемента из 4; количество способов размещения равно: А= 504.

Ответ: а) 3 024 способа; б) 504 способа.

21. Ф. Высказать гипотезу о числе всевозможных разбиений п элементов на 3 группы.

Решение.

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

1

1

1

1

2

2

2

…

2

3

3

3

3

n ячеек

Подсчитаем, сколько есть вариантов заполнения этой линейки ячеек.

Первую ячейку можно заполнить одним из трех способов (записать 1, или записать 2, или записать 3). Точно так же можно заполнить вторую, третью и все последующие ячейки до конца линейки.

По комбинаторному правилу произведения общее число способов равно:

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

при п = 1 есть 3 способа, т. е. З¹;

при п= 2 есть 9 способов, т. е. 3²;

при п=3 есть 27 способов, т. е. З³.

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

Ответ: 3^п способов.

Замечание. Полученная формула - это формула для числа размещений из п элементов по 3 с повторениями: А = 3^п.

Литература

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.