Решение

Применяя формулы для числа перестановок и числа размещений, запишем соотношение в виде .

После сокращения получим , , , . Поскольку число натуральное, то смысл имеет только значение .

 

4.2. Сочетания и их свойства

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

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

Число сочетаний обозначается символом , где – первая буква от английского слова combination – сочетания.

Пример 1. Для участия в научной конференции требуется направить четверых сотрудников из 32 сотрудников отдела. Сколько существует вариантов выбора представителей?

Решение

Поскольку для выбора представителей важен только состав участников, но не важно, в каком порядке происходило их выдвижение, то количество всевозможных вариантов равно числу сочетаний из 32 по 4:

.

Пример 2. Решить неравенство .

Решение

В силу определения сочетаний значениями переменной могут быть только целые числа от 1 до 10. Используя формулу сочетаний, запишем неравенство в виде .

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

Число обладает рядом свойств. Укажем без доказательства некоторые из них:

1) , в частности ;

2) ;

3) .

Доказательства перечисленных свойств можно получить непосредственно из определения сочетаний.

 

4.3. Выборки с повторением

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

Пусть дано множество, состоящее из различных элементов . Зафиксируем некоторое натуральное число и вычислим, сколько существует способов составить группы, содержащие элементов из данных , причем каждый из элементов может быть выбран более одного раза. Первым элементом может быть любой из элементов множества, т. е. для выбора первого элемента существует способов. Поскольку каждый элемент можно выбирать неоднократно, то второй элемент можно выбрать также способами. Рассуждая подобным образом, получим, что каждый из элементов можно выбрать способами. Согласно комбинаторному принципу умножения получим, что общее число выборок по элементов из данных равно . Указанная выборка называется повторной. Заметим, что ограничение, справедливое для бесповторных выборок, , не работает в случае повторяющихся элементов. Для повторных выборок число может быть как больше, так и меньше либо равным .

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

 

 

Рис. 40

Пример 1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 5, 8 при условии, что цифры в числе могут повторяться?

Решение

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

 

Вопросы и задачи для самостоятельного решения

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

2. Сколько четных чисел можно составить из цифр 1, 2, 5, 4, 0?

3. Сколько существует вариантов ответа на тест из 10 вопросов, если на каждый вопрос требуется ответить «да» или «нет»?

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

5. Сколько существует различных шестизначных телефонных номеров, которые не начинаются с цифр 0, 1, 9, 8?

6. Вычислите:

а) ; б) ; в) ; г) .

7. Вычислите:

а) ; б) ; в) ; г) .

8. Вычислите:

а) ; б) ; в) ; г) .

9. Вычислите:

а) ; б) ; в) ; г) .

10. Проверьте равенства:

а) ; б) .

11. Решите уравнения:

а) ; в) ;

б) ; г) .

 

 

5. ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

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

Для успешного решения заданий необходимо выучить следующие разделы:

§ с 1-го по 6-е задание – разд. 1 «Элементы теории множеств»:

1-е задание – подразд. 1.1 «Основные понятия теории множеств. Способы задания множеств», 1.2 «Операции над множествами»;

2-е задание – подразд. 1.3 «Диаграммы Эйлера – Венна»;

3-е задание – подразд. 1.4 «Свойства операций над множествами»;

4-е задание – подразд. 1.5 «Декартовы произведения множеств»;

5-е задание – подразд. 1.6 «Бинарные отношения. Свойства бинарных отношений»;

6-е задание – подразд. 1.7 «Функции»;

§ с 7-го по 12-е задание – разд. 2 «Элементы математической логики»:

7–10-е задания – подразд. 2.2 «Высказывания. Логические операции и их основные свойства»;

11-е задание – подразд. 2.3 «Способы решения логических задач»;

12-е задание – подразд. 2.4 «Булевы функции. Свойства элементарных булевых функций», 2.5 «Дизъюнктивные и конъюнктивные нормальные формы булевых функций», 2.6 «Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы»;

§ с 13-го по 14-е задание – разд. 3 «Элементы теории графов»:

13-е задание – подразд. 3.1 «Основные понятия теории графов»;

14-е задание – подразд. 3.2 «Способы задания графов», 3.3 «Связность графов»;

§ 15-е задание – разд. 4 «Элементы комбинаторики»: подразд. 4.1 «Перестановки, размещения и их количество», 4.2 «Сочетания и их свойства».