Глава 1. А. В. Лебедев, Л. Н. Фадеева, 2018 isbn 9785600021495 1

• Название: А. В. Лебедев, Л. Н. Фадеева, 2018 isbn 9785600021495 1
• Дата: 17.09.2022
• Размер: 6.48 Mb.
• Имя файла: Глава 1.pdf
• Тип: Задача; #681261

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 1
Глава 1. Элементы комбинаторного анализа
Одной из основных задач комбинаторного анализа (комбинаторики) является подсчет числа элементов конечных множеств, заданных каким-либо описательным условием. Для этого разработаны различные формулы и правила.
§ 1.1. Основные правила комбинаторики
Пусть имеется k групп А
1
, А
2
, ..., А
k
, причем i-ая группа содержит n
i
элементов. Тогда справедливы следующие правила.
Правило умножения.
Общее число N способов, которыми можно выбрать по одному элементу из каждой группы и расставить их в определенном порядке (т.е. получить упорядоченную совокупность (a
1
, a
2
, ..., a
k
), где a
i
 A
i
), равно
k
n
n
n
N
2 1

Это правило распространяется и на ситуации, когда новые группы образуются в процессе выбора элементов, если численности этих групп не зависят от того, какие именно элементы были выбраны.
Правило сложения. Если k групп А
1
, А
2
, ..., А
k
не имеют общих элементов, то общее число способов, которыми можно осуществить выбор одного элемента или из A
1
, или из A
2
,
..., или из A
k
, равно
k
n
n
n
N




2 1
Задача 1. В группе 30 студентов. Необходимо выбрать старосту, заместителя старосты и профорга. Сколько существует способов это сделать?
Решение. Старостой может быть выбран любой из 30 студентов, заместителем – любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. n
1
=30, n
2
=29,
n
3
=28. По правилу умножения общее число N способов выбора старосты, его заместителя и профорга равно
24360 28 29 30 3
2 1





n
n
n
N
Задача 2. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?
Решение. Первое письмо имеет n
1
=2 альтернативы: либо его относит к адресату первый почтальон, либо второй. Для второго письма также есть n
2
=2 альтернативы и т.д., т.е.
n
1
=n
2
=…=n
10
=2. Следовательно, в силу правила умножения, общее число способов распределить письма между двумя почтальонами равно
1024 2
2 2
2 10
раз
10 10 2
1










n
n
n
N
Задача 3. В ящике 100 деталей, из них 30 – деталей 1-го сорта, 50 – 2-го, остальные –

