Глава 1. Комбинаторика — процессный счёт

Где стоит часть

После метатеории (Часть XIV) и частей о вычислении и функции-как-процессе (XV–XVI) том приходит к прикладной математике. Три дисциплины настоящей части — комбинаторика, теория вероятностей, теория информации — объединены одним свойством: они онтологически конкретны. Они работают с конечными списками и алгоритмическими процессами, не требуют аксиомы выбора и завершённых несчётных пространств, и потому ложатся в P4-онтологию почти без зазора. Это самая 0-аксиомная часть тома.

Сквозная нить части — информация как количество актов различения: комбинаторика считает различения, вероятность распределяет их, энтропия измеряет. А под всеми тремя проходит уже знакомая граница финитизации, и здесь она принимает особенно резкий вид.

Флагман части (комбинаторное лицо): конечная комбинаторика есть Element — она разрешима перечислением; бесконечная — есть предел-роль (role-limit).

Настоящая глава — о счёте. Её тезис: комбинаторные количества суть не готовые числа над готовыми множествами, а значения вычислимых процессов над конечными списками; а там, где счёт уходит в бесконечное, он переходит границу финитизации на сторону предела-роли.

Счёт как процесс

Факториал, биномиальные коэффициенты, числа сочетаний — это не «существующие» величины, а вычислимые функции: процессы, выдающие на конечном входе конечный результат¹. Перестановка здесь берётся в вычислительном режиме — как список без повторений; список первичен, а групповая (симметрическая) структура появляется позже как дополнительная роль-организация этих списков. «Множество перестановок» — лишь режим его рассмотрения. Сочетание — тоже режим: один и тот же конечный носитель считается то как упорядоченный (список), то как неупорядоченный (мультимножество-роль).

Базовые тождества подтверждают процессный характер счёта. Тождество Паскаля — это шаг рекурсии (значение строки треугольника через предыдущую), а сумма строки даёт степень двойки:

$$\sum _k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n,$$

и это доказанное равенство, а не наблюдение². Симметрия $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$ — это тождество двух способов считать одно и то же, ровно операциональная делимость: количество не зависит от того, какой ролью (выбранное / отброшенное) мы его считаем.

Принцип Дирихле — общий конечный двигатель

В основании дискретной математики лежит один скромный, но универсальный двигатель — принцип Дирихле (принцип «голубятни»): если $n+1$ предмет разложить по $n$ ящикам, какой-то ящик получит два. В нашей онтологии он конструктивен: на конечном носителе совпадение находится перечислением — это чистая Element-операция, без всякого обращения к бесконечности³.

Существенно, что это тот же двигатель, что работает в накачке автоматов и в китайской теореме об остатках: один конечный комбинаторный принцип, проявляющийся в разных доменах. Его бесконечный родственник (бесконечный ящик содержит бесконечно много предметов) живёт уже на стороне предела-роли — к нему мы вернёмся во флагмане главы.

Производящие функции как процессы

Производящая функция — мост между счётом и анализом, и в нашей онтологии она процесс: последовательность коэффициентов, разворачиваемая по запросу, а не завершённый аналитический объект (ровно «функция как процесс» Части XVI). Ярчайший пример — числа Каталана.

{ Каталановы числа допускают замкнутую форму через биномиальные коэффициенты,

$$C_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$$

(эквивалентно классической форме $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$), дающую $C_0,\dots =1,1,2,5,14,42,132,\dots$ — и это вычисляется, ступень за ступенью⁴. Но глубже лежит рекуррентность как процессное правило,

$$C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i},$$

которое отвечает формальному производящему уравнению $C(x)=1+xC(x{)}^2$ (на уровне коэффициентных процессов, не аналитического равенства) и доказано биекцией первого возврата на путях Дика — структурным, а не формульным аргументом⁵. Числа Моцкина получают свою замкнутую форму тем же приёмом⁶.}

Урок процессен: производящая функция не «есть» где-то целиком — она порождает свои коэффициенты правилом, и комбинаторное тождество есть доказанное свойство этого правила, а не совпадение готовых рядов.

Флагман: конечное — Element, бесконечное — предел-роль

Резче всего граница финитизации в комбинаторике видна на теории Рамсея. Число Рамсея $R(3,3)$ — наименьшее $N$, при котором всякая двуцветная раскраска рёбер полного графа на $N$ вершинах содержит одноцветный треугольник.

$R(3,3)=6$ — и это Element. Верхняя граница доказана перечислением: проверкой всех раскрасок $15$ рёбер полного графа на шести вершинах обнаруживается, что одноцветный треугольник возникает всегда⁷. Нижняя граница — свидетель: раскраска пятиугольника (пятивершинного цикла) без одноцветного треугольника⁸. Вместе они дают $R(3,3)=6$ — разрешимо, без всякой завершённой бесконечности.

Конечная теория Рамсея есть Element: число $R(3,3)$ найдено перечислением, сторона завершающегося процесса.

