1. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел (Слайды к лекциям), страница 2

Числоразличных перестановок выбранных k элементов равно k! (потеореме 2).Следовательно, C (n, k) =(n)kk! .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о команде на олимпиадуНапомним условие задачи.Пример. В олимпиаде по программированию можетучаствовать команда из трех студентов группы.Сколько возможностей составить команду, если в группе 20студентов?Решение. Воспользуемся формулой из теоремы 4:20·19·183= 1140.C (20, 3) = (20)3! =3!Т.е.

существует 1140 возможных команд на олимпиаду попрограммированию из трех студентов этой группы.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЗадача о числе простых графовПример. Сколько существует графов без петель и кратныхребер с n помеченными вершинами и h ребрами?Решение.

Пусть вершины графа помечены числамивидов{1, 2, . . . , n}. Тогда существует всего C (n, 2) = n(n−1)2ребер. Мы считаем графы с h ребрами, т.е. из C (n, 2)возможных ребер нужно выбрать h ребер.Значит, графов без петель и кратных ребер с n помеченнымивершинами и h ребрами, ровно C (C (n, 2), h).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРекуррентная формула для числа сочетанийТеорема 5. При n ≥ 2, 1 ≤ k ≤ n верно равенствоC (n, k) = C (n − 1, k) + C (n − 1, k − 1).Доказательство.

Пусть A = {a1 , . . . , an−1 , an }. Нам надоподсчитать число сочетаний из n по k при 1 ≤ k ≤ n, n ≥ 2.Заметим, что если k = 1, то C (n, 1) = n.С другой стороны, C (n − 1, 1) = n − 1, и, по соглашениям для0убывающих факториалов, верно C (n − 1, 0) = (n−1)= 1.0!Поэтому, C (n, 1) = C (n − 1, 1) + C (n − 1, 0).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРекуррентная формула для числа сочетанийДоказательство (продолжение).

При k ≥ 2 воспользуемсяправилом суммы. Разобьем все сочетания на дванепересекающиеся множества: сочетания, не содержащиеэлемент an , и сочетания, содержащие элемент an .Сочетаний, не содержащих элемент an , в точности C (n − 1, k),т.к. это все сочетания из элементов множестваA0 = {a1 , . . . , an−1 } по k.Сочетаний, содержащих элемент an , в точности C (n − 1, k − 1),т.к. все такие сочетания можно получить, добавив элемент an ,к каждому из сочетаний из элементов множестваA0 = {a1 , . . .

, an−1 } по (k − 1).Отсюда, по правилу суммы,C (n, k) = C (n − 1, k) + C (n − 1, k − 1) при 2 ≤ k ≤ n.Несложно проверить, что доказанное соотношение верно длявсех чисел n и k при 0 ≤ k ≤ n.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадБином НьютонаТеорема 6 [Формула бинома Ньютона]. При n ≥ 1 верноnPC (n, k)x k y n−k .(x + y )n =k=0Доказательство.

(x + y )n = (x + y )(x + y ) . . . (x + y ) .|{z}nПодсчитаем, сколько раз при перемножении скобок появитсяслагаемое x k y n−k , 0 ≤ k ≤ n.Выделим k скобок. Из них выберем множитель x. Изоставшихся (n − k) скобок выберем множитель y .Число возможностей выделить k скобок из всех равно числусочетаний из n по k. Т.е. равно C (n, k).Следовательно, после перемножения скобок и приведенияподобных слагаемых коэффициент при слагаемом x k y n−kбудет равен C (n, k).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадБиномиальные коэффициентыkЧисло (n)дляk! называется биномиальным коэффициентомчисел n и k и обозначается как Cnk или kn .Получили свойства биномиальных коэффициентов: Cn0 = 1,k−1kCnk = 0 при k > n и Cnk = Cn−1+ Cn−1Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадСочетания с повторениямиСочетанием с повторениями из n элементов по k называетсянеупорядоченная (n, k)-выборка с возможными повторениямиэлементов.Пример.

Пусть A = {1, 2, 3}.Перечислим все сочетания с повторениями из элементовмножества A по 2:1, 1; 1, 2; 1, 3; 2, 2; 2, 3; 3, 3.Пример. На почте пять видов открыток к Новому году.Сколькими способами из них можно выбрать семь открыток?Для решения этой задачи надо подсчитать число сочетаний сповторениями из 5 по 7.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло сочетаний с повторениямиЧисло сочетаний с повторениями из n по k будем обозначатькак Ĉ (n, k).Теорема 7. При n ≥ 1, k ≥ 1 верно равенствоĈ (n, k) = C (n + k − 1, k).Доказательство.

