Кроме того, приведено интересное комбинаторное понятие—числа Каталана, имеющие разнообразное применение. <...> Основные перечислительные правила Основные перечислительные правила комбинаторики очень просты, естественны и понятны. <...> Правило произведения: если первое событие может произойти n1 способами, а второе независимо от исхода первого события, может произойти n2 способами, то совместная реализация двух событий может произойти n1Чn2 способами. <...> В группе из 20 студентов и 15 студенток: — выбор старосты возможен 20+15=35 способами (правило суммы); 4 (правило произведения). <...> По правилу произведения выбирают: — семизначные телефонные номера (107 вариантов); — семизначные телефонные номера с неповторяющимися цифрами 10 · 9 · 8 · 7 · 6 · 5 · 4 вариантов; — число перестановок из n элементов равно n(n−1) (n−2) · . <...> 5 — выбор пары «студент — студентка» 20Ч15=300 способами Число сочетаний Ck щений, состоящих из одних и тех же элементов, т. е. образующих одно и то же сочетание: Ck n = Ak n Ak k = n! (n−k)! k! . числу способов деления n+k элементов, выстроенных в линию, на n непустых зон: Ck ¯ = коэффициентами поскольку они появляются в формуле бинома Ньютона. — число разных подмножеств мощности k в множестве из n k=0 элементов. <...> Б´ oльшая частьсвойств биномиальных коэффициентов может бытьполучена по меньшей мере двумя способами — из алгебраического выражения для величины Ck ство свойства симметрии очевидно из формулы для Ck n =Cn−k же множестве подмножества мощности n−k. <...> Рекуррентное соотношение Ck ражения для биномиальных коэффициентов и проделав очевидные 6 n = Ck−1 n−1 +Ck щих из определения сочетания. <...> Другие свойства могут бытьлегко получены из формулы бинома Ньютона. <...> Свойство симметрии Ck n и из комбинаторных соображений, вытекаюнаторное доказательство состоит в том, что выбор подмножества мощности k в множестве мощности n эквивалентен выбору в том n . <...> Величины Ck — коэффициенты в формуле бинома Ньютона (x+y)n = n n: n называют также биномиальными IV. <...> Тогда отмеченный <...>
Элементы_комбинаторики.pdf
УДК 519.1
ББК 22.141
Ж85
Рецензенты: А.В. Чашкин, П.Г. Ключарев
Ж85
Жуков А.Е.
Элементы комбинаторики : учеб. пособие / А.Е. Жуков,
Д. А. Жуков. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. —
99, [5] с. : ил.
ISBN 978-5-7038-3752-8
Изложены основные идеи и понятия, нашедшие применение в
области компьютерной криптографии. Приведены разные конструкции
и методы работы с комбинаторными объектами, большое количество
примеров и задач.
Для студентов, изучающих курсы «Информатика», «Дискретная математика»,
«Основы теории информации» и «Комбинаторика». Может
бытьполезно студентам и аспирантам для самостоятельного изучения.
УДК
519.1
ББК 22.141
ISBN 978-5-7038-3752-8
МГТУ им. Н.Э. Баумана, 2014
c
Стр.2
ОГЛАВЛЕНИЕ
Предисловие ..................................................... 3
Глава 1. Основные комбинаторные понятия и схемы .............. 4
1.1. Основные перечислительные правила...................... 4
1.2. Основные комбинаторные схемы .......................... 5
1.3. Числа Стирлинга второго рода............................. 11
1.4. Подстановки на конечном множестве ..................... 14
1.5. Числа Стирлинга первого рода . . . . ........................ 15
1.6. Урновые схемы ........................................... 18
1.7. Схемы отображений конечных множеств . . ................ 20
1.8. Задачи .................................................... 21
Глава 2. Формула включения-исключения......................... 23
2.1. Характеристическая функция множества................... 23
2.2. Число элементов, удовлетворяющих тем или иным свойствам 26
2.3. Приложения формулы включения-исключения . . . . ........ 27
2.4. Задачи .................................................... 29
Глава 3. Линейные рекуррентные последовательности. ............ 31
3.1. Основные понятия и определения ......................... 31
3.2. Линейное пространство линейных рекуррентных последовательностей.......................................................
32
3.3. Решение линейных рекуррентных соотношений............ 36
3.4. Задачи .................................................... 42
Глава 4. Производящие функции.................................. 44
4.1. Энумераторы ............................................. 44
4.2. Формальные степенные ряды ............................. 51
4.3. Получение производящих функций ....................... 56
4.4. Задачи .................................................... 65
Приложения ..................................................... 67
Литература ...................................................... 101
Стр.102