1.1: Композиції та розділи

Last updated
Save as PDF

Page ID: 105472

Leo Moser
University of Alberta via The Trilla Group

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Розглядаються проблеми, що стосуються кількості способів, за допомогою яких число може бути записано у вигляді суми. Якщо береться до уваги порядок членів в сумі, то сума називається складом і кількість композицій$n$ позначається$c(n)$. Якщо порядок не враховується, сума є розділом, а кількість розділів$n$ позначається$p(n)$. Таким чином, склади з 3 є

3 = 3, 3 = 1 + 2, 3 = 2 + 1, а 3 = 1 + 1 + 1,

так що$c(3) = 4$. Перегородки з 3 є

3 = 3, 3 = 2 + 1, а 3 = 1 + 1 + 1,

так$p(3) = 3$.

Існує по суті три методи отримання результатів на композиціях і перегородках. Спочатку суто комбінаторними аргументами, друге - алгебраїчними аргументами з генеруючими рядами і, нарешті, аналітичними операціями над генеруючим рядом. Обговоримо лише перші два з цих способів.

Ми розглядаємо перші композиції, з ними легше обробляти, ніж перегородки. Функція легко$c(n)$ визначається наступним чином. Розглянемо$n$ записані як суму 1. Ми маємо$n - 1$ пробіли між ними, і в кожному з пробілів ми можемо вставити косу$2^{n - 1}$ риску, даючи можливості, що$2^{n - 1}$ відповідають композиції$n$. Наприклад

3 = 1 1 1, 3 = 1/1 1, 3 = 1 1/1, 3 = 1/1/1.

Якраз для ілюстрації алгебраїчного методу в цьому досить тривіальному випадку ми розглянемо

$\sum_{\infty}^{n = 1} c(n)x^n$.

Легко перевірити, що

$\begin{array} {rcl} {\sum_{n = 1}^{\infty} c(n) x^n} &= & {\sum_{m = 1}^{\infty} (x + x^2 + x^3 + \cdot \cdot \cdot)^m} \\ {} &= & {\sum_{m = 1}^{\infty} (\dfrac{x}{1 - x})^m = \dfrac{x}{1 - 2x} = \sum_{n =1}^{\infty} x^{n - 1}x^n.} \end{array}$

Приклад$\PageIndex{1}$

В якості вправи я б запропонував використовувати як комбінаторний метод, так і алгебраїчний підхід, щоб довести наступні результати:

Кількість композицій$n$ в точності$m$ частини є${n - 1 \choose m -1}$ (каталонська);
Число композицій$n$ на парні частини -$2^{\dfrac{n}{2} - 1}$ якщо$n$ парне і 0, якщо$n$ непарне;
Кількість композицій з$n$ на парну кількість частин дорівнює кількості композицій з на$n$ непарну кількість частин.

Рішення

Додайте сюди текст.

Дещо цікавіше - визначення кількості$c^{*}(n)$ композицій на непарні$n$ частини. Тут алгебраїчний підхід дає

$\begin{array} {rcl} {\sum_{n = 1} c^{*}(n) x^n} &= & {\sum_{m = 1}^{\infty} (x + x^3 + x^5 + \cdot \cdot \cdot)^m} \\ {} &= & {\sum_{m = 1}^{\infty} (\dfrac{x}{1 - x^2})^m = \dfrac{x}{1 - x - x^2} = \sum F(n) x^n.} \end{array}$

Перехресне множення останніх двох виразів ми бачимо, що

$F_{n + 2} = F_{n} + F_{n + 1}$,$F_0 = 0, F_1 = 1$

Таким чином, F - це так звані числа Фібоначчі.

1, 1, 2, 3, 5, 8, 13,...

Функція, що генерує, дає два явних вирази для цих чисел. По-перше, шляхом «часткового дроблення»$\dfrac{x}{1 - x - x^2}$, розширюючи кожен член як степеневий ряд і порівнюючи коефіцієнти, отримаємо

$F_n = \dfrac{1}{\sqrt{5}}{(\dfrac{1 + \sqrt{5}}{2})^n - (\dfrac{1 - \sqrt{5}}{2})^n}.$

Інший вираз для$F_n$ отримують, спостерігаючи, що

$\dfrac{x}{1 - x - x^2} = x(1 + (x + x^2)^1 + (x + x^2)^2 + (x + x^2)^3 + \cdot\cdot\cdot).$

Порівнюючи коефіцієнти тут отримаємо (Лукас)

$F_n = {n - 1 \choose 0} + {n - 2 \choose 1} + {n - 3 \choose 2} + \cdot\cdot\cdot).$

Можна розглянути проблему виведення цієї формули за допомогою комбінаторних аргументів.

Припустимо, ми позначимо кількістю композицій n з усіма доданими не більше 2, а по b (n) кількість композицій$n$ з усіма доданими не менше 2.$a(n)$ Цікавий результат полягає в тому, що$a(n) = b(n + 2)$. Доведу цей результат і пропоную проблему пошуку розумного узагальнення.

Спочатку зауважте, що$a(n) = a(n − 1) + a(n − 2)$. Це випливає з того, що кожна допустима композиція закінчується на 1 або 2. Видаливши це останнє доведення, отримаємо допустимий склад$n − 1$ і$n − 2$ відповідно. Так як$a(1) = 1$ і$a(2) = 2$, з цього випливає$a(n) = F_n$. Функція$b(n)$ задовольняє тій же формулі рекурсії. Фактично, якщо остання досада в допустимому складі$n$ є 2, вилучити його для отримання допустимого складу$n − 2$; якщо останній доказ більше 2, зменшити його на 1, щоб отримати допустимий склад$n − 1$. Так як$b(2) = b(3) = 1$, випливає, що$b(n) = F_{n−2}$ так$a(n)=F_n =b(n+2)$.

