Правила сложения и умножения

Установим два важных правила, которые часто применяют при решении комбинаторных задач. Рассмотрим примеры.

Пример 1.2.1. Необходимо составить варианты контрольной работы, каждый из которых должен содержать три задачи. Одна задача выбирается из любого параграфа I гл. сборника задач, вторая – из любого параграфа II гл., а последняя из любого параграфа III гл. При этом следует учесть, что I и III гл. содержат два параграфа, а II гл. – три параграфа. Сколько видов контрольной работы можно составить исходя из этих условий, если вид работы определяется только номерами параграфов, из которых выбраны задачи?

Решение. Задачу решим двумя способами.

Способ 1. Пусть каждой задаче соответствует двузначное число, где первая цифра соответствует номеру выбранной главы, а вторая – номеру параграфа. Чтобы не допустить ошибки при подсчете, воспользуемся специальным графом, который иногда называют деревом (рис. 1.2.1). Начальную точку обозначим буквой О. Двигаясь по ребрам графа слева направо, начиная с точки, получим 12 различных видов контрольной работы.

Правила сложения и умножения - student2.ru

Рис. 1.2.1. Дерево решений Примера 1.2.1

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

     

В первую клетку можно поместить либо 11, либо 12. Поэтому первую клетку можно заполнить двумя способами:

   

На «дереве» это обстоятельство иллюстрируется двумя ветвями, исходящими из точки О и ведущими к столбцу «Первая задача». Для каждого из двух способов заполнения первой клетки имеется три варианта заполнения второй клетки, так как вторую задачу можно выбрать тремя способами, поскольку гл. II содержит три параграфа:

 

Первые две клетки можно заполнить шестью способами: 2 · 3 = 6. Заметим, что именно 6 ветвей заканчиваются в столбце «Вторая задача».

Для каждого из этих шести способов существует два способа заполнения третьей клетки, так как третья задача может быть выбрана из двух параграфов главы III:

Тогда общее число способов заполнения трех клеток равно 2 · 3 · 2 = 12. Именно столько ветвей заканчивается в столбце «Третья задача». Таким образом, можно составить 12 различных видов контрольной работы.

Ответ: 12.

Пример 1.2.2.В группе 25 человек. Необходимо выбрать старосту и профорга. Сколькими способами можно это сделать?

Решение.Старостой может быть выбран любой из 25 студентов, т. е. существует 25 способов выбора старосты. Когда староста уже выбран, профоргом можно выбрать любого из оставшихся 24 студентов. Таким образом, одному способу выбора старосты соответствуют 24 способа выбора профорга. Следовательно, общее число способов выбора старосты и профорга равно 25 · 24 = 600.

Ответ:600.

Таким образом, пусть Правила сложения и умножения - student2.ru ( Правила сложения и умножения - student2.ru ) – элементы конечного множества. На основании решения примеров 1.2.1 и 1.2.2 сформулируем правило умножения.

Правило умножения.Если элемент А1 может быть выбран n1 способами, после каждого такого выбора элемент А2 может быть выбран n2 способами и т. д., после каждого (k – 1) выбора элемент Аk может быть выбран nk способами, то выбор всех А1, А2, …, Аk в указанном порядке может быть осуществлен n1 · n2…·nk способами.

Пример 1.2.3.Имеется 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколько способов выбора двух изделий возможно в данной ситуации, если учитывается порядок выбора изделий?

Решение.Условимся первым действием считать выбор изделий 1-го, вторым – выбор изделий 2-го сорта. По правилу умножения два изделия 1-го сорта можно выбрать 20 · 19 = 380 способами. Два изделия 2-го сорта можно выбрать 30 · 29 = 870 способами. Согласно условию задачи следует выбрать два изделия одного сорта, не важно какого. Это могут быть либо изделия 1-го сорта, либо изделия 2-го сорта. Таким образом, должно быть выполнено либо первое действие, либо второе, но не первое действие, а затем второе. Эти действия не могут быть выполнены одновременно, поскольку они взаимно исключают друг друга. Поэтому общее число способов выбора изделий одного сорта равно 380 + 870 = 1250.

Ответ: 1250.

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




Соображения, которые были приведены при решении примера 1.2.3, позволяют сформулировать правило сложения.

Правило сложения. Если элемент А1 может быть выбран n1 способами, элемент А2 – другими n2 способами, элемент А3 – отличными от первых двух n3 способами и т. д., элемент Аk – nk способами, отличными от первых (k – 1), то выбор одного из элементов: или А1, или А2, …, или А3 может быть осуществлен n1 + n2 +…+ nk способами.

