Занятие №4. Элементы комбинаторики

Занятие №4. Элементы комбинаторики

1.  Правила суммы и произведения.

2.  Соединения без повторений.

3.  Соединения с повторениями.

4.  Бином Ньютона

Правило суммы. Если элемент можно выбрать различными способами и независимо от него элемент можно выбрать различными способами, то выбрать все различные комбинации элементов «A или B» можно способами.

Ø  Пример 1. Студентам на предстоящий зачет дается на выбор 5 тем по математическому анализу и 7 по теории вероятностей. Сколькими способами можно выбрать тему по математическому анализу или по теории вероятностей? Решение: Множества не пересекаются, значит можно применить правило суммы: способов.

Правило произведения. Если элемент можно выбрать различными способами и независимо от него элемент можно выбрать различными способами, то все различные комбинации элементов «A и B» можно выбрать способами.

Ø  Пример 2. На первой полке стоит 10 книг, а на второй 5. Сколькими способами можно взять книги с обеих полок? Решение: По правилу произведения: способов.

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

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

Это число равно произведению всех целых чисел от 1 до включительно:

Символ обозначает факториал числа , т. е. произведение всех натуральных чисел от 1 до . Считают, что .

Ø  Пример 3. Найти число перестановок из трех элементов а, Ь, с. Имеем . Действительно, имеем 6 перестановок: 1)abc; 2)acb; 3)bac; 4)bca; 5) cab; 6)cba.

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

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

Ø  Пример 5. Найти число размещений из четырех элементов abed по два. Имеем: .

Ø  Пример 6. В президиум собрания избраны восемь человек. Сколькими способами они могут распределить между собой обязанности председателя, секретаря и счетчика? Искомое число есть число размещений из 8 элементов по 3:

.

Замечание. Перестановки можно считать частным случаем размещений (именно размещениями из элементов по ).

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

.

Ø  Пример 7. Найти все сочетания из пяти элементов abсde по три. Имеем:

.

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

счетчика одинаковы, то в отличие от примера 4 мы имеем не размещения, а сочетания. Искомое число:

.

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

.

Ø  Пример 9. Найти число различных перестановок с повторяющимися элементами из букв аааббсс. Переставляя первую букву на место второй, а вторую на место первой, мы не получим новой комбинации. Точно так же, меняя местами четвертую и пятую буквы и в целом ряде других случаев, мы новых комбинаций не получаем. Но комбинации abaabcc, caabcb и ряд других – новые. В этом примере , , . Число различных между собой перестановок:

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

Ø  Пример 10. В автомате продается 5 видов шоколада. Сколькими способами можно купить 7 плиток? Число способов будет равно числу сочетаний (т. к. среди купленных 7 плиток нет порядка в расположении) с повторениями (т. к. невозможно купить 7 разных плиток, если имеется 5 видов):

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

Ø  Пример 11. Имеется по одному билету в театр, цирк и музей. Сколькими способами их можно распределить между четырьмя студентами, если каждый может получить сколько угодно билетов? Число способов будет равно числу размещений (т. к. среди билетов есть различия) с повторениями (т. к. возможно, что два или три билета получит один студент):

Бином Ньютона. Биномом Ньютона называют формулу, представляющую выражение при целом положительном в виде многочлена.

Упомянутая формула для целого положительного имеет вид:

Ø  Пример 10.

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

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

1 1 2 1 7 1 ………………………

 

Свойства коэффициентов бинома Ньютона.

1.  Коэффициенты членов, равноудаленных от концов разложения, одинаковы.

2.  Сумма коэффициентов разложения равна .

3.  Сумма коэффициентов членов, стоящих на нечетных местах, равна сумме коэффициентов членов, стоящих на четных местах.

Задания для самостоятельного решения.

1.  Проверить равенство .

2.  Решить уравнение .

3.  Сколькими способами можно составить бригаду, состоящую из 5 врачей 3 мед. сестер, если всего 10 врачей и 7 медсестер?

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

5.  Сколькими способами 10 человек могут встать в очередь друг за другом?

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

7.  В цветочном магазине продаются цветы шести сортов. Сколько можно составить различных букетов из десяти цветов в каждом? (Букеты, отличающиеся лишь расположением цветов, считаются одинаковыми.)

8.  Алфавит некоторого языка содержит 30 букв. Сколько существует шестибуквенных слов (цепочка букв от пробела до пробела), составленных из букв этого алфавита, если буквы в словах могут повторяться?

9.  Найти разложение .

10.  Найти разложение .