Сколькими способами могут занять первое второе

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

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

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 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4×100 м на первом, вто­ром, третьем и четвертом этапах?

Выбор из 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,

а) Выбираем 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.

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:

Источник