1. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел (1268163)
Текст из файла
Лекция: Основные комбинаторные числа.Оценки и асимптотики для комбинаторныхчисел.Лектор - доцент Селезнева Светлана Николаевнафакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте 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 элементов? Только порядком элементов.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