3-го. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?
Решение. Деталь 1-го сорта может быть извлечена n
1
=30 способами, 2-го сорта – n
2
=50 способами. По правилу суммы существует N=n
1
+n
2
=30+50=80 способов извлечения одной детали 1-го или 2-го сорта.
§ 1.2. Размещения
Пусть имеется некоторая конечная совокупность элементов {a
1
, a
2
, ..., a
n
}, называемая
генеральной совокупностью, и n – объем этой совокупности. Пусть эксперимент состоит в том, что из генеральной совокупности последовательно выбирают k элементов и записывают их в порядке выбора.
Размещениями называются упорядоченные совокупности элементов (или записи о выборе элементов), отличающиеся друг от друга либо составом, либо порядком элементов.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 2
Возможны следующие ситуации.
1.2.1. Размещения без повторений
Пусть ранее выбранный элемент перед выбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без
возвращения, а его результат – размещением без повторений из n элементов по k.
Теорема 1. Число размещений без повторений из n элементов по k равно
1
)!
(
!
k
n
n
A
k
n


Доказательство. Очевидно, что первый элемент можно выбрать n
1
=n способами, и поскольку выбранный элемент не возвращается в генеральную совокупность, то следующий элемент выбирается из совокупности, объем которой на единицу меньше, то есть n
2
=n1, и т.д., так что n
k
=n–(k–1). Тогда по правилу умножения общее число способов равно
)!
(
!
))
1
(
)...(
1
(
k
n
n
k
n
n
n
N






Пример 1. Все размещения без повторений двух элементов из множества


c
b
a
,
,
:
,
,
,
,
,
cb
bc
ca
ac
ba
ab
В частном случае, когда выбираются все элементы генеральной совокупности, т.е. когда k=n, такие размещения без повторений оказываются перестановками.
Перестановками называются упорядоченные совокупности, отличающиеся друг от друга только порядком входящих в них элементов.
Как следует из теоремы 1, число перестановок из n элементов равно
P
n
=n!
Пример 2. Все перестановки множества


c
b
a
,
,
:
bca
cab
acb
cba
bac
abc
,
,
,
,
,
Задача 4. Расписание одного дня состоит из 5 различных уроков. Определить число вариантов расписания при выборе из 11 дисциплин.
Решение. Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования, поэтому
55440 11 10 9
8 7
!
6
!
11
)!
5 11
(
!
11 5
11









 A
N
Задача 5. Порядок выступления 7 участников конкурса определяется жребием.

Сколько различных вариантов жеребьевки при этом возможно?
Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 7 элементов. Их число равно
5040 7
6 5
4 3
2 1
!
7 7









P
1.2.2. Размещения с повторениями
Пусть ранее выбранный элемент перед выбором следующего возвращается в генеральную совокупность (при этом каждый раз делается запись о том, какой элемент был выбран). Такой выбор называется последовательным выбором с возвращением, а его результат – размещением с повторениями из n элементов по k.
Теорема 2. Число размещений с повторениями из n элементов по k равно
k
k
n
n
A 
Доказательство. Поскольку любой выбранный элемент перед выбором следующего возвращается в генеральную совокупность, то выбор на каждом шаге производится из
1
Напомним определение факториала: n!=12...n и 0!=1.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 3 совокупности объема n. Можно считать, что выбор производится из k групп и все группы состоят из одинакового числа элементов n
1
=n
2
=…=n
k
=n. Тогда, в силу правила умножения, число способов такого выбора равно N=n
k
Пример 3. Все размещения с повторениями двух элементов из множества


c
b
a
,
,
:
,
,
,
,
,
,
,
,
cc
cb
ca
bc
bb
ba
ac
ab
aa
Задача 6. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по всем номинациям установлены различные премии?
Решение. Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций как составом, так и их порядком. Так как каждый фильм может получить призы как по одной, так и по нескольким номинациям, то одни и те же фильмы могут повторяться. Поэтому число таких комбинаций равно числу размещений с повторениями из 10 элементов по 5:
100000 10 5
5 10


 А
N
§ 1.3. Сочетания
Сочетаниями называются неупорядоченные совокупности элементов, отличающиеся друг от друга только составом (без учета порядка).
1.3.1. Сочетания без повторений
Пусть из генеральной совокупности объема n берется сразу несколько элементов
(либо элементы берут последовательно, но порядок их появления не учитывается). В результате такого одновременного неупорядоченного выбора k элементов из генеральной совокупности объема n получаются комбинации, которые называются сочетаниями без
повторений из n элементов по k.
Теорема 3. Число сочетаний без повторений из n элементов по k равно
!
)!
(
!
k
k
n
n
С
k
n


Доказательство. Среди
k
n
A
размещений без повторений имеется по k! наборов каждого состава, представляющих собой всевозможные перестановки из k элементов этого состава. Если объединить наборы одинакового состава в группы, то каждой группе соответствует одно сочетание без повторений. В каждой группе будет k! размещений, а всего размещений
k
n
A
. Следовательно, число групп, а значит, и число сочетаний без повторений из
n по k равно
!
)!
(
!
!
k
k
n
n
k
A
C
k
n
k
n



Пример 4. Все сочетания без повторений двух элементов из множества


c
b
a
,
,
:
     
,
,
,
,
,
c
b
c
a
b
a
Отметим некоторые полезные свойства числа сочетаний без повторений:
;
2
;
;
;
1 2
1 0
1 1
1 0
k
n
k
k
n
n
n
n
n
n
n
k
n
k
n
k
n
k
n
n
k
n
n
n
n
C
P
A
C
C
C
C
C
C
C
C
C
C
C
















© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 4
Числа
k
n
C
называют также биномиальными коэффициентами, поскольку они участвуют в разложении бинома Ньютона:





n
k
k
n
k
k
n
n
b
a
C
b
a
0
)
(
Задача 7. В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми двумя участниками должна быть сыграна одна партия?
Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т.е. представляет собой сочетания без повторений из 16 элементов по 2. Поэтому их число равно
120 2
1 16 15
!
2
!
14
!
16 2
16





C
Задача 8. Садовник должен в течение трех дней посадить 6 деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?
Решение. Предположим, что садовник сажает деревья в ряд, и может принимать различные решения относительно того, после какого по счету дерева остановиться в первый день и после какого – во второй. Таким образом, можно представить себе, что деревья разделены двумя перегородками, каждая из которых может стоять на одном из 5 мест (между деревьями). Перегородки должны стоять там по одной, поскольку иначе в какой-то день не будет посажено ни одного дерева. Таким образом, надо выбрать 2 элемента из 5 (без повторений). Следовательно, число способов
10 2
5

C
1.3.2. Сочетания с повторениями
Пусть из генеральной совокупности объема n выбирается k элементов, один за другим, причем каждый выбранный элемент перед выбором следующего возвращается в генеральную совокупность. При этом ведется запись, какие именно элементы появились и сколько раз, однако порядок их появления не учитывается. Получившиеся записи называются сочетаниями с повторениями из n элементов по k.
Теорема 4. Число сочетаний с повторениями из n элементов по k равно
k
k
n
k
n
C
C
1



Доказательство. Результатом выбора k элементов из n с возвращением и без учета порядка является запись о том, сколько раз выбирали каждый из n элементов генеральной совокупности. А именно, получаем набор вида (k
1
, k
2
, ..., k
n
), где число k
i показывает, сколько раз был выбран i-ый элемент (если его ни разу не выбирали, то k
i
=0). При этом все k
i
неотрицательны и их сумма равна k. Требуется найти число наборов, удовлетворяющих этим условиям.
Представим набор (k
1
, k
2
, ..., k
n
) в виде групп по k
1
, k
2
, ..., k
n
единиц, разделенных нулями (ноль ставится после каждой группы, кроме последней; если группа пуста, то ноль после нее ставится все равно). Например, (1,2,3) представляется в виде 10110111, (0,1,2,0,3,0) в виде 01011001110 и т.д.
Таким образом, получаются последовательности из n+k1 символов, где k единиц и
n1 нулей. И наоборот, каждой такой последовательности соответствует набор (k
1
,k
2
,...k
n
), удовлетворяющий нужным условиям. Для единиц нужно выбрать k мест из n+k1 имеющихся, остальные места заполняются нулями. Значит, число вариантов равно
k
k
n
C
1


Пример 5. Все сочетания с повторениями двух элементов из множества


c
b
a
,
,
:

          
,
,
,
,
,
,
,
,
,
,
,
c
c
c
b
b
b
c
a
b
a
a
a

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 5
Задача 9. В условиях задачи 6 определить, сколько существует вариантов распределения призов, если по всем номинациям установлены одинаковые призы?
Решение. Если по каждой номинации установлены одинаковые призы, то порядок фильмов в комбинации 5 призов значения не имеет, и число вариантов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое по формуле
2002 5
4 3
2 1
14 13 12 11 10 5
14 5
1 5
10 5
10














C
C
С
Задача 10. Сколько существует четырехзначных номеров
2
, сумма цифр которых равна
5?
Решение. Представим число 5 в виде суммы последовательных единиц, разделенных на группы перегородками (каждая группа в сумме образует очередную цифру числа).
Понятно, что таких перегородок понадобится 3. Мест для перегородок имеется 6 (до всех единиц, между ними и после). Каждое место может занимать одна или несколько перегородок (в последнем случае между ними нет единиц, и соответствующая сумма равна нулю). Рассмотрим эти места в качестве элементов множества. Таким образом, надо выбрать
3 элемента из 6 (с повторениями). Следовательно, искомое число номеров
56 3
2 1
6 7
8 3
8 3
6






 C
С
Другое решение заключается в том, что набор цифр любого четырехзначного номера, удовлетворяющего условиям задачи, можно рассматривать как набор чисел (k
1
, k
2
, k
3
, k
4
), где все числа неотрицательны и их сумма равна 5. По теореме 4 и ее доказательству, таких наборов всего
56
!
3
!
5
!
8 5
8 5
4


 C
C
Отметим, что соответствие между n-значными номерами и наборами из n чисел в таких задачах можно установить, только если заданная сумма цифр не превосходит 9
(поскольку в противном случае цифры не могут быть больше 9, а числа в наборе могут).
§ 1.4. Разбиение множества на группы
Пусть множество из n различных элементов разбивается на k групп так, что в первую группу попадают n
1
элементов, во вторую – n
2 элементов, в k-ую группу – n
k элементов, причем n
1
+n
2
+...+n
k
=n. Такую ситуацию называют разбиением множества на группы.
Теорема 5. Число разбиений n элементов на k групп, когда в первую группу попадают
n
1
элементов, во вторую – n
2
элементов, в k-ую группу – n
k
элементов, равно:
!
!...
!
!
)
,...,
,
(
2 1
2 1
k
k
n
n
n
n
n
n
n
n
N

Доказательство. В первую группу выберем любые n
1
элементов из n имеющихся первоначально, что можно сделать
1
n
n
С
способами. Вторую группу надо заполнить n
2
элементами из оставшихся nn
1 элементов.
Это можно сделать
2 1
n
n
n
С

различными способами.
Продолжая эту процедуру и используя правило умножения, получаем, что число способов разбиения n элементов на k групп так, что в первую группу попадают n
1
элементов, во вторую – n
2 элементов, в k-ую группу – n
k элементов,равно
!
!...
!
!
!
0
!
)!
(
)!
(
!
)!
(
)!
(
!
!
2 1
1 1
2 1
2 1
1 1
1 1
2 1
1
k
k
k
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
C
C
С
k
k


















Заметим, что порядок элементов при разбиении на группы не важен, а вот порядок групп (какая из них считается первой, какая – второй и т.д.) существенен.
2
Здесь и далее под n-значными номерами будем понимать наборы цифр длины n. Например, четырехзначные номера – это любые комбинации от 0000 до 9999.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 6
Пример 6. Перечислим разбиения множества из 4 элементов a, b, c, d на 2 группы по
2 элемента (6 штук):
[{a,b},{c,d}], [{a,c},{b,d}], [{a,d},{b,c}], [{c,d},{a,b}], [{b,d},{a,c}], [{b,c},{a,d}].
Задача 11. Сколькими способами можно разбить группу из 25 студентов на три подгруппы А, В и С по 6, 9 и 10 человек соответственно?
Решение. Здесь n=25, k=3, n
1
=6, n
2
=9, n
3
=10. По теореме 5, число разбиений равно
!
10
!
9
!
6
!
25
)
10
,
9
,
6
(
25

N
Задача 12. Сколько существует семизначных номеров, состоящих из цифр 4, 5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 – по 2 раза?
Решение. Каждый семизначный номер, удовлетворяющий условию задачи, отличается от другого только порядком следования цифр, при этом фактически все семь мест в этом числе делятся на три группы: на одни места ставится цифра «4», на другие места – цифра
«5», а на третьи места – цифра «6». Таким образом, множество состоит из 7 элементов (n=7), причем n
1
=3, n
2
=2, n
3
=2, и, следовательно, количество таких номеров равно
210
!
2
!
2
!
3
!
7
)
2
,
2
,
3
(
7


N
Задача 13. Слово «МАТЕМАТИКА» разрезали на буквы, перемешали и выбирают по одной, без возвращения. Сколько различных последовательностей может получиться?
Решение. Возможные последовательности отличаются друг от друга только порядком следования букв, при этом все множество из 10 мест разбивается на 6 групп: два места для
«М»; три места для «А», два места для «Т», по одному месту для «Е», «И», «К». Получаем
151200
!
1
!
1
!
1
!
2
!
3
!
2
!
10
)
1
,
1
,
1
,
2
,
3
,
2
(
10


N
Более понятное (а на самом деле, эквивалентное) решение заключается в следующем.
Если бы все 10 букв в исходном слове были различны, число их перестановок равнялось бы
10!. Но поскольку от перемены мест одинаковых букв последовательность не меняется, это число нужно еще поделить на числа перестановок букв «М», «А» и «Т», а именно 2!, 3! и 2! соответственно.
Подводя итоги главы, представим все полученные результаты в одной таблице.
Таблица 1.1.
Размещения
Сочетания
Без повторений
)!
(
!
k
n
n
A
k
n


!
)!
(
!
k
k
n
n
С
k
n


С повторениями
k
k
n
n
A 
k
k
n
k
n
C
C
1



Перестановки
Разбиения на группы
P
n
=n!
!
!...
!
!
)
,...,
,
(
2 1
2 1
k
k
n
n
n
n
n
n
n
n
N

При этом перестановки являются частным случаем размещений без повторений, а разбиения на группы – обобщением сочетаний без повторений.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 7
Задачи для самостоятельного решения

1. Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?
2. Доступ к файлу открывается, только если введен правильный пароль – определенный трехзначный номер
3

из нечетных цифр. Каково максимальное число возможных попыток угадать пароль?
3. Группу из 10 человек требуется разбить на две непустые подгруппы А и B. Сколькими способами это можно сделать?

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

6. Шесть студентов-переводников нужно распределить по трем группам. Сколькими способами это можно сделать?
7. Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

8. Сколько существует пятизначных номеров, в которых есть цифры 1 и 2?
9. Байт – это машинное слово, состоящее из восьми бит. Каждый бит равен либо 0, либо 1.

Сколько символов можно закодировать с помощью байта?
10. Автомобильный номер состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 30 букв и 10 цифр?

11. Сколько четырехзначных чисел, составленных из неповторяющихся нечетных цифр, содержат цифру 3?
12. Из цифр от 1 до 9 составляются всевозможные пятизначные числа, не содержащие одинаковых цифр. Определить количество чисел, в которых есть цифры 2, 4 и 5 одновременно.
13. Есть 3 билета в различные театры. Сколькими способами они могут быть распределены среди 25 студентов группы, если каждый студент может получить только один билет?

14. Сколькими способами можно расположить на полке 10 томов энциклопедии?
15. Сколькими способами можно расположить на полке 10 томов энциклопедии так, чтобы девятый и десятый тома не стояли рядом?
16. Шесть групп занимаются в шести расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?
17. Сколькими способами можно расставить группу из 10 студентов в очередь так, чтобы между двумя студентами, Артемом и Борисом, стояло два человека?
18. Из бригады в 14 врачей ежедневно в течении 7 дней назначают двух дежурных врачей.
Определить количество различных расписаний дежурства, если каждый врач дежурит ровно один раз в неделю.
19. Слово "ЭКОНОМИКА" разрезали на буквы, перемешали и выбирают их по одной, без возвращения. Сколько различных последовательностей букв может получиться?
20. Слово "МЕНЕДЖМЕНТ" разрезали на буквы, перемешали и выбирают их по одной, без возвращения. Сколько различных последовательностей букв может получиться?

21. В ящике 5 красных и 4 зеленых яблока. Сколькими способами можно выбрать три яблока из ящика?
22. Из ящика, в котором лежат 10 красных и 5 зеленых яблок, выбирают одно красное и два зеленых яблока. Сколькими способами это можно сделать?

23. Десять человек при встрече обмениваются рукопожатиями (каждый с каждым). Сколько всего рукопожатий будет сделано?
3
Напомним, что под n-значными номерами понимаются наборы цифр длины n.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 8
24. В группе из 25 студентов нужно выбрать старосту и 3 членов студенческого комитета.

Сколькими способами это можно сделать?
4 25. Акционерное собрание компании выбирает из 50 человек президента компании, председателя совета директоров и 10 членов совета директоров. Сколькими способами это можно сделать?
26. Из фирмы, в которой работают 10 человек, 5 сотрудников должны уехать в командировку. Сколько может быть составов этой группы, если директор фирмы, его заместитель и главный бухгалтер одновременно уезжать не должны?
27. В телевизионной студии работают 3 режиссера, 4 звукорежиссера, 5 операторов, 7 корреспондентов и 2 музыкальных редактора. Сколькими способами можно составить съемочную группу, состоящую из одного режиссера, двух операторов, одного звукорежиссера и двух корреспондентов?
28. Студенческая группа из 27 человек, пишет контрольную работу из трех вариантов (по 9 человек в каждом). Сколькими способами можно выбрать 5 человек из группы так, чтобы среди них оказались писавшие все три варианта?
29. На группу из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами они могут быть распределены (не более одного билета в руки)?
30. Имеются 7 билетов: 3 в один театр и 4 — в другой. Сколькими способами они могут быть распределены между студентами группы из 25 человек?
31. Садовник должен в течение трех дней посадить 10 одинаковых деревьев. Сколькими способами он может распределить по дням работу, если будет сажать не менее одного дерева в день?
32. Инвестор намеревается купить 12 акций 4 компаний (не менее чем по одной акции каждой). Сколькими способами он может распределить свой капитал?
33. Инвестор намеревается купить 11 акций 5 компаний (причем от покупки акций одной или более из этих компаний он может отказаться). Сколькими способами он может распределить свой капитал?

34. Сколько существует трехзначных номеров, сумма цифр которых равна 6?
35. Сколько существует четырехзначных номеров, сумма цифр которых равна 9?
36. Группу из 10 человек требуется разбить на две подгруппы так, чтобы в первой группе было 6 человек, а во второй – 4 человека. Сколькими способами это можно сделать?
37. Группу из 16 человек требуется разбить на 3 подгруппы, в первой из которых должно быть 5 человек, во второй — 7 человек, в третьей — 4 человека. Сколькими способами это можно сделать?
38. Студенческую группу из 24 человек (12 девушек и 12 юношей) разбивают на две равные подгруппы так, чтобы в каждой подгруппе юношей и девушек было поровну. Сколькими способами это можно сделать?
39. Семь яблок и три апельсина надо положить в два пакета так, чтобы в каждом пакете был хотя бы один апельсин и чтобы количество фруктов в них было одинаковым. Сколькими способами это можно сделать? Пакеты считаются различными.
40. Лифт, в котором находится 9 пассажиров, может останавливаться на 10 этажах. На одном этаже выходят 2 человека, на другом – 3, и еще на одном – 4. Сколькими способами пассажиры могут выйти из лифта?
41. Восемь авторов должны написать книгу из 16 глав. Сколькими способами можно распределить материал между авторами, если два человека взялись написать по три главы, четыре – по две и два – по одной главе книги?
42. Сколькими способами можно расположить на шахматной доске (88) две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находится с ней на одной горизонтали или на одной вертикали шахматной доски)
4
В задачах 2427 предполагается, что совмещение разных должностей одним человеком не допускается.

© А.В.Лебедев, Л.Н.Фадеева, 2018
ISBN 978-5-600-02149-5 9
43. Сколько существует двузначных чисел
5

, кратных либо 2, либо 5, либо тому и другому числу одновременно?
44. Десяти ученикам выданы два варианта контрольной работы. Сколькими способами можно посадить учеников в два ряда (по 5 человек друг за другом), чтобы у сидящих рядом не было одинаковых вариантов, а у сидящих друг за другом был один и тот же вариант?
45. Три машины № 1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов и если в каждый магазин направляется ровно одна машина? Сколько вариантов маршрута (порядка доставки товара в магазины) возможно, если решено использовать только машину № 1?
5
В этой задаче имеются в виду обычные двузначные числа, от 10 до 99.