dm_tema_2

Пример

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

Составим первое число 12345. Все остальные числа получим перестановкой цифр этого числа. Всего будет 5!=120 различных чисел.

Пример

В студенческой группе из 25 человек необходимо выбрать старосту и профорга. Сколькими способами можно сделать этот выбор? Задача заключается в размещении без повторения 2-х элементов из 25. Число размещений равно

Пример

Сколько существует различных булевых векторов длины 8, содержащих ровно 3 единицы?

Ответом является число сочетаний из 8 по 3 без повторений

C83 = 5!3!8! = 56:

Пример

Сколькими способами можно распределить k одинаковых предметов по n различным корзинам?

Для каждого предмета выбираем корзину. Таким образом, формируем неупорядоченные выборки из n ïî k с повторениями. Число таких

выборок равно k

Cn .

Пусть упорядоченное множество A = fa1; : : : ; ang содержит повторяющиеся элементы m типов.

Например, множество цифр числа 732773 содержит элементы тр¼х типов f7; 3; 2g.

Обозначим через ki число элементов i-ãî òèïà, i = 1; : : : ; m, k1 + + km = n.

Сколько можно получить различных перестановок множества A?

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

n!

Pk1;k2;:::;km = k1!k2! km!:

Пример

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

Всего букв в слове 11. Буквы и, а встречаются дважды. Следовательно, число различных слов будет равно

11!

2!2!

= 9979200:

Пусть A конечное множество, jAj = n. Зададим целые положительные числа k1; : : : ; km такие, что

k1 + + km = n:

Теорема

Число разбиений множества A íà m непересекающихся подмножеств

Доказательство.

По правилу произведения

n!

= k1!k2! : : : km!:

Заметим, что формулы для Cnk1;k2;:::;km è Pk1;k2;:::;km совпадают.

Пример

Сколькими способами можно сформировать две подгруппы из группы студентов в 25 человек, если в одной подгруппе будет 12 студентов, во второй 13?

Это можно сделать

способами.

2. Комбинаторика 2.3 Биномиальные коэффициенты

2.3 Биномиальные коэффициенты

называются биномиальными коэффициентами.

Теорема

Справедливы формулы:

1)Cn0 = Cnn = 1

2)Cnm = Cnn m

Доказательство. Докажем 3

2. Комбинаторика 2.3 Биномиальные коэффициенты

Формулу

Cnm = Cnm 11 + Cnm 1

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

Каждый из внутренних элементов треугольника равен сумме двух элементов, расположенных над ним