Это правило легко распространить на любое конечное число действий.

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

Размещения

Пусть дано множество из n различных элементов. Из этого множества могут быть образованы подмножества из m различных элементов (0 ≤ m ≤ n).

Размещениями из n элементов по m в каждом называются такие соединения, из которых каждое содержит m элементов, взятых из числа данных n элементов, и которые отличаются друг от друга либо составом элементов, либо порядком их расположения (либо и тем, и другим).

Например, из одного элемента можно составить лишь одно размещение.

Из двух элементов Правила сложения и умножения - student2.ru и Правила сложения и умножения - student2.ru можно составить два размещения по одному элементу: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru и два размещения по два элемента: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru .

Из трех элементов Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru можно составить три размещения по одному элементу: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru ; шесть размещений по два элемента: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru и шесть размещений по три элемента: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru .

Все приведенные соединения отличаются друг от друга хотя бы одним элементом или порядком их расположения.

На практике чаше представляет интерес количество размещений, а не их конкретный вид. Число размещений из п элементов по т будем обозначать символом Правила сложения и умножения - student2.ru , где 0 ≤ m ≤ n[1].

Пример 1.3.1. В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами это можно сделать, если ни одна страница газеты не должна содержать более одной фотографии?

Решение. Первую фотографию можно поместить на любую из 12 страниц, т. е. 12 способами, вторую – на любую из оставшихся 11 страниц, т. е. 11 способами. Для размещения третьей фотографии имеется 10 способов, для последней – 9 способов. По правилу умножения четыре фотографии можно разместить на 12 страницах 12 · 11 · 10 · 9 = 11 880 способами.

Найденное число размещений четырех фотографий на 12 страницах газеты – это число. Правила сложения и умножения - student2.ru . Действительно, для размещения фотографий следует отобрать 4 различных страницы газеты из 12 имеющихся. Затем необходимо отобранные страницы упорядочить, не обращая внимания на их номера, т. е. определить, на какую страницу поместить первую фотографию, на какую – вторую и т. д.

Полученная упорядоченная совокупность страниц является размещением из 12 элементов по 4, а число Правила сложения и умножения - student2.ru таких размещений является ответом.

Таким образом, Правила сложения и умножения - student2.ru = 11 880.

Ответ: 11 880.

Число размещений из n элементов по m в каждом вычисляется по формуле[2]

Правила сложения и умножения - student2.ru = Правила сложения и умножения - student2.ru . (1.3.1)

Факториал.Произведение n натуральных чисел от Правила сложения и умножения - student2.ru до n обозначается сокращенно n!, то есть 1 · 2 · 3 · 4 · … · (n – 1) · n = n! (читается n факториал).

Например, 5! = 1 · 2 · 3 · 4 · 5 = 120. По определению 0! = 1.

Используя понятие факториала, формулу ( Правила сложения и умножения - student2.ru .3.1) можно представить следующим образом:

Правила сложения и умножения - student2.ru = Правила сложения и умножения - student2.ru , (1.3.2)

где 0 ≤ m ≤ n.

Очевидно, что Правила сложения и умножения - student2.ru (при m = 1) и Правила сложения и умножения - student2.ru (при m = 0).

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

Решение.Так как в любом числе важную роль играет входящих в него цифр, то для ответа на вопрос, очевидно, следует определить число размещений из 10 цифр по 4:

Правила сложения и умножения - student2.ru = Правила сложения и умножения - student2.ru .

Не все последовательности из 4 цифр собой четырехзначное число, поскольку среди них есть и те, у которых на 1-м месте находится 0. Найдем число таких последовательностей.

Так как у рассматриваемых последовательностей на 1-м месте уже стоит 0, то следует выбрать еще 3 цифры из оставшихся 9. Найдем число размещений из 9 по 3: Правила сложения и умножения - student2.ru =7 · 8 · 9 = 504. Таким образом, искомое число четырехзначных чисел равно разности Правила сложения и умножения - student2.ruПравила сложения и умножения - student2.ru .

Ответ: 4 536.

Пример 1.3.3. Расписание одного дня состоит из 6 уроков. Определить число вариантов расписания при выборе из 12 предметов.

