Райгородский А. М. - Комбинаторика - Рекуррентные соотношения

• На прошлой лекции была написана рекурсия для количества разбиений числа на слагаемые.  

• Теорема, доказанная на прошлой лекции, выглядит следующим образом:  

• ф от н н- один нк равняется ф от минус н- один, н- один и так далее.  

• ф от н, н- один и так далее, нк - это количество способов представить число н в виде суммы упорядоченных слагаемых.  

• ф от ноль с любыми параметрами после точки с запятой полагается равным единице.  

• Если н отрицательное, то ф от н, н- один и так далее, нк полагается равным нулю.  

• Функция фиотен определяется как количество способов представить число н в виде суммы натуральных слагаемых.  

• Пример: для н равного единице, существует только одно разбиение, для двойки - два, для тройки - три и так далее.  

• Гипотеза: фиотен всегда равняется два в минус первой степени.  

• Теорема утверждает, что фиотен всегда равен два в минус первой степени.  

• Доказательство проводится по индукции.  

• База индукции уже доказана, шаг индукции: для всех к, не превосходящих н, фиот к равняется два в ка минус первой степени.  

• Доказательство для к плюс один: фиот к плюс один равняется два в ка плюс один минус первой степени.  

• Использование рекурсии для доказательства теоремы.  

• Вычитание н из н плюс один и сохранение всех возможных слагаемых после точки с запятой.  

• Последние два слагаемых никогда не участвуют в разбиении числа н минус один.  

• Ф от один, точка с запятой один, равно единице.  

• Начальное условие: ф от ноль, точка с запятой ноль, равно единице.  

• Объяснение, что такое геометрическая прогрессия и её знаменатель.  

• Пример с прогрессией, начинающейся с единицы и увеличивающейся в k раз.  

• Важность умения суммировать геометрические прогрессии.  

• Напоминание о том, как суммировать геометрические прогрессии.  

• Пример с многочленами и их разложением.  

• Формула для суммы геометрической прогрессии.  

• Применение формулы для суммы геометрической прогрессии.  

• Пример с прогрессией со знаменателем 2.  

• Доказательство, что сумма прогрессии равна 2 в степени n.  

• История о парадоксе Ахиллеса и черепахи.  

• Древние греки боялись пределов и не понимали их.  

• Современные математики преодолели этот барьер и понимают пределы.  

• Гордость за прогресс в понимании пределов.  

• Формальные определения пределов появились в 17-18 веках.  

• Важность формальных определений для анализа.  

• Попеечные разбиения имеют удобную рекурсию.  

• Для помидоров вводится обозначение "ф большое" от n.  

• "Ф большое" учитывает неупорядоченные слагаемые.  

• "Ф большое" считает разбиения, отличающиеся только порядком слагаемых, как одно и то же.  

• "Ф большое" меньше, чем "ф маленькое", так как отождествляет разбиения.  

• "Ф большое" определяется через рекуррентное соотношение.  

• Рекурсия учитывает уменьшение количества параметров после точки с запятой.  

• Доказательство тривиально: разбиения классифицируются по наличию слагаемых величины n-1.  

• Начальные условия для "ф большое" включают "ф от ноль" и "ф от минус ноль".  

• Если после итерации рекурсии не остается параметров, значение равно нулю.  

• Начальные условия позволяют восстановить все возможные значения "ф большое".  

• "п от н" аналогично "ф большое", но учитывает отождествленные разбиения.  

• Для n=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73,  

• Обсуждение чисел Фибоначчи и их связи с числами, которые могут быть восприняты как числа Фибоначчи.  

• Упоминание о том, что никто не знает точной формулы для числа П.  

• Введение в симптотическую формулу для числа П.  

• Сравнение с формулой Стирлинга для факториала.  

• Рассказ о двух английских математиках, Харди и Литтлвуде, и их вкладе в математический анализ и теорию чисел.  

• Упоминание о Рамануджане, индийском математике, который самостоятельно воспроизводил классические результаты без систематического образования.  

• Рамануджан и его работа с Харди и Литтлвудом.  

• Упоминание о том, что Рамануджан получал интуитивные догадки во сне от богини.  

• Описание теоремы Харди и Рамануджана, которая утверждает, что функция П асимптотически ведет себя как 4n корней из трех, умноженное на e в степени пи.  

• Упоминание о сложности доказательства и роли Рамануджана в его завершении.  

• Введение в диаграммную технику для работы с неупорядоченными разбиениями.  

• Упоминание о вкладе Эйлера и Юнга в разработку этой техники.  

• Описание канонического порядка слагаемых в разбиении и его важности для анализа.  

• Рассматривается каноническое разбиение числа на слагаемые.  

• Пример: 4 = 1 + 1 + 2 переписывается как 4 = 1 + 1 + 2.  

• Каноническое разбиение упорядочивает числа по неубыванию величины.  

• Рисуется диаграмма, представляющая разбиение.  

• Пример: 3 + 3 + 3, где количество горошин соответствует числу, разбиваемому на слагаемые.  

• Диаграмма показывает, что числа в каноническом порядке нарастают вправо.  

• Множество неупорядоченных разбиений однозначно соответствует множеству диаграмм.  

• Возможность восстановления разбиения по диаграмме и наоборот.  

• Это позволяет доказывать теоремы о равенстве количеств разбиений.  

• Количество разбиений числа на не более k слагаемых равно количеству разбиений числа на ровно k слагаемых.  

• Пример: разбиение числа n на не более k слагаемых и разбиение числа n+k на ровно k слагаемых.  

• Доказательство требует аккуратного подхода.  

• Преобразование диаграммы для отображения количества слагаемых.  

• Добавление столбика высоты k к диаграмме для отображения разбиения числа n+k.  

• Новая диаграмма однозначно соответствует разбиению числа n+k на ровно k слагаемых.  

• Восстановление разбиения числа n на не более k слагаемых из разбиения числа n+k на ровно k слагаемых.  

• Удаление левого столбика диаграммы для восстановления разбиения числа n.  

• Соответствие между разбиениями установлено.  

• Число n разбивается на не более чем k слагаемых.  

• Добавляется столбик высоты k, что приводит к новому разбиению числа n+k на ровно k слагаемых.  

• Установлено соответствие между разбиениями числа n на не более k слагаемых и разбиениями числа n+k на ровно k слагаемых.  

• Каждому разбиению числа n на не более k слагаемых соответствует разбиение числа n+k на ровно k слагаемых.  

• Диаграммы для этих разбиений взаимно-однозначно сопоставляются.  

• Удаление столбика возвращает к исходному разбиению числа n на не более k слагаемых.  

• Вопрос о том, что не понятно, остается без ответа.  

• Удаление первого столбика восстанавливает разбиение числа n на не более k слагаемых.  

• Количество разбиений каждого типа одинаково.  

• Теорема 1: Количество разбиений числа n на не более k слагаемых равно количеству разбиений числа n+k на ровно k различных слагаемых.  

• Пример с баранами и козлами для иллюстрации.  

• Количество баранов и козлов в стойлах совпадает.  

• Теорема 2: Количество разбиений числа n+k на k+1 слагаемых равно количеству разбиений числа n+k на ровно k различных слагаемых.  

• Отличие от теоремы 1: слагаемые могут быть одинаковыми.  

• Пример с прямоугольным треугольником для иллюстрации.  

• Добавление прямоугольного треугольника с катетами k.  

• Суммарное количество точек в треугольнике равно k+1.  

• Слияние точек в диаграмме приводит к разбиению числа n+k на ровно k различных слагаемых.