Справочный материал «Решение комбинаторных задач. Размещения»

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

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:

n ячеек

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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

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

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

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