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

Лекция: Основные комбинаторные числа.Оценки и асимптотики для комбинаторныхчисел.Лектор - доцент Селезнева Светлана Николаевнафакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suВыборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадВыборкиПусть A = {a1 , . . . , an } – множество из n элементов.Совокупность элементов ai1 , . . . , aik , k ≥ 1, называетсявыборкой объема k из n элементов, или (n, k)-выборкой.Выборка называется упорядоченной, если порядокследования элементов в ней задан.Две упорядоченные выборки, отличающиеся лишь порядкомследования элементов, считаются различными.Если порядок следования элементов не являетсясущественным, то выборка называется неупорядоченной.В выборках могут допускаться или не допускаться повторенияэлементов.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадПравило суммы и правило произведенияКак правило, основной вопрос заключается в подсчете числавозможных выборок с определенными свойствами.Часто при подсчете числа комбинаторных объектов (выборок)применяются два основных приема: правило суммы иправило произведения.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадПравило суммы правило произведенияПравило суммы: если объект A может быть выбран mспособами, а объект B – другими n способами при условии,что одновременный выбор A и B невозможен, то выбор «A илиB» можно осуществить m + n способами.Правило произведения: если объект A может быть выбран mспособами, и после каждого из таких выборов объект B в своюочередь может быть выбран n способами, то выбор «A и B» вуказанном порядке можно осуществить m · n способами.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРазмещенияРазмещением из n элементов по k называется упорядоченная(n, k)-выборка без повторений элементов.Пример.

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

При 1 ≤ k ≤ n верно равенствоP(n, k) = n(n − 1) · · · · · (n − k + 1).Доказательство. Пусть A = {a1 , . . . , an }. Нам надо подсчитатьчисло размещений из n по k, 1 ≤ k ≤ n.Понятно, что если k = 1, то P(n, 1) = n.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло размещенийДоказательство (продолжение).

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

. , ai−1 , ai+1 , . . . , an }. Таких размещений вточности P(n − 1, k − 1).Получаем рекуррентное соотношениеP(n, k) = n · P(n − 1, k − 1) при 2 ≤ k ≤ n.Отсюда по индукции получаем, чтоP(n, k) = n(n − 1) · · · · · (n − k + 1).Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о туристеНапомним условие задачи.Пример. Турист может посетить города Углич, Ростов,Ярославль, Кострому, Сергиев Посад.Сколько маршрутов с последовательным посещением трехгородов он может составить?Решение. Воспользуемся формулой из теоремы 1:P(5, 3) = 5 · 4 · 3 = 60.Т.е. можно составить 60 таких маршрутов.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадУбывающий факториалЧисло n(n − 1) · · · · · (n − k + 1) называется убывающимфакториалом для чисел n и k и обозначается как (n)k .

Т.е.P(n, k) = (n)k .Для удобства вычислений по определению полагают, что(n)0 = 1 и (n)k = 0 при 0 ≤ n < k.Получили рекуррентное соотношение для убывающихфакториалов (n)k = n · (n − 1)k−1 .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадПерестановкиПерестановкой n элементов называется упорядоченная(n, n)-выборка без повторений элементов.Пример. Пусть A = {1, 2, 3}.Перечислим все перестановки элементов множества A:1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 1, 2; 3, 2, 1.Пример.

Восемь студентов пишут ответ на экзаменационныйвопрос.Сколькими способами их могут последовательно вызватьотвечать?Для решения этой задачи надо подсчитать число перестановок8 элементов.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло перестановокЧисло перестановок n элементов будем обозначать как P(n, n).Теорема 2. Имеет место равенство P(n, n) = n(n − 1) · · · · · 1.Доказательство.

