Explore

Современная комбинаторика (Modern combinatorics)

Approx. 32 hours to complete

Save Course

Go to Course

Course Summary

This course is an introduction to modern combinatorics, covering topics such as enumeration, graph theory, and designs. It is suitable for anyone with a basic knowledge of discrete mathematics.

Key Learning Points

Learn how to solve combinatorial problems using various techniques
Understand the importance of combinatorics in computer science, cryptography, and other fields
Explore advanced topics such as Ramsey theory and algebraic combinatorics

Learning Outcomes

Ability to solve complex combinatorial problems using various techniques
Understanding of the importance of combinatorics in various fields
Familiarity with advanced topics such as Ramsey theory and algebraic combinatorics

Prerequisites or good to have knowledge before taking this course

Basic knowledge of discrete mathematics
Familiarity with mathematical notation

Course Difficulty Level

Intermediate

Course Format

Online self-paced course
Video lectures
Assignments and quizzes
Discussion forums

Similar Courses

Applied Combinatorics
Combinatorics and Probability
Discrete Mathematics

Related Education Paths

Notable People in This Field

Paul Erdős
Ronald Graham
Richard Rado

Related Books

Description

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

Современная комбинаторика, таким образом, это своего рода основа основ: это и красивейшая теория с массой нетривиальных задач и методов, но это и прекрасная база для приложений в computer science, в анализе сложных сетей, в теории кодирования и криптографии, в биоинформатике и др. В курсе мы познакомим слушателей с наиболее важными областями и инструментами современной комбинаторики, причем многие темы курса по сути уникальны: здесь не только классические комбинаторные величины и тождества, но также и общая теория обращения Мебиуса, и диаграммы Юнга, и рекурсия, и производящие функции. Это позволит нам в дальнейших курсах выйти на реальные приложения в анализе таких сложных сетей, как Интернет, социальные, биологические сети, сети межбанковских взаимодействий и др. Для участия в курсе слушателю необходимо иметь базовые представления о теории множеств и началах анализа. Все остальные понятия будут введены в ходе курса. Курс состоит из 7 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания, составляющие 10% от всего курса (5% тест и 5% задачи с ответом). Экзамен также состоит из теста и задач с ответом, каждая часть оценивается в 15% от общей суммы. Для успешного прохождения курса необходимо в каждом задании набрать не менее 50% от общего числа баллов. Данный курс рекомендуется к прохождению перед курсом Теория вероятностей.

Outline

Основные принципы комбинаторики
Введение
МФТИ
Правила сложения и умножения
Пример на правило умножения
Принцип Дирихле
Пример с квадратом
Последовательности векторов. Постановка задачи
Последовательности векторов. Доказательство утверждения
Шестизначные числа
Первокурсники в кинотеатре
Числа сочетаний, размещений и перестановок. Определения.
Теоремы о числе размещений с повторениями и без
Количество сочетаний без повторений
Количество сочетаний с повторениями
Дежурство в столовой
Карты из колоды
Тома Пушкина на книжной полке
Теорема о раскраске множества в два цвета. Формулировка утверждения (*)
Теорема о раскраске множества в два цвета. Доказательство утверждения (*)
Теорема о раскраске множества в два цвета. Общая проблема (*)
Программа и расписание курса
Список литературы
Правила аттестаций
Правила поведения на форуме
МФТИ
Условия задач
Конспект
Решение задач
Конспект
Условия задач.
Условия и решения задач
Решения задач
Тест к неделе 1
Задачи к неделе 1
Дополнительные задачи

Комбинаторные тождества
Бином Ньютона. Полиномиальный коэффициент
Полиномиальная формула
Задачи и студенты
Фигуры на шахматной доске
Формулировка утверждения
Научно-исследовательский институт
Книги на полке
Комбинаторные тождества 1-2. Треугольник Паскаля
Комбинаторные тождества 3-4
Комбинаторное тождество 5
Комбинаторное тождество 6
Сумма степеней натуральных чисел
Комбинаторные тождества 7-8
Сумма биномиальных коэффициентов с чётными показателями
Вычисление хитрой суммы биномиальных коэффициентов
База и предположение индукции(*).
Переход индукции (*)
Конспекты
Условия задач
Условия задач
Конспект
Конспект
Условия задач
Решения задач
Тест к неделе 2
Задачи к неделе 2
Дополнительные задачи