Решение. Каждый вариант расписания представляет собой набор 6 дисциплин из 12 вариантов, которые отличаются составом дисциплин, порядком их следования (или и тем, и другим), т. е. является размещением из 12 элементов по 6. Число вариантов расписаний вычисляется по формуле (1.3.2)

Правила сложения и умножения - student2.ru

Ответ: 665 280.

Перестановки

Рассмотрим частный случай, когда m = n. Соответствующие этому случаю размещения называют перестановками.

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

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

При m = n получаем Правила сложения и умножения - student2.ru

Число перестановок из одного элемента равно Правила сложения и умножения - student2.ru .

Число перестановок из двух элементов Правила сложения и умножения - student2.ru и Правила сложения и умножения - student2.ru равно двум: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru .

Число перестановок из трех элементов Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru равно шести: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru .

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

Pn = 1 · 2 · 3 · … · (n – 1) · n = n! (1.4.1)

Решение задачи о квартете

Четыре горе-музыканта из басни И. А. Крылова долго пересаживались с места на место. В ходе этого «творческого поиска» Осел внес предложение: «Мы, верно, уж поладим, коль рядом сядем». Определим число возможных перестановок. Здесь n = 4, поэтому способов «усесться чинно в ряд» имеется P4= 4! = 1 · 2 · 3 · 4 = 24.

Для решения некоторых задач приходится применять идею перестановок с поправками. Предположим, что главным влияющим на качество игры фактором являются соседи каждого музыканта (не важно, кто из них справа, а кто слева). При таком условии перестановка «Мартышка, Осел, Козел, Мишка» эквивалентна зеркально-симметричной «Мишка, Козел, Осел, Мартышка». Понятно, что в этом случае все P4 вариантов разбиваются на пары равнозначных перестановок. Если из каждой пары оставить по одной перестановке, то общее число различающихся вариантов будет Правила сложения и умножения - student2.ru .

Предположим, что музыканты сели не в ряд, а по кругу. В этом случае в каждом из вариантов пронумеруем всех участников по часовой стрелке, начиная, например с Мартышки. В различных перестановках каждый музыкант, конечно, должен иметь разные номера. Только у Мартышки будет постоянный номер Правила сложения и умножения - student2.ru . Значит, осталось пронумеровать различными способами только троих. Поэтому здесь число возможных перестановок P3 = 3! = 6.

Пример 1.4.1.Порядок выступления 8 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т. е. является перестановкой из 8 элементов. Их число определяется по формуле (1.4.1)

P8 = 8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40 320.

Ответ: 40 320.

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

Решение. Решим задачу двумя способами.

Способ 1. Будем считать выделенные книги за книгу. Тогда для шести книг существует P6 = 6! = 720 перестановок. Однако пять определенных книг можно переставить между собой P5 = 5! = 120 способами. По правилу умножения имеем P6 · P5 = 720 · 120 = 84 400.

Способ 2. Возможны следующие случаи: первая из пяти книг стоит на 1-м месте, тогда пятая стоит на 5-м месте; первая книга стоит на 2-м месте, а пятая стоит на 6-м, первая стоит на 6-м месте, тогда пятая стоит на последнем 10-м месте. Число таких случаев равно шести. Сами книги могут быть переставлены P5 = 5! = 120 способами. По правилу умножения выделенные шесть книг можно расставить 6 · P5 = 720 способами. Оставшиеся пять книг можно переставить P5 = 5! = 120 способами. Воспользовавшись снова правилом умножения, приходим к тому же результату, который был получен при первом способе решения: P5 · 6 · P5 = P5 · P6 = 120 · 720 = 86 400.

Ответ: 86 400.

Сочетания

В некоторых задачах по комбинаторике не имеет значения порядок расположения объектов в той или иной совокупности. Важно лишь то, какие именно элементы ее составляют.

Если два различных размещения состоят из одинаковых элементов некоторого множества, то они обязательно отличаются порядком входящих в них элементов. Иногда возникает необходимость не учитывать порядок элементов, входящих в размещение. В этом случае все m!размещений, которые состоят из одних и тех же m элементов, считаются неразличимыми.

Предположим, что из чисел 3, 5, 7 необходимо составить различные произведения двух чисел. Таких произведений три, а именно: 3 · 5 = 15; 3 · 7 = 21; 5 · 7 = 35. Произведения вида 3 · 5 и 5 · 3 совпадают, так как положение сомножителей, входящих в произведение, не учитывается. Если требуется из указанных цифр составить двузначные числа, то таких чисел уже шесть. Запишем эти числа: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru . В этом случае был учтен порядок цифр.