Цікавою ідеєю для композицій є вага композиції. Припустимо, ми пов'язуємо з кожним складом число, яке називається вагою, яке є твором доводів. Визначимо$w(n)$ суму ваг складів$n$. Генеруюча функція$w(n)$ є

$\sum_{n = 1}^{\infty} w(n) x^n = \sum_{m = 1}^{\infty} (x + 2x^2 + 3x^3 + \cdot\cdot\cdot)^m = \dfrac{x}{1 - 3x + x^2}.$

З цього ми знаходимо, що$w(n)=3w(n − 1) − w(n − 2)$. Я залишаю це як вправу, щоб довести з цього, що$w(n) = F_{2n−1}$.

Тепер перейдемо до перегородок. Не існує простої явної формули для$p(n)$. Нашою головною метою тут буде довести формулу рекурсії

$p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + p(n - 15) + \cdot\cdot\cdot$

виявлений Ейлером. Алгебраїчний підхід до теорії розділів залежить від алгебраїчних маніпуляцій з генеруючою функцією

$\sum_{n = 0}^{\infty} p(n)x^n = \dfrac{1}{(1 - x)(1 - x^2)(1 - x^3) \cdot\cdot\cdot}$

та пов'язані функції для розділів з обмеженим доступом. Комбінаторний підхід залежить від використання діаграм розділів (Феррера). Наприклад, діаграма Феррера розділу 7 = 4 + 2 + 1

$Знімок екрана 2019-10-20 в 8.42.16 PM.png$

Корисним тут є поняття сполучених розділів. Це виходить при відображенні схеми в$45^{\circ}$ лінії, що йде вниз від лівого верхнього кута. Наприклад,

перегородки

$Знімок екрана 2019-10-20 в 8.47.04 PM.png$ і $Знімок екрана 2019-10-20 в 8.47.14 PM.png$

сполучені один з одним. Така відповідність дає практично відразу такі теореми:

Число перегородок$n$ на$m$ частини дорівнює кількості перегородок$n$ на частини, найбільша з яких$m$;
кількість$n$ перегородок на не більше$m$ частин дорівнює числу перегородок $n$на частини, що не перевищують$m$.

Дещо інший характер має наступний: кількість перегородок$n$ на непарні частини дорівнює числу перегородок$n$ на окремі частини. Для цього наведемо алгебраїчне доказ. Використовуючи досить очевидні функції генерації для необхідних розділів, результат зводиться до показу того, що

$\dfrac{1}{(1 - x)(1 - x^3)(1 - x^5)(1 - x^7)\cdot\cdot\cdot} = (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)\cdot\cdot\cdot.$

Перехресне множення робить результат інтуїтивно зрозумілим.
Тепер перейдемо до більш важливої теореми завдяки Ейлеру:

$(1 - x)(1 - x^2)(1 - x^3)\cdot\cdot\cdot = 1 - x^1 - x^2 + x^5 + x^7 - x^{12} - x^{15} + \cdot\cdot\cdot,$

де експоненти - це номери форми$\dfrac{1}{2} k(3k \pm 1)$. Спочатку відзначимо, що

$(1 - x)(1 - x^2)(1 - x^3) \cdot\cdot\cdot = \sum((E(n) - O(n))x^n,$

де$E(n)$ - кількість$n$ розділів на парну кількість окремих частин і$O(n)$ кількість$n$ розділів на непарну кількість окремих частин.

Ми намагаємося встановити відповідність один до одного між розділами двох розглянутих видів. Така кореспонденція, природно, не може бути точною, оскільки точна відповідність довела б це$E(n) = O(n)$.

Беремо графік, що представляє$n$ поділ на будь-яку кількість нерівних частин. Найнижчу лінію$AB$ називаємо основою графа. З$C$ крайнього північно-східного вузла ми проводимо найдовшу південно-західну лінію, можливу на графіку; це може містити лише один вузол. Ця лінія$CDE$ називається крилом графа.

$Знімок екрана 2019-10-20 в 8.56.40 PM.png$

Зазвичай ми можемо перемістити базу в положення нового крила (паралельно і праворуч від «старого» крила). Іноді ми можемо проводити зворотну операцію (переміщення крила повинно бути над основою, нижче старої основи). Коли описана операція або її зворотна можлива, вона веде з розділу з в непарну кількість частин в парну кількість частин або навпаки. Таким чином, в цілому$E(n) = O(n)$. Однак два випадки вимагають особливої уваги,. Вони типізовані діаграмами

$Знімок екрана 2019-10-20 в 8.57.17 PM.png$ і $Знімок екрана 2019-10-20 в 8.57.41 PM.png$

У цих випадках$n$ має вигляд

$k + (k + 1) + \cdot\cdot\cdot + (2k - 1) = \dfrac{1}{2} (3k^2 - k)$

$(k + 1) + (k + 2) + \cdot\cdot\cdot + (2k) = (3k^2 + k)$.

В обох цих випадках відбувається перевищення однієї перегородки на парну кількість частин, або однієї в непарне число, відповідно як$k$ парне або непарне. Значить$E(n) - O(n) = 0$, хіба що$n = \dfrac{1}{2}(3k \pm k)$, коли$E(n) - O(n) = (-1)^k$. Це дає теорему Ейлера.

Тепер, з

$\sum p(n) x^n (1 - x - x^2 + x^5 + x^7 - x^{12} - \cdot\cdot\cdot) = 1$

отримуємо рекуррентне відношення для$p(n)$, а саме

$p(n) = p(n - 1) + p(n - 2) - p(n - 5) - p(n - 7) + p(n - 12) + \cdot\cdot\cdot.$