Комбинаторика - это наука, которая, с одной стороны, богата исключительно красивыми постановками задач, зачастую доступными школьнику, а с другой стороны, это очень глубокая современная область знаний, без овладения инструментами которой невозможно серьезное понимание как большинства других фундаментальных дисциплин - анализа, алгебры, теории графов, теории вероятностей и др., - так и многих прикладных проблем. Современная комбинаторика, таким образом, это своего рода основа основ: это и красивейшая теория с массой нетривиальных задач и методов, но это и прекрасная база для приложений в computer science, в анализе сложных сетей, в теории кодирования и криптографии, в биоинформатике и др. В курсе мы познакомим слушателей с наиболее важными областями и инструментами современной комбинаторики, причем многие темы курса по сути уникальны: здесь не только классические комбинаторные величины и тождества, но также и общая теория обращения Мебиуса, и диаграммы Юнга, и рекурсия, и производящие функции. Это позволит нам в дальнейших курсах выйти на реальные приложения в анализе таких сложных сетей, как Интернет, социальные, биологические сети, сети межбанковских взаимодействий и др. Для участия в курсе слушателю необходимо иметь базовые представления о теории множеств и началах анализа. Все остальные понятия будут введены в ходе курса. Курс состоит из 7 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания, составляющие 10% от всего курса (5% тест и 5% задачи с ответом). Экзамен также состоит из теста и задач с ответом, каждая часть оценивается в 15% от общей суммы. Для успешного прохождения курса необходимо в каждом задании набрать не менее 50% от общего числа баллов.
Семинар. Задача 7.7
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Современная комбинаторика (Modern combinatorics)
219 个评分
从本节课中
Производящие функции
Производящие функции. Теорема о сходимости степенных рядов (б/д). Примеры, иллюстрирующие теоремы. Сходимость на границе интервала. Числа Фибоначчи и их производящая функция. Суммы чисел Фибоначчи, чисел сочетания и пр. Числа Каталана. Извлечение корней из степенных рядов. Формула для числа Каталана: д-во через производящие функции.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Седьмая задача.
В этой задаче мы хотим доказать два тождества.
Значит, первое тождество выглядит так, доказательство 4n-нной на Σ (i) от 0 до n.
То есть 2i по i умножить на C2, C из 2 умножить на -i по n-i.
Ну, когда мы видим какое-нибудь страшное тождество, то как мы его доказываем?
Ну, давайте попробуем написать производящую функцию для левой,
правой частей, посмотреть что у нас получается.
Если мы напишем производящую функцию для левой части,
то это будет просто Σ по n (0- ∞) 4n на xn,
так будет производящая функция.
Ну, и как мы уже видели на этом семинаре,
мы можем это объединить в 4x и записать это в виде 1 на (1- 4x).
Мы это для любого λ делали.
Поэтому сейчас, как раз для 4 это подходит.
Ну, или можно это переписать как (1- 4x) в -1 степени.
Давайте посмотрим, что такое правая часть.
Ну, мы видим, что тут, на самом деле, слагаемые это просто C из 2n по n,
умноженные с разными индексами i, ну, и дальше просуммированные.
Давайте напишем производящую функцию, обозначим ее g (x),
производящую функцию для последовательности C из 2n по n и
заметим, что если мы ее умножим на себя,
то мы получим ровно функцию 4 в степени n, согласно этому тождеству.
Значит, как это выглядит?
Если мы возьмем такое произведение, значит,
C из 0 по 0, C из 2 по 1 * x плюс C из 4 по 2 на x² +,
..., и все это умножить на себя
же вот,
мы получим, что если мы посчитаем коэффициент при x в степени n, то
у получившегося произведения, то мы должны его будем просто проссумировать значит,
из этого ряда, мы возьмем коэффициент x при степени η, будет C из 2i по i,
из этого ряда, коэффициент при xn степени i, равен C из 2 на (n- i) по (n- i).
Ну и по ряду если мы посчитаем коэффициент xn у произведения этих двух рядов.
то будет ровно та сумма, которая написана справа.
То есть, сумма справа — это коэффициент при n-нной степени у
степенного ряда g² (x).
То есть, если это равенство выполнено,
то тогда же в ²(x) у нас равно 1- 4x в -1-ой степени.
Но откуда, видимо,
g(x) должен быть равен (1- 4x) в степени -1/2.
То есть если мы докажем, что у этого ряда ровно
вот такие коэффициенты, то это то же самое, такое же тождество,
потому что для этого ряда очевидно, что корень из 2x равно (1- 3x) в -1 степени,
у ряда (1- 4x) в -1 степени вот такой коэффициент при n-нной степени,
а у такого ряда в квадрате, такого ряда в квадрате вот такой коэффициент при n-нной
степени, Ну, значит, мы хотим найти коэффициенты вот такого ряда.
Ну, у нас на лекциях была формула, сейчас я ее напишу,
формула обобщенного биномиального коэффициента, она выглядела так,
(1 + x) в степени α равно сумма по n от 0 до ∞,
C из α(n) на x в степени n, где α — произвольное число.
Но значит, если мы поставим сюда -4x, то это будет выглядеть так.
1- 4x в степени -1/2,
это будет сумма по n от 0 до ∞,
C из -1/2 (n) умножить на -4x в n-нной степени.
Ну, давайте для начала вычислим вот этот обобщенный биномиальный коэффициент,
а потом его поставим сюда и посмотрим, что у нас здесь получится.
Но, давайте перейдем на ту доску.
Значит, мы хотим посчитать C из -1/2 по n.
Ну, давайте по определению.
То есть, по определению мы делим на этот факториал,
а в числителе мы пишем произведение -1/2 (-1/2- 1),
..., и тут должно быть ровно один сомножитель,
то есть последний сомножитель будет (-1/2- n + 1).
Давайте все приведем к общему знаменателю и вынесем 2 за скобку,
значит у нас 2, скобок всего n, значит 2 встречается n раз.
Мы ее напишем в знаменателе.
Тут будет 2n на n факториал.
Ну, давайте сначала, ставим в скобки, значит,
тут будет (-1) тут будет -1/2- 1,
то есть -3/2 то есть тут будет -3 на -5..., ну, и последнее.
Значит, что здесь будет?
Давайте я подробно запишу (-1 -2n и + 2).
То есть будет -2n- 1.
Значит, если я вынесу -1 за скобку, то это будет выглядеть так -1, так, давайте,
лучше я перейду на новую часть, тут не влезет ничего, новую строку,
значит, -1 в n-нной умножить на 1 на 3 на 5, ...,
и последнее будет (2n- 1) поделить на 2n,
2 в n-нной умножить на n факториал.
Вот давайте поймем, насколько это отличается от того, что мы хотим доказать.
Мы хотим доказать, что это 2n факториал, ведь 2n на n факториал.
Но чтобы это был 2n факториал, нужно домножить на все четные числа: 2, 4,
6, 8, ..., 2n.
Вот давайте на них домножим и разделим.
Мы получим, что это будет -1 в n-нной степени умножить
на 2n факториал делить на 2 в n-нной умножить
на n факториал и умножить на четные числа,
на которые мы домножили: 2, 4, 6, 8, ..., 2n.
Но заметим, что если мы отсюда, с каждого сомножителя вынесем двойку, то у нас
будет ровно 2 в степени n на n факториал, то есть ровно то, что написано здесь.
Поэтому это будет равно -1 n-нная
умножить на 2n факториал и
делить на 2 в степени n на n факториал, n факториал и еще 2 в степени n.
То есть, это будет C из 2n по n — то,
что мы хотим доказать и умножить на такой самый множитель.
Это будет -1 в степени n делить на 4 в степени n.
Но теперь давайте вспомним, что мы хотим доказать.
Значит, мы хотим написать коэффициенты ряда
(1- 4x) в степени -1/2.
Как я уже писал, это будет сумма по n от 0 до ∞.
Дальше же нужно поставить коэффициент C из -1/2 по n,
и умножить это все на -4x в степени n.
Давайте подставим то, что здесь написано и вынесем -4.
Значит, мы получим- 1 n-нная делить
на 4n на C из 2n по n и все это
умножить на -4 в степени n на x в степени n.
То есть смотрите, у нас все сокращается -1 n-нная сокращается с -,
а 4n сокращается с 4n-нной.
И мы получаем в точности ряд с коэффициентами
из 2n по n на x в степени n.
То, что мы хотели.
То есть мы доказали, что вот такой ряд что (1- 4x) в степени
-1/2 равен сумме n от 0 до ∞ C из 2n по n на x в степени n.
Значит, он в квадрате равен (1- 4х) в степени- 1 и мы получили
доказательство тождества, которое мы хотели получить.
Так, переходим к пункту б).
Давайте я перейду на ту доску.
Сейчас я возьму условие, чтобы не забыть.
Значит, тут мы хотим доказать следующее тождество.
C из n
по 0 в квадрате- C из n по 1 в квадрате
+...+ -1
n-нная C из n по n².
Значит, надо найти не тождество, а найти сумму.
Чему это равно?
Ну, давайте подумаем.
Ну, опять же мы хотим представить это как какую-то производящую функцию.
Как бы нам ее представить?
Пусть это будет у меня an, значит, я хочу написать вот такую производящую функцию.
Вот смотрите, что здесь происходит.
Мы, явно здесь, разные числа остатков равенства,
давайте мы их немножко перепишем.
А именно, запишем an как, так где бы, давайте здесь запишу.
Вместо того, чтобы написать в квадратах, я напишу их,
перейду к противоположному, то есть заменю C из n по k на C из n по n- k,
тогда у меня получится вот такое произведение.
Значит, an у меня равно вот
такому произведению, ну, смотрите,
теперь явно у меня есть тут произведение каких-то двух рядов,
видите, у меня коэффициенты C из n по i добавляется на коэффициент из C по n- i.
Давайте рассмотрим две производящих функции.
Значит, одна функция у меня будет f(x) это будет просто сумма,
по n от 0 до ∞, C из n.
Так, тут надо написать какую-нибудь i,
да C из n по i на x в степени i ну, то есть понятно,
что я просто не для i больших n, у меня этот коэффициент будет равен 0.
Ну и g(x), я возьму тоже самое, только будет тут коэффициент еще
-1 в степени i, C из n по i, x в степени i.
Ну и для простоты можно сказать,
что у нас тут сумма естественно идет только до n, до n-нной степени.
Так, ну, и если еще преобразовать,
то это просто будет не что иное, как 1-ое будет не что иное,
как (1+x) в степени n, а второе будет не что иное, как (1- x) в степени n.
Это в бинуале то, что мы уже встречали на первых лекциях.
Вот теперь смотрите, an это ровно n-нный коэффициент у произведения этих рядов.
Ну, это понятно, потому что мы ровно, когда мы берем этот коэффициент под
нулевой степенью 1-го ряда умножить на n-нный коэффициент второго ряда.
А это там первый коэффициент там ряда g(x), коэффициент первой степени ряда
g(x), а это коэффициент при n- 1 степени ряда f(x) и так далее.
Ну, значит, что у нас получается, что эта сумма, значит,
эта производящая функция — это просто f(x) умножить на g(x), то есть,
это будет (1 + x) в степени n умножить на -x в степени n.
Но это не что иное, как (1- x²) в степени n.
То есть an-нные — это просто коэффициенты вот такого ряда.
Ну, отсюда легко получается формула для n.
Значит, давайте как можно раскрыть этот ряд.
Что у нас получится?
Значит, это будет сумма по i от 0 до 2n.
И дальше у нас коэффициенты будут встречаться только при четных степенях,
ну, то есть коэффициенты в степени i, то есть это будет n в степени i,
C из 2n по C из n по i умножить на x в степени 2i.
Ну все, значит у меня вот этому равно n.
Значит, у меня n будет равно 0, если n — нечетно.
и -1 в степени i на C из n по i,
если у меня i пробегает
i = 2k и пробегает от 0 до 2n.
Да, только сейчас тут надо было написать,
тут надо было написать наверное ai видимо тогда.
Так будет правильно написать.
Вот ответ.
Все — задача решена.