Перестановка – это частный случайразмещения n элементов по k при k = n.Поэтому (по теореме 1) P(n, n) = (n)n = n(n − 1) · · · · · 1.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о студентахНапомним условие задачи.Пример. Восемь студентов пишут ответ на экзаменационныйвопрос.Сколькими способами их могут последовательно вызватьотвечать?Решение. Воспользуемся формулой из теоремы 2:P(8, 8) = 8 · 7 · · · · · 1 = 5760.Т.е. возможны 5760 вариантов последовательных ответовстудентов.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадФакториалЧисло n(n − 1) · · · · · 1 называется факториалом числа n иобозначается как n!Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРазмещения с повторениямиРазмещением с повторениями из n элементов по kназывается упорядоченная (n, k)-выборка с возможнымиповторениями элементов.Пример.

Пусть A = {1, 2, 3}.Перечислим все размещения с повторениями по 2 из элементовмножества A:1, 1; 1, 2; 1, 3; 2, 1; 2, 2; 2, 3; 3, 1; 3, 2; 3, 3.Пример. Есть по одному билету в театр, в цирк и на концерт.Сколькими способами их можно распределить между четырьмястудентами (если каждый студент может получить сколькоугодно билетов)?Для решения этой задачи надо подсчитать числа размещений сповторениями из 4 по 3.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло размещений c повторениямиЧисло размещений с повторениями из n по k будем обозначатькак P̂(n, k).Теорема 3.

При n ≥ 1, k ≥ 1 верно равенство P̂(n, k) = nk .Доказательство. Пусть A = {a1 , . . . , an }. Нам надо подсчитатьчисло размещений с повторениями из n по k, n ≥ 1, k ≥ 1.Понятно, что если k = 1, то P̂(n, 1) = n.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло размещений с повторениямиДоказательство (продолжение). При k ≥ 2 воспользуемсяправилом произведения.

Выделим два признака каждогоразмещения с повторениями: значение первого элемента изначения всех остальных элементов.Первый элемент можно выбрать n различными способами.При каждом фиксированном первом элементе, например, какai , остальные элементы образуют размещение с повторениямипо (k − 1) из того же множества A = {a1 , . . . , an }. А такихразмещений с повторениями в точности P̂(n, k − 1).Получаем рекуррентное соотношение P̂(n, k) = n · P̂(n, k − 1)при n ≥ 1, k ≥ 2.Отсюда по индукции получаем, что P̂(n, k) = nk .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадРешение задачи о билетахНапомним условие задачи.Пример. Есть по одному билету в театр, в цирк и на концерт.Сколькими способами их можно распределить между четырьмястудентами (если каждый студент может получить сколькоугодно билетов)?Решение.

Воспользуемся формулой из теоремы 3:P̂(4, 3) = 43 = 64.Т.е. существует 64 способа распределения билетов междустудентами.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЗадача о числе функций алгебры логикиПример. Сколько существует функций алгебры логики,зависящих от переменных x1 , . . . , xn ?Решение.

Каждая функция алгебры логики определяетсясвоими значениями на 2n наборах значений переменных. Накаждом наборе она принимает или значение 0, или значение 1.Значит, функций алгебры логики, зависящих от переменныхnx1 , . . . , xn , есть P̂(2, 2n ) = 22 .Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадСочетанияСочетанием из n элементов по k называется неупорядоченная(n, k)-выборка без повторений элементов.Пример.

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

Пусть A = {a1 , . . . , an }. Нам надо подсчитатьчисло сочетаний из n по k, 1 ≤ k ≤ n.Рассмотрим все размещения из n элементов множества A по k.Их ровно (n)k .В каждом размещении выбраны какие-то k элементов измножества A. Если не учитывать порядок этих выбранных kэлементов, мы получим некоторое сочетание из элементовмножества A по k.Выборки Размещения Перестановки Размещения с повторениями Сочетания Сочетания с повторениями ЗадЧисло сочетанийДоказательство (продолжение). Другими словами,размещения с одним и тем же набором выбранных k элементовзадают одно и то же сочетание по k элементов.Чем различаются размещения с одним и тем же наборомвыбранных k элементов? Только порядком элементов.