Тексты лекций / Текст лекции 2

1.18.В студенческой группе учатся 9 девушек и 11 юношей. Сколькими способами можно сформировать командуиз 7человек для участияв соревнованиях,если внее должно войти не менее 3 юношей?

1.19.а) В классе учатся 18 человек. Сколькими способами можно составить график дежурств по классу на 6 дней так, чтобы каждый день дежурили по 3 человека, причем никто не дежурил дважды?

б) В классе учатся 18 человек. Сколькими способами можно разбить его учеников на 6 равных по численности групп?

1.20.а) Сколькими способами можно разложить 8 одинаковых шаров по 3 занумерованным коробкам так, чтобы ни одна из коробок не осталась пустой?

б) Сколькими способами можно разложить 8 одинаковых шаров по 3 занумерованным коробкам?

1.21.а)Сколькимиспособамиможнопредставитьчисло ввидеупорядоченнойсуммыположительных целых чисел?

б) Сколькими способами можно представить число в виде упорядоченной суммы неотрицательных целых чисел?

1.23.а) Сколько существует рефлексивных бинарных соотношений на множестве из элементов?

б) Сколько существует симметричных бинарных соотношений на множестве из элементов?

в) Сколько существует антисимметричных бинарных соотношений на множестве из элементов?

1.24.Используя бином Ньютона, доказать тождества:

1.25. Найти такое число , при котором число сочетаний из элементов по наиболь-

Ответы и указания к упражнениям

1.4. 200. Решение. Чтобы обмен осуществился, Олег должен выбрать одну из своих книг, а Иван - одну из своих. Пара выбранныхими книг определяет обмен,поэтому обмен можно отождествить с выборкой объема 2, первый элемент которой - книга Олега, второй - книга Ивана. Число способов обмена равно количеству таких выборок. Произвольную выборку можносоставитьвдвашага:напервом выбратьоднуиз десятикнигОлега,навтором -одну из двадцати книг Ивана. Следовательно, по правилу произведения количество выборок, а значит и число способов обмена равно 10 20 = 200. 1.5. 2048. Решение. Будем писать число справа налево, т.е. на первом шаге выбирать последнюю цифру числа, на втором -

11

Тема 2 «Элементы комбинаторики» Олейник Т.А., 2020

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

число пятизначных чисел, в десятичной записи которых нет цифры 5). 1.9. а) 15120; б) 9 . Решение. а) Каждому размещению шаров по коробкам сопоставим упорядоченную выборку, элементы которой - номера коробок: первый элемент выборки - номер коробки, в которуюпомещенпервыйшар,второйэлемент-номеркоробки,вкоторуюпомещенвторой шар, и т.д. В этих упорядоченных выборках элементы не повторяются (так как по условию задачивкаждуюкоробкуможноположитьнеболееодногошара),следовательно,мыимеем дело с размещениями из 9 элементов по 5. Число таких размещений найдем по формуле

выборку, элементами которой являются номера коробок: первый элемент выборки - номер коробки, в которую помещен первый шар, второй элемент - номер коробки, в которую помещенвторой шар, и т.д.В этихвыборкахэлементы могутповторяться(таккак поусловию задачи в каждую коробку можно положить сразу несколько шаров), следовательно, мы имеем дело с размещениями с повторениями из 9 элементов по 5. Число таких размещений найдем по формуле = 9 . 1.10. Каждое шестибуквенное слово - перестановка из 6 элементов, следовательно, разных шестибуквенных слов столько, сколько перестановок из

ретаряитрехчленовсчетнойкомиссииможноосуществитьзатришага.Напервомвыбрать председателя,навтором-секретаря,натретьем-членовсчетнойкомиссии.Напервомшаге имеем 50 возможностей, на втором - 49, на третьем - возможностей столько же, сколько неупорядоченных выборок без повторений трех человек из 48, т.е. . Следовательно, по правилу произведения выбор председателя, секретаря и трех членов счетной комиссии можно осуществить 50 49 = 42375200 способами.

12