Формула обращения Мёбиуса
Циклические слова
Простые числа
Основная теорема арифметики
Исторический анекдот(**)
Количество циклических последовательностей длины 2
Существование разложение в произведение простых чисел (**)
Вспомогательное утверждение для основной теоремы арифметики(**)
Доказательство единственности разложения в произведения простых (**)
Функция Мёбиуса
Сумма по делителям числа
Сумма функции Мебиуса по делителям числа
Формула обращения Мебиуса. Формулировка
Формула обращения Мебиуса. Доказательство
Пример применения формулы обращения Мёбиуса -1
Пример применения формулы обращения Мёбиуса - 2
Пример применения формулы обращения Мёбиуса -3
Условия задач
Конспект
Условия и решения задач
Условия задач
Конспект
Условия и решения задач
Решения контрольной работы
Тест к неделе 3
Задачи к неделе 3

Циклические последовательности
Линейные и циклические последовательности
Период линейной последовательности
Биекция между множествами последовательностей одного периода
Количество линейных последовательностей
Количество циклических последовательностей длины n и периода n
Количество циклических последовательностей
Пример вычисления количества циклических последовательностей
Пример вычисления количества циклических последовательностей -2
Частично упорядоченное множество
4.8. Функция Мебиуса для ЧУМа
4.9. Связь с обычной функцией Мебиуса
4.10 Совпадение функций Мебиуса для произведения различных простых чисел
4.11 Совпадение функций Мебиуса для остальных чисел
4.12 Формула обращения Мебиуса на ЧУМе
Семинар. Задача 4.3
Семинар. Задача 4.4
4.13 Определение множества.(*)
4.14 Определение частичного порядка (*)
4.15 Функция Мёбиуса (*).
Условия задач
Конспект
Решения задач
Условия задач
Конспект
Условия и решения задач
Решения задач недели 4.
Конспект
Тест к неделе 4
Задачи к неделе 4
Дополнительные задачи

Разбиения
5.1 Разбиения чисел на слагаемые
5.2 "Карнавальная" формулировка задач о разбиениях (**)
5.3. Задача о "попойке"
5.4 Задача о "капусте"
5.5 Формула Харди-Рамануджана (*), (**)
Семинар. Задача 5.1
5.6 Диаграмма Юнга
5.7. Теоремы о количестве неупорядоченных разбиений.
5.8 Двойственная диаграмма Юнга
Семинар. Задача 5.2
Семинар. Задача 5.3
Семинар. Задача 5.4
5.9 Обобщенная формула обращения Мебиуса (*)
5.10 Вывод формулы включений и исключений(*).
Условие задач
Конспект
Решения задач
Условия задач
Конспект
Условия и решения задач
Конспект
Решения задач 5 недели
Тест к неделе 5
Задачи к неделе 5

Линейные рекуррентные соотношения. Формальные степенные ряды.
6.1 Линейные рекуррентные соотношения
6.2 Числа Фибоначчи
6.3 Линейные рекуррентные соотношения второго порядка. Характеристическое уравнение
6.4 Линейные рекуррентные соотношения второго порядка. Теорема 1. Формулировка
6.5 Линейные рекуррентные соотношения 2 порядка. Теорема 1. Пункт 1. Доказательство
6.6 Линейные рекуррентные соотношения 2 порядка. Теорема 1. Пункт 2. Доказательство
6.7 Линейные рекуррентные соотношения 2 порядка. Теорема 2
6.8 Линейные рекуррентные соотношения k порядка (*)
Семинар. Задача 6.1
Семинар. Задача 6.2
Семинар. Задача 6.3
Семинар. Задача 6.4
6.9 Формальные степенные ряды
6.10 Деление степенных рядов
6.11 Вывод комбинаторного тождества при помощи формальных степенных рядов
Семинар. Задача 6.5
Семинар. Задача 6.6
Условия задач
Конспект
Условия и решения задач
Условия задач
Конспект
Условия и решения задач
Решения задач недели 6
Тест к неделе 6
Задачи к неделе 6

Производящие функции
7.1 Производящая функция
7.2 Теорема о сходимости рядов
7.3 Примеры, иллюстрирующие теорему
7.4 Сходимость на границе круга (*)
7.5 Пример вычисления производящей функции
Семинар. Задача 7.1
Семинар. Задача 7.2
Семинар. Задача 7.3
Семинар. Задача 7.4
7.6 Пример с числами Фибоначчи
7.7 Производящая функция чисел Фибоначчи
7.8 Числа Каталана
7.9 Производящая функция чисел Каталана
7.10 Извлечение корня из формального степенного ряда
7.11 Формула для чисел Каталана
Семинар. Задача 7.5
Семинар. Задача 7.6
Семинар. Задача 7.7
Условия задач
Конспект
Решения задач
Условия задач
Конспект
Условия и решения задач
Решения задач недели 7
Тест к неделе 7
Задачи к неделе 7

Экзамен
Экзаменационный тест
Экзаменационные задачи

Summary of User Reviews

Read reviews for the Modern Combinatorics course on Coursera. Users generally enjoyed the course and found it to be informative and well-structured. One key aspect that users appreciated was the clear and concise explanations of complex concepts.