subject
Intro

Coursera: Основы комбинаторики (Introduction to combinatorics)

Курс "Основы комбинаторики" является частью программы “Основы комбинаторики и теории чисел”.

В этой части дается введение в комбинаторику.

И здесь удается пройти путь от самых базовых принципов (правило сложения и умножения, принцип Дирихле, формула включений и исключений) и конструкций (сочетания, размещения, перестановки), которые есть, без сомнения, во всех комбинаторных курсах, до совершенно уникальных тем, которые практически в подобных курсах не освещаются, хотя являются по сути одними из самых современных в комбинаторном анализе. Более того, эти уникальные темы дают очень естественный выход на вторую часть курса --- теоретико-числовую. Среди этих тем обращение Мёбиуса, в том числе общая формула на частично упорядоченных множествах, частным случаем которой служит даже формула включений и исключений. В курсе освещаются и другие важные разделы комбинаторики: линейные рекуррентные соотношения с постоянными коэффициентами, формальные степенные ряды и производящие функции, разбиения чисел на слагаемые и диаграммы Юнга, и т.д. Таким образом, курс уникален не только наличием в нем отдельных ярких тем, но и широтой охвата всей комбинаторной тематики.


Syllabus

Неделя 1. Основные принципы комбинаторики. Правило сложения. Правило умножения. Принцип Дирихле. Пример применения принципа Дирихле.  Теорема о раскраске множества в два цвета. Мощности множества попарно неортогональных {-1,0,1}-векторов : верхняя и нижняя оценки. Числа сочетаний, размещений и перестановок. Бином Ньютона. Полиномиальная формула.

Неделя 2. Формула включений и исключений. Простейшие тождества. Треугольник Паскаля. Сумма биномиальных  и полиномиальных коэффициентов. Сумма квадратов биномиальных коффициентов. Формулы для суммы степеней натуральных чисел. Знакопеременное тождество.

Неделя 3. Формула для количества ‘слов’. Определение циклической последовательности. Формулировка проблемы. Простое число. Бесконечность простых. Основная теорема арифметики. Функция Мебиуса. Суммы по делителям. Формула обращения Мебиуса. Вывод формулы для количества циклических последовательностей.

Неделя 4. Частично упорядоченное множество. Обобщенная функция Мебиуса. Связь с обычной функцией Мебиуса. Теорема об формуле обращения Мебиуса на ч.у.м. Передоказательство формулы включений и исключений.

Неделя 5. Разбиения чисел на слагемые. Упорядоченные и неупорядоченные разбиения. Формула для числа упорядоченных разбиений. Рекуррентное соотношение для числа неупорядоченных разбиений. Формула Харди-Рамануджана. Диаграмма Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений.

Неделя 6. Линейные рекуррентные соотношения. Числа Фибоначчи. Теорема о решении линейного рекуррентного соотношения второго порядка. Формальные степенные ряды. Операции над рядами. Пример “деления в столбик”.

Неделя 7. Производящие функции. Теорема о сходимости степенных рядов (б/д). Примеры, иллюстрирующие теоремы. Сходимость на границе интервала. Числа Фибоначчи и их производящая функция. Суммы чисел Фибоначчи, чисел сочетания и пр. Числа Каталана. Извлечение корней из степенных рядов. Формула для числа Каталана: д-во через производящие функции.

Неделя 8. Экзаменационная работа

2 Student
reviews
Cost Free Online Course (Audit)
Pace Finished
Provider Coursera
Language Russian
Certificates Certificate Available
Hours 4-6 hours a week
Calendar 8 weeks long
+ Add to My Courses
Learn Data Analysis udacity.com

Learn to become a Data Analyst. Job offer guaranteed or get a full refund.

Advertisement
75+ Hour Free Coding Course flatironschool.com

Get started with Ruby & JS curriculum online with all-day instructor help.

Advertisement
FAQ View All
What are MOOCs?
MOOCs stand for Massive Open Online Courses. These are free online courses from universities around the world (eg. Stanford Harvard MIT) offered to anyone with an internet connection.
How do I register?
To register for a course, click on "Go to Class" button on the course page. This will take you to the providers website where you can register for the course.
How do these MOOCs or free online courses work?
MOOCs are designed for an online audience, teaching primarily through short (5-20 min.) pre recorded video lectures, that you watch on weekly schedule when convenient for you.  They also have student discussion forums, homework/assignments, and online quizzes or exams.

2 reviews for Coursera's Основы комбинаторики (Introduction to combinatorics)

Write a review
4 months ago
Marat Minshin completed this course.
Was this review helpful to you? YES | NO
2 years ago
Alexander Sigachov completed this course, spending 5 hours a week on it and found the course difficulty to be very hard.
Was this review helpful to you? YES | NO

Write a review

How would you rate this course? *
How much of the course did you finish? *
Review
Create Review