Сочетаниямииз n элементов по m в каждом называют такие соединения, из которых каждое содержит m элементов, взятых из числа данных n элементов, и которые отличаются друг от друга только составом элементов.

Из одного элемента можно составить лишь одно сочетание.

Из двух элементов Правила сложения и умножения - student2.ru и Правила сложения и умножения - student2.ru можно составить два сочетания по одному элементу: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru и лишь одно сочетание по два элемента: Правила сложения и умножения - student2.ru .

Из трех элементов Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru можно составить три сочетания по одному элементу: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , три сочетания по два элемента: Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru , Правила сложения и умножения - student2.ru и лишь одно сочетание по три элемента: Правила сложения и умножения - student2.ru .

Все приведенные сочетания в каждом примере отличаются друг от друга хотя бы одним элементом.

Число сочетаний из n элементов по m обозначается символом: Правила сложения и умножения - student2.ru и вычисляется по формулам (1.5.1) и (1.5.2):

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru , 0 ≤ m ≤ n; (1.5.1)

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru , 0 ≤ m ≤ n. (1.5.2)

Свойства сочетаний

1. Правила сложения и умножения - student2.ru/

2. Правила сложения и умножения - student2.ru.

3. Правила сложения и умножения - student2.ru.

4. Правила сложения и умножения - student2.ru.

5. Правила сложения и умножения - student2.ru –рекуррентная формула, где 0 < m < n.

Пример 1.5.1. Необходимо выбрать в подарок 3 из 10 имеющихся различных книг. Сколькими способами это можно сделать?

Решение. Из смысла задачи следует, что порядок выбора книг не играет роли. Здесь важен их состав. Число возможных способов выбора трех книг в подарок из 10 имеющихся определяется по формуле (1.5.1)

Правила сложения и умножения - student2.ru .

Ответ: 120.

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

Решение. Каждая партия играется двумя участниками из 15 и отличается от других только составом пар участников, т.е. представляет собой сочетание из 15 элементов по 2. Их число находим по формуле (1.5.1)

Правила сложения и умножения - student2.ru .

Ответ: 105.

Пример 1.5.3. Имеется Правила сложения и умножения - student2.ru белых и Правила сложения и умножения - student2.ru красных шаров. Сколькими способами можно выбрать Правила сложения и умножения - student2.ru шаров так, чтобы среди них были Правила сложения и умножения - student2.ru красных?

Решение. Среди отобранных шаров 4 белых и 3 красных. Белые шары можно выбрать Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru способами. Красные шары можно выбрать Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru способами. Тогда по правилу произведения искомое число способов равно Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru .

Ответ: 2 100.

Пример 1. 5. 4. Сколько существует вариантов опроса 12 студентов на одном занятии по английскому языку, если ни один из них не будет подвергнут опросу дважды и на занятии может быть опрошено любое количество учащихся, причем порядок, в котором опрашиваются студенты, безразличен?

Решение. Преподаватель может не опросить ни одного из 12 студентов, что является одним из вариантов. Этому случаю соответствует Правила сложения и умножения - student2.ru . Преподаватель может опросить только одного из студентов. Таких вариантов Правила сложения и умножения - student2.ru . Если преподаватель будет опрашивать двух студентов, то число вариантов опроса равно Правила сложения и умножения - student2.ru . Для опроса трех студентов существует Правила сложения и умножения - student2.ru вариантов и т. д. Наконец, могут быть опрошены все студенты данной подгруппы. Число вариантов в этом случае равно Правила сложения и умножения - student2.ru . Тогда по правилу сложения всех возможных вариантов опроса равно

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru .

С другой стороны, для каждого из студентов существует две возможности: он будет опрошен или не опрошен на данном занятии. Другими словами, каждую из 12 операций, заключающихся в том, что каждый студент будет либо опрошен, либо не опрошен, можно выполнить по правилу умножения Правила сложения и умножения - student2.ru способами, что и следовало ожидать, так как согласно 4-му свойству сочетаний

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru .

Ответ: 212.

В размещении учитывается порядок входящих в них элементов, а в сочетаниях – не учитывается. При решении задач это не следует забывать.

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

Пусть имеется четыре различных элемента a, b, c, d (в достаточном количестве комплектов) и пусть требуется составить из этих четырех элементов по два элемента размещения с повторениями.

