Полный текст:
5. В библиотеке
имеется 5 различных учебников и 2 различных задачника по дискретной математике.
Сколькими способами студент может выбрать: а) учебник или задачник, б) учебник
и задачник?
Решение. Поскольку книгу из множества учебников можно выбрать
5 способами, а при каждом таком выборе книгу из множества задачников – 2
способами, то:
а)
по правилу суммы, число способов выбора учебника или задачника: ;
б)
по правилу произведения, число способов выбора пары «учебник; задачник»: .
************************************************************************
15. Из пункта в пункт ведут три
дороги, из пункта в пункт – пять дорог. Найти
число различных маршрутов поездки из пункта в пункт .
Решение.
Число различных маршрутов из пункта в пункт : . Независимо от выбора каждого из таких маршрутов, число
дальнейших маршрутов из пункта в пункт : . Поэтому по правилу произведения число различных маршрутов
поездки из в :
.
************************************************************************.
25. В выражении различным
образом расставляют две круглые скобки. Найти число вариантов расстановки скобок.
Решение. Скобка (левая или правая) может находиться на одной
из шести позиций: перед первой цифрой, перед второй, … , перед пятой, после
пятой. Очевидно, каждому варианту расстановки скобок однозначно отвечают два
разных номера из шести позиций около цифр: на позиции с меньшим номером –
открывающаяся скобка, на позиции с большим – закрывающаяся. Наоборот, двум
таким разным номерам отвечает единственный корректный вариант расстановки
скобок. Поэтому искомое число вариантов равно числу комбинаций без повторений
из шести номеров по 2:
.
Ответ. 15 вариантов.
************************************************************************
35. Найти
число восьмизначных чисел с различными цифрами, кратных 5.
Решение. Любое восьмизначное
число, кратное 5, можно однозначно построить, выполнив следующие действия:
1) выбор цифры старшего
разряда (любая цифра, кроме нуля) – 9 способов;
2) выбор цифры младшего
разряда (если число кратное 5, то это или 0, или 5) – 2 способа;
3) в каждом из остальных
шести разрядов может находиться любая из 10 цифр, среди которых могут быть
одинаковые. Поэтому число способов выполнения данного действия равно числу
размещений с повторениями из 10 цифр по 6:
.
Из сказанного видно, что
выбор какого-то варианта определенного действия никак не влияет на число
вариантов остальных действий. Поэтому, согласно правилу произведения в терминах
действий, искомое количество нужных чисел
миллионов.
Ответ. 18 миллионов.
************************************************************************
45. Студенту
необходимо сдать четыре экзамена на протяжении восьми дней. Сколькими способами
это можно сделать, если в день разрешено сдавать не более одного экзамена?
Решение. Упорядочим сдаваемые
экзамены любым фиксированным способом (по сложности, или важности, или
алфавитному названию предмета и т.п.): первый, второй, третий, четвертый. Пусть
номер дня, в который
будет сдаваться й экзамен. Очевидно, все натуральные числа от 1
до 8, причем среди них нету двух одинаковых. Поскольку порядок очередности
сдачи играет роль (одно дело, например, сдавать экзамены от самого простого к
самому сложному, и совсем другое – в обратном порядке), то искомое число
способов равно числу размещений без повторений из 8 номеров дней по 4:
.
Ответ. 1680 способов.
************************************************************************
55. Имеется ячеек, в первой
из которых лежит предметов, во
второй – предметов, …, в
m-ой – предметов.
Сколькими способами можно вынуть по предметов из
каждой ячейки?
Решение. Для той ячейки (), в которой находится предметов, число
способов изъятия предметов равно
(независимо от изъятия предметов из остальных ячеек) числу комбинаций без
повторений из элементов по :
.
Поэтому
по правилу произведения в терминах действий число способов изъятия по предметов из каждой
ячейки
Ответ. .
************************************************************************
65. Записать
разложение по формуле бинома:
а) ; б) ; в) ; г) .
Решение.
а)
б)
в)
г)
*****************************************************************************
75. Доказать, что число делится на 100.
Доказательство. Поскольку,
используя бином Ньютона, получаем
а последнее число в приведенной цепочке равенств делится на
100 (так как является произведением 100
на натуральное число), то
исходное число также делится на 100, что и требовалось доказать.
************************************************************************
85. Доказать
тождества:
а) , ; б) ; в) .
Доказательство.
а)
;
б)
;
в)
************************************************************************
95. Найти число всех слов длины в n-буквенном алфавите , все буквы в которых различны.
Решение. Поскольку порядок букв
в слове важен, речь идет о количестве слов как упорядоченных множеств. В этих
множествах (словах) все элементы (буквы) по условию различны. Поэтому искомое
число – число размещений без повторений из букв по (в этом случае должно
быть ):
.
************************************************************************
105. Пять новых студентов
курса, которые перевелись из других вузов, надо распределить по трем группам.
Сколькими способами это можно сделать, если в каждую группу надо направить хотя
бы одного студента?
Решение.
Пусть студенты упорядочены по списку с номерами от первого до пятого. Тогда
каждому возможному распределению этих студентов по группам соответствует упорядоченная пятерка из номеров групп 1,2,3;
некоторые из них при этом будут повторяться. Поэтому число всех возможных распределений
равно числу размещений с повторениями из трех цифр по 5: .
Из
этих всех способов надо исключить те, при которых все пятеро студентов попадают
максимум в две группы (первую и вторую, первую и третью, вторую и третью). Для
каждого из трех последних вариантов распределения студентов по двум группам
число способов распределения . Но в сумме трех таких чисел (96) каждое число способов, при
которых все студенты попадают в одну группу, учитывается дважды – по одному
разу для каждой из двух пар групп, содержащих фиксированную. Поэтому число
способов, при которых студенты попадают максимум в две группы, на самом деле
равно 93-3=93, а искомое число способов – 243-93=150.
Ответ. 150 способов.
************************************************************************
115. Сколькими способами
можно разложить 20 одинаковых предметов по 5 неразличимым ящикам так, чтобы
а)
оказалось не более двух пустых ящиков;
б) в
каждом ящике оказалось не менее двух предметов;
в) в
каждом ящике оказалось не менее одного, но не более пяти предметов?
Решение. а) пусть число предметов в первом, втором,…, пятом ящиках. Возможны
варианты:
1) все 5 ящиков непустые: число способов
такого разложения равно числу положительных решений в целых числах уравнения
.
Пусть , (все ящики –
непустые). Тогда искомое число – число неотрицательных решений в целых числах
уравнения
,
или,
что то же самое,
.
Искомое число – число комбинаций с повторениями из пяти
элементов (номеров ящиков) по 15:
. (1)
2) Пусть теперь 4 первые ящика непустые:
число способов такого разложения равно числу положительных решений в целых
числах уравнения
.
Пусть , (все ящики –
непустые). Тогда искомое число – число неотрицательных решений в целых числах
уравнения
,
или,
что то же самое,
.
Искомое число – число комбинаций с повторениями из четырех
элементов (номеров ящиков) по 16:
.
Но
поскольку пустой ящик из пяти можно указать пятью способами, то нужное для
общего случая 4 непустых ящиков число
. (2)
3) Пусть теперь 3 первые ящика непустые:
число способов такого разложения равно числу положительных решений в целых
числах уравнения
.
Пусть , (все ящики –
непустые). Тогда искомое число – число неотрицательных решений в целых числах
уравнения
,
или,
что то же самое,
.
Искомое число – число комбинаций с повторениями из трех
элементов (номеров ящиков) по 17:
Но поскольку два пустых ящика из пяти можно указать десятью
способами, то нужное для общего случая 3 непустых ящиков число
. (3)
Сумма чисел (1)-(3) и дает нужный ответ:
3876+4845+1710=10431 способ.
б) Пусть , (все ящики содержат не
менее двух предметов). Тогда искомое число – число неотрицательных решений в
целых числах уравнения
,
или,
что то же самое,
.
Искомое число – число комбинаций с повторениями из пяти
элементов (номеров ящиков) по 10:
.
в) пусть ; тогда при размещение предметов
будет удовлетворять условие задачи. Подставляя в исходное уравнение, получаем:
,
откуда . Число неотрицательных решений такого уравнения
Однако из этох способов следует исключить те, при которых хоть
одно равно пяти (при этом
остальные равны нулю, и таких способов ровно 5). Поэтому искомое число
способов
126-5=121.