Бесконечная теория Рамсея — предел-роль. Бесконечная теорема Рамсея (во всякой двуцветной раскраске бесконечного полного графа есть бесконечное одноцветное подмножество) требует обозреть завершённый бесконечный объект и доказывается через лемму Кёнига / компактность — сторона предела-роли⁹. Формально здесь не доказывается сама бесконечная теорема Рамсея — фиксируется классификация: конечная версия есть Element (перебор и свидетель), бесконечная требует предельного / компактностного яруса. И здесь снова работает принцип Дирихле — но его бесконечная версия, которая и переводит счёт через границу.

Одна и та же теория Рамсея разрезана границей финитизации: конечное число $R(3,3)$ перечислимо (Element), бесконечный аналог — предел-роль. Двигатель один (Дирихле), сторон две.

E/R/R-разбор: комбинаторика как система

Разберём комбинаторику по E/R/R в порождающем порядке Rules $\to$ Roles $\to$ Elements.

{ Rules (L5). Удерживающие правила — правила счёта: произведение независимых выборов, сумма несовместных, рекурсия Паскаля, рекуррентность Каталана $C_{n+1}=\sum C_i{C}_{n-i}$. Над ними — общий конечный двигатель, принцип Дирихле. Эти правила стоят уровнем выше считаемых объектов и порождают количества.}

Roles (L4). Количество есть роль-мера конечного носителя. «Множество сочетаний» и «множество перестановок» — режимы (различные роли) одного списка, а не разные объекты (операциональная делимость). Производящая функция играет роль процесса-нити, порождающей коэффициенты; на бесконечной стороне счёт играет роль предела (бесконечный Рамсей).

Elements (L1 + P4). Носители — конечные списки: перестановки (списки без повторений), раскраски рёбер, решётчатые пути. Под P4 актуальны именно они; «множество всех раскрасок» конечного графа конечно и перечислимо (Element), тогда как бесконечный полный граф — предел-роль, не завершённый объект.

Проверка сформированности. Правила счёта — Rules; количество-как-мера и режимы — Roles; конечные списки — Elements; пересечений нет. Самоприменения нет: правило счёта стоит над списками и не есть один из них.

Что даёт разбор. Он показывает, почему дискретная математика так уютно ложится в P4: её носители конечны и перечислимы по построению, а количество есть значение процесса, а не свойство завершённого множества. И он называет единственную её границу: переход к завершённому бесконечному (бесконечный Рамсей, бесконечный Дирихле) есть сторона предела-роли — не запрет, а ровно та же граница финитизации, что несёт весь том.

Счёт устроен; в следующей главе те же конечные структуры обретают рёбра — мы переходим к теории графов: связности, циклам и дискретной кривизне, по-прежнему на 0-аксиомной, Element-стороне.

---

---

Часть: Часть XVII. Дискретная математика, вероятность, информация · Том: «Математика»

Навигация: ← Глава 6. Лестница реификации: число → функция → функционал — Часть XVI · Глава 2. Теория графов — связность, циклы, кривизна →

Footnotes

1. Факториал, биномиальные коэффициенты и тождество Паскаля формализованы как вычислимые функции с доказанными рекуррентными свойствами; машинно проверено, 0 аксиом. ↩

2. row_sum_pow2: сумма $n$-й строки треугольника Паскаля равна $2^n$; binomial_sym: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$. Машинно проверено, 0 аксиом. ↩

3. finite_pigeonhole_engine (в CombinatoricsExt); тот же конечный двигатель, что лемма о накачке регулярных языков (Часть XV) и китайская теорема об остатках (Часть XIII). Машинно проверено, 0 аксиом. ↩

4. catalan (в CombinatoricsExt) с конкретными значениями catalan_0..6 ($1,1,2,5,14,42,132$); ноль-индексация — техническая условность Rocq. Машинно проверено, 0 аксиом. ↩

5. Рекуррентность $C_{n+1}=\sum C_i{C}_{n-i}$ доказана через биекцию «первого возврата» на решётчатых путях; отражение Андре даёт независимую кросс-верификацию замкнутой формы. Машинно проверено, 0 аксиом. ↩

6. $M_n={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{2k}\right)C_k$ получено F-экстракцией с биномиальным преобразованием и коллапсом нечётных членов; машинно проверено, 0 аксиом. ↩

7. enum_forces_triangle: forallb mono15 (all_vectors 15) = true — все $2^{15}$ раскрасок проверены vm_compute; отсюда R33_upper: любая раскраска даёт треугольник. Чистая Element-операция: разрешимо конечным перебором, 0 аксиом. ↩

8. R33_lower: hasmono5 c5 = false — явная раскраска $c_5$ пятиугольника без одноцветного треугольника. Вместе с верхней границей: ramsey_3_3 ($R(3,3)=6$) и ramsey_decidable. ↩

9. ramsey_boundary фиксирует разрез: конечный Рамсей разрешим перечислением (Element), бесконечный — предел-роль (через König). Машинно проверено, 0 аксиом: утверждается разрез, а не бесконечная теорема. ↩