Если бы составлялись размещения без повторения, то все размещения должны были быть различными:

ab ba ac ca ad da cb bc bd db dc cd

Размещения с повторениями из этих четырех элементов будут следующие:

aa ab ba ac ca ad da cb bc bd bb db dc cc cd dd

Таким образом, размещение с повторениями из n элементов по m элементов (при 0 ≤ m ≤ n) может содержать любой элемент сколько угодно раз от 1 до m включительно, или не содержать его совсем, т. е. каждое размещение с повторениями из n элементов по m элементов может состоять не только из m различных элементов, но и из m каких угодно и как угодно повторяющихся элементов.

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

Число размещений с повторениями из n элементов по m обозначается символом Правила сложения и умножения - student2.ru .

Число размещений с повторениями определяется по формуле

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru (1.6.1)

Решение задачи о паспортах

Определим, сколько может быть паспортов советского образца с различными сериями и номерами, если зафиксировать римские цифры серии. Остаются две русские буквы и шесть арабских цифр. Рассмотрим цифры и буквы отдельно.

Буквы. В русском алфавите 33 буквы. Нам нужно выбрать любые две (они могут быть одинаковыми). Следовательно, имеет место размещение с повторениями, где n = 33 и m = 2.

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru 332 = 1 089.

Цифры. Здесь выбирается (с повторениями) m = 6 цифр из n = 10 возможных. Для этого есть Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ruспособов.

Поскольку каждую пару букв можно соединить с любой шестеркой цифр, то возможно существование Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru 332 · 106 = 1 089 000 000 паспортов, имеющих одни и те же римские цифры серии.

Ответ: 1 089 000 000.

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

Решение. Каждый гость из 4 может быть помещен в любую из 10 комнат, поэтому общее число размещений по формуле (1.6.1) равно

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru

Ответ: 10 000.

Перестановки с повторениями

Пусть имеется пять элементов, среди которых три одинаковых элемента: a, a, a, b, c. Перестановками из этих пяти элементов будут такие соединения, из которых каждое содержит все эти пять элементов и которые будут отличаться друг от друга лишь порядком расположения этих пяти элементов.

Очевидно, что элемент a будет входить в каждое соединение три раза.

Всевозможными перестановками из пяти элементов будут следующие:

Правила сложения и умножения - student2.ru

Эти перестановки будут перестановками с повторениями потому, что в каждое соединение один и тот же элемент Правила сложения и умножения - student2.ru входит три раза, т. е. столько раз, сколько раз он имелся среди данных пяти элементов.

Из приведенных перестановок видно, что их число равно 20. Если же все 5 элементов были бы различными, то число перестановок равнялось бы не 20, а числу 5! = 120.

Предположим теперь, что нам неизвестно число перестановок с повторениями из пяти данных элементов. Обозначим его X. И представим себе, что в группе a, a, a, b, c вместо трех одинаковых элементов a, a, a мы взяли три различных элемента a1, a2, a3. Тогда имеющееся число перестановок Правила сложения и умножения - student2.ru увеличится в 3! раз, т. е. во столько раз, сколько можно сделать перестановок из трех различных элементов. Тогда число всех перестановок будет равно 5! = X : (3!).

Отсюда Правила сложения и умножения - student2.ru.

Нетрудно получить и общую формулу для случая, когда имеется n групп, состоящих соответственно из k1, k2,…, kn неразличимых предметов. Если существует n элементов: a, b, …, c среди которых элемент a повторяется k1 раз, элемент b повторяется k2 раз и т. д., элемент c повторяется kn раз, то число перестановок с повторениями выражается при помощи формулы

Правила сложения и умножения - student2.ru . (1.7.1)

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

Решение. Всего фигур 8, из них три фигуры по две и две – по одной. По формуле (1.7.1) число перестановок равно Правила сложения и умножения - student2.ru = 5 040.

Ответ: 5 040.

Пример 1.7.2.Сколько перестановок можно сделать из букв слова «математика»?

Решение. В слове две буквы «м», три буквы «а», две буквы «т», по одной букве «е», «и», «к». Всего 10 букв. По формуле (1.7.1) число перестановок равно

Правила сложения и умножения - student2.ru .

Ответ: 151 200.

Сочетания с повторениями

Пусть задано 5 различных элементов a, b, c, d, e (в достаточном количестве комплектов) и пусть требуется составить из этих пяти элементов по 3 элемента сочетания с повторениями.

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

