Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Комбинаторика. Размещения. Решение задач

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



  • Математика

Поделитесь материалом с коллегами:

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

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

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

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

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

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

hello_html_m5bd06bcd.gif(1)

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

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

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

hello_html_m227d517.gif.

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

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

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

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

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

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

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

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

hello_html_1ed2102f.gif(2)

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

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

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

hello_html_m17194104.gif.











Задачи

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

Решение.

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

аб, ба, ва,

ав, бв, вб.

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

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

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

Решение.

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

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

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


Ahello_html_m74a2c488.gifhello_html_m53d4ecad.gifhello_html_m53d4ecad.gif

Ahello_html_m68cfb2f.gif

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


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

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

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


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

Решение.

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

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

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

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

Решение.

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

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

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

Решение.

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

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

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

Решение.

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

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

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

Решение.

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

Ahello_html_m5e94709d.gif= 210 способов.

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

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

Решение.

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

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

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

Решение.

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

Ahello_html_155c2da7.gif= 2 730 способов.

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

Решение.

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

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

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

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

Решение.

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

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

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

Аhello_html_m2945151b.gifhello_html_m44c710d4.gif= 6! = 720 способов.

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

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

Решение.

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

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

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

6,8?

Решение.

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

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

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

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

Аhello_html_10ec9935.gif = 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) с учетом порядка выбора; число вариантов: Аhello_html_607b62e6.gif =hello_html_m4cfc62f9.gif= 210 чисел.

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

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

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

Решение.

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

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

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

Решение.

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

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

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

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

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

Решение.

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

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

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

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

Решение.

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

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

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

Решение.

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

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

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

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

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

Решение.

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

б) Двое едут в одном вагоне, а двое - в других, причем различных. «Склеиваем» два элемента из 4; количество способов размещения равно: Аhello_html_m455c86c1.gif= 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). Точно так же можно заполнить вторую, третью и все последующие ячейки до конца линейки.

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

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

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

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

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

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

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

Замечание. Полученная формула - это формула для числа размещений из п элементов по 3 с повторениями: Аhello_html_3677ce3e.gif = 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.







Автор
Дата добавления 06.12.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров2758
Номер материала ДВ-235009
Получить свидетельство о публикации

Похожие материалы

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