Пусть A = {a1 , . . . , an }. Нам надо подсчитатьчисло сочетаний с повторениями из элементов множества A поk при n ≥ 1 и k ≥ 1.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло сочетаний с повторениямиДоказательство (продолжение). Рассмотрим вектор с(n + k − 1) координатами из нулей и единиц, в котором ровно(n − 1) нулей.Содержательно будем считать нули разделителями. Эти (n − 1)нулей делят вектор на n кусков.Будем полагать, что число единиц в i-м куске – это числоэлементов ai в сочетании с повторением, которое соответствуетэтому вектору.

Понятно, что общее число единиц в вектореравно k.Для примера рассмотрим n = 3, и k = 3. Тогда вектор(1, 1, 0, 0, 1) сответствует выборке a1 , a1 , a3 . А, например,выборке a1 , a2 , a3 соответствует вектор (1, 0, 1, 0, 1).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло сочетаний с повторениямиДоказательство (продолжение). Получаем, что каждомусочетанию с повторениями из n по k соответствует некоторыйвектор из нулей и единиц с (n + k − 1) координатами, вкотором ровно (n − 1) нулей, и наоборот, по каждому такомувектору однозначно восстанавливается сочетание сповторением, ему соответствующее.Значит, число сочетаний с повторениями из n по k совпадает счислом таких векторов.А сколько таких векторов? Нам надо из (n + k − 1) координатвектора выбрать k координат, в которых будут стоять единицы.В остальных координатах будут находится нули.Число возможностей выбора – это число сочетаний из(n + k − 1) по k.Следовательно, Ĉ (n, k) = C (n + k − 1, k).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи об открыткахНапомним условие задачи.Пример.

На почте пять видов открыток к Новому году.Сколькими способами из них можно выбрать семь открыток?Решение. Воспользуемся формулой из теоремы 7:= 330.Ĉ (5, 7) = C (5 + 7 − 1, 7) = C (11, 7) = 11·10·9·84!Т.е. существует 330 возможностей составить наборпоздравительных открыток в Новому году.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЗадача о числе псевдографовПример. Сколько существует псевдографов (т.е. графов, вкоторых допускаются петли и кратные ребра) с n помеченнымивершинами и h ребрами?Решение.

Пусть вершины графа помечены числами{1, 2, . . . , n}. Тогда существует всегоĈ (n, 2) = C (n + 1, 2) = n(n+1)видов ребер. Мы считаем графы2с h ребрами, т.е. из Ĉ (n, 2) возможных ребер нужно выбрать свозможными повторениями h ребер.Значит, псевдографов с n помеченными вершинами и hребрами, ровно Ĉ (Ĉ (n, 2), h).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЗадача о билетах в театрПример. Сколькими способами можно распределить трибилета в театр между 20 студентами, если1) распределяются билеты в разные театры, а каждый студентможет получить не более одного билета;2) распределяются билеты в разные театры и на разные дни, акаждый студент может получить любое (не превышающее трех)число билетов;3) распределяются равноценные билеты на вечер, и каждыйстудент может получить не более одного билета;4) распределяются равноценные билеты на вечер, и каждыйстудент может получить сколько угодно (но не более трех)билетов?Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о билетах в театрРешение.1) Пусть распределяются билеты в разные театры, а каждыйстудент может получить не более одного билета.Т.к.

каждый студент может получить не более одного билета,имеем дело с выборкой без повторений.Т.к. билеты неравноценны, то порядок в выборке важен.Значит, число возможных способов распределений билетовравно числу размещений из 20 по 3, т.е.(20)3 = 20 · 19 · 18 = 6840.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о билетах в театрРешение (продолжение).2) Пусть распределяются билеты в разные театры и на разныедни, а каждый студент может получить любое (непревышающее трех) число билетов.Т.к.

каждый студент может получить более одного билета,имеем дело с выборкой с повторениями.Т.к. билеты неравноценны, то порядок в выборке важен.Значит, число возможных способов распределений билетовравно числу размещений с повторениями из 20 по 3, т.е.203 = 8000.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о билетах в театрРешение (продолжение).3) Пусть распределяются равноценные билеты на вечер, икаждый студент может получить не более одного билета.Т.к. каждый студент может получить не более одного билета,имеем дело с выборкой без повторений.Т.к.

билеты равноценны, то порядок в выборке не важен.Значит, число возможных способов распределений билетовравно числу сочетаний из 20 по 3, т.е.3 = (20)3 = 20·19·18 = 10 · 19 · 6 = 1140.C203!6Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о билетах в театрРешение (продолжение).4) Пусть распределяются равноценные билеты на вечер, икаждый студент может получить сколько угодно (но не болеетрех) билетов.Т.к. каждый студент может получить любое число билетов,имеем дело с выборкой с повторениями.Т.к.