Если бы сочетания составлялись без повторений, то они должны были быть различными:

abc abd abe acd ace ade bcd bce bde cde.

Сочетания же с повторениями по три элемента из заданных пяти элементов будут иметь вид:

aaa aab aac aad aae abb abc abd abe acb acd ace add ade aee bbb bbc bbd bbe bce bcd bce bdd bde bee ccc ccd cce cdd cde cee ddd dde dee eee

Таким образом, сочетания же с повторениями из n элементов по m элементов (при 0≤ m ≤ n) может содержать любой элемент сколько угодно раз от Правила сложения и умножения - student2.ru до m включительно, или не содержать его совсем, т. е. каждое сочетание из n элементов по m элементов может состоять не только из m различных элементов, но и из m каких угодно и как угодно повторяющихся элементов.

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

Число сочетаний с повторениями из n элементов по m будем обозначать символом Правила сложения и умножения - student2.ru .

Существует формула для вычисления числа сочетаний с повторениями:

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru . (1.8.1)

Здесь m может быть и больше n.

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

Решение. Число равновозможных заказов по формуле (1.8.1) равно

Правила сложения и умножения - student2.ru Правила сложения и умножения - student2.ru

Ответ: 220.

2. РЕШЕНИЕ ЗАДАЧ

Разные задачи

Лучший способ освоения комбинаторики – решение задач. Начинать естественно, надо с простейших. Именно о простых, типовых (и в тоже время важнейших) задачах и пойдет речь.

Пример 2.1.1. В студенческой группе Правила сложения и умножения - student2.ru человек. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 20 человек, его заместителем – любой из оставшихся 19, а профоргом – любой из 18 студентов, т. е. n1 = 20, n2 = 19, n3 = 18. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно

n1· n2 · n3 = 20 · 19 · 18 = 6 840 способов.

Ответ:6 840.

Пример 2.1.2. Четыре юноши и четыре девушки садятся на 8 расположенных подряд стульев, причем юноши садятся на места с четными номерами, а девушки – на места с нечетными номерами. Сколькими способами это можно сделать?

Решение.Первый юноша может сесть на любое из четырех четных мест, второй – на любое из оставшихся трех мест, третий – на любое из оставшихся двух мест. Последнему юноше предоставляется всего одна возможность. Согласно правилу произведения, юноши могут занять четыре места 4 · 3 · 2 · 1 = 24 способами. Столько же возможностей имеют и девушки.

Таким образом, согласно правилу произведения, юноши и девушки могут занять все стулья 24 · 24 = 576 способами.

Ответ: 576.

Пример 2.1.3.В ящике 250 изделий. Известно, что 100 из них – первого, 120 – второго, а остальные – третьего сорта. Сколько способов выбора извлечения из ящика одной детали первого или третьего сорта?

Решение. Деталь первого сорта может быть извлечена n1 = 100 способами, третьего сорта – n2 = 30.

По правилу суммы существует n1 + n2 = 100 + 30 + 130 способов извлечения одной детали первого или третьего сорта.

Ответ: 130.

Пример 2.1.4.В высшей лиге чемпионата страны по футболу 16 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

Решение. Число разных способов распределения медалей равно

Правила сложения и умножения - student2.ru .

Ответ: 3 360.

Примечание. Необходимо различать сочетания и размещения. Например, в группе – 25 студентов, Правила сложения и умножения - student2.ru из них вышли из аудитории на перерыв. Студенты стоят вместе и беседуют. Тогда порядок, в котором они стоят, – не существенен. Число всех возможных групп из 25 человек по Правила сложения и умножения - student2.ru в этом случае – сочетания. Если же студенты отправились на перерыве в буфет или в кассу за стипендией, то тогда существенно, в каком порядке они стоят, т. е. кто из них первый, второй и т.д. В этой ситуации при подсчете возможных групп из 25 человек по Правила сложения и умножения - student2.ru необходимо составлять размещения.

Пример 2.1.5. У туриста есть семь консервных банок с ухой. В походе он будет находиться девять дней; из них какие-то семь дней будет есть уху, а три дня будет питаться всухомятку. Сколько у туриста есть способов выбрать дни с горячим питанием?

Решение. Число способов равно Правила сложения и умножения - student2.ru . Используя формулу (1.5.1), находим:

Правила сложения и умножения - student2.ru

Ответ: 36.

Пример 2.1.6.В спортивной секции з

Наши рекомендации