Конструирование комбинаторных объектов и их подсчёт

Последовательности (Seq)

Утверждение:

Пусть $A=\{a_{1},a_{2}, \ldots ,a_{z}\}$ — множество из различных объектов, $S=Seq(A)$ — множество всех последовательностей из элементов $A$, $W=\{w_{1},w_{2}, \ldots ,w_{l}\}$ — количество объектов веса от $1$ до $l$. Мы считаем, что нет объектов веса $0$, так как в противном случае существует бесконечное количество последовательностей любого веса. Тогда, количество последовательностей веса $n$ можно вычислить как $S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}$. Причем $S_{0} = 1$, так как есть единственный способ составить пустую последовательность.

$\triangleright$

Докажем по индукции. База $n = 1$. $S_{1}=w_{1} S_{0}=w_{1}$, что верно, так как единственный способ составить последовательность веса $1$ — это взять любой элемент веса $1$. Переход. Пусть для $j \lt n$ верно. Докажем для $n$. Возьмем произвольный элемент из $A$ веса $i \leqslant n$, и допишем его к последовательности элементов веса $n-i$. Образуется новая последовательность веса $n$. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса $n$ и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.

$\triangleleft$

Подсчет битовых векторов длины $n$

Пусть $A=\{0, 1\}$, $W=\{2, 0 \ldots 0\}$ $S=Seq(A)$ — множество всех битовых векторов, $S_{0}=1$.

Тогда, $S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}=2S_{n-1}=2^{n}$.

Подсчет Seq из маленьких и больших элементов

Пусть $A=\{1, 2\}$, $W=\{1, 1, 0 \ldots 0\}$, $S=Seq(A)$ — множество всех последовательностей из маленьких и больших элементов, $S_{0}=1$, $S_{1}=1$.

Тогда, $S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=S_{n-1}+S_{n-2}=F_{n}$, где $F_{n}$ — $n$-ое число Фибоначчи .

Подсчет подвешенных непомеченных деревьев с порядком на детях

Пусть $T_{n}$ — количество таких деревьев с $n$ вершинами, $T_{0} = 1$. $S=Seq(A)$ — множество всех последовательностей из данных деревьев. $S_{n}$ — количество последовательностей с суммарным количество вершин $n$. Чтобы получить дерево из $n$ вершин, достаточно взять $1$ вершину, и подвесить к ней последовательность деревьев с суммарным количеством вершин $n-1$. Тогда:

$T_{n}=S_{n-1}$.

$S_{n}=\sum_{i=1}^{n} T_{i} S_{n-i}=\sum_{i=1}^{n} S_{i-1} S_{n-i}=\sum_{i=0}^{n-1} S_{i} S_{n-i-1}=C_{n}$, где $C_{n}$ — $n$-ое число Каталана.

Множества (PSet)

Утверждение:

Пусть $A=\{a_{1},a_{2}, \ldots ,a_{z}\}$ — множество из различных объектов, $P=PSet(A)$ — множество всех множеств, составленных из элементов $A$, $W=\{w_{1},w_{2}, \ldots ,w_{l}\}$ — количество объектов веса от $1$ до $l$. Для простоты считаем что нет объектов веса $0$. Тогда количество множеств суммарного веса $n$ можно вычислить как $P_{n}=p_{n, n}$, где $p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} p_{n-ik, k-1}$ — количество таких множеств, которые содержат объекты, вес которых не больше чем $k$. Причем $p_{0, i} = 1$, так как не набирать никакой вес есть один способ, а $p_{i, 0} = 0$, $i \ne 0$, так как нельзя набрать положительный вес из ничего.

$\triangleright$

Изначально у нас есть только пустое множество веса $0$. Рассмотрим очередной этап вычисления $p_{n,k}$. Для данных $n$ и $k$ у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от $0$ до $\lfloor \frac{n}{k} \rfloor$ элементов веса $k$ (при условии, что столько различных элементов имеется) в данное множество. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше $k$ (чтобы избежать повторений) суммарного веса $n-ik$, где $i$ — количество элементов веса $k$ которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле.

$\triangleleft$

Количество PSet из элементов 0 и 1

Пусть $A=\{0, 1\}$, $P=PSet(A)$ — множество всех множеств из $A$, $W=\{2, 0 \ldots 0\}$, $w_{0} = 1$. Тогда $P_{n}=p_{n, n}$, где $p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} p_{n-ik, k-1}$.

$P_{0}=p_{0, 0} = 1$.

$P_{1}=p_{1, 1} = p_{1, 0} + 2p_{0, 0} = 2p_{0, 0} = 2$.

$P_{2}=p_{2, 2} = p_{2, 1} + 0 \cdot p_{0, 1} = p_{2, 0} + 2p_{1, 0} + p_{0, 0}= p_{0, 0} = 1$.

${P_{3}=p_{3, 3} = p_{3, 2} + 0 \cdot p_{0, 2} = p_{3, 1} + 0 \cdot p_{0, 1} = p_{3, 0} + 2p_{2, 0} + 0 \cdot p_{1, 0} + 0 \cdot p_{0, 0}= 0}$.

Для $n \gt 2$, $P_{n} = 0$ .

$\{\}$

$\{0\}, \{1\}$

$\{0, 1\}$

Количество разбиений на слагаемые

Пусть $A=\mathbb{N}$, $P=PSet(A)$ — множество всех разбиений на слагаемые, $W=\{1 \ldots 1\}$, $w_{0} = 1$. Тогда,

$P_{n}=p_{n, n}$, где $p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} p_{n-ik, k-1} = p_{n, k-1} + p_{n - k, k}$, что, как несложно заметить, соответствует формуле, полученной методом динамического программирования.

Мультимножества (MSet)

Утверждение:

Пусть $A=\{a_{1},a_{2}, \ldots ,a_{z}\}$ — множество из различных объектов, $M=MSet(A)$ — множество всех мультимножеств из элементов $A$, $W=\{w_{1},w_{2}, \ldots ,w_{k}\}$ — количество объектов веса $\{1 \ldots k\}$. Тогда количество мультимножеств из объектов суммарного веса $n$ можно вычислить как $M_{n}=m_{n, n}$, где $m_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} m_{n-ik, k-1}$ — количество таких мультимножеств, которые содержат объекты, вес которых не больше чем $k$.

Количество MSet из элементов 0 и 1

Пусть $A=\{0, 1\}$, $S=PSet(A)$ — множество всех множеств из $A$, $W=\{2, 0 \ldots 0\}$, $w_{0} = 1$.

Тогда, $M_{n}=m_{n, n}$, где $s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}$

$M_{0}=m_{0, 0} = 1$.

$M_{1}=m_{1, 1} = m_{1, 0} + 2m_{0, 0} = 2m_{0, 0} = 2$.

$M_{2}=m_{2, 2} = m_{2, 1} + 0 \cdot m_{0, 1} = m_{2, 0} + 2m_{1, 0} + 3m_{0, 0}= 3m_{0, 0} = 3$.

$M_{3}=m_{3, 3} = m_{3, 2} + 0 \cdot m_{0, 2} = m_{3, 1} + 0 \cdot m_{0, 1} = m_{3, 0} + 2m_{2, 0} + 3m_{1, 0} + 4m_{0, 0}= 4m_{0, 0} = 4$.

$\{\}$

$\{0\}, \{1\}$

$\{0, 0\}, \{0, 1\}, \{1, 1\}$

$\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}$

${M_{n}=m_{n, n} = m_{n, n-1} + 0 \cdot m_{0, n-1} = m_{n, n-2} + 0 \cdot m_{0, n-2} = \ldots = m_{n, 0} + 2m_{n - 1, 0} + \ldots + nm_{1, 0} + (n+1) m_{0,0} = (n + 1) m_{0,0} = n+1}$.

Подсчет подвешенных непомеченных деревьев без порядка на детях

Пусть $T_{n}$ — количество таких деревьев с $n$ вершинами, $T_{0} = 1$. $F=MSet(T)$ — множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. $F_{n}=f_{n,n}$ — количество лесов с суммарным количество вершин $n$. $f_{n, k}$ — количество таких лесов из $n$ вершин, что деревья в них содержат не более чем $k$ вершин. Чтобы получить дерево из $n$ вершин, достаточно взять $1$ вершину и подвесить к ней лес деревьев с суммарным количеством вершин $n-1$. Тогда:

$T_{n}=F_{n-1}$.

$F_{n}=f_{n, n}$.

$f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}$.

Количество таких деревьев с $n$ вершинами образуют последовательность $1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots$

Пары (Pair)

Утверждение:

Пусть $A=\{a_{1},a_{2}, \ldots ,a_{z}\}$, $B=\{b_{1},b_{2}, \ldots ,b_{m}\}$ — множества из различных объектов, $D=Pair(A, B)$ — множество всех пар объектов, составленных из элементов $A$ и $B$. $W=\{w_{1},w_{2}, \ldots ,w_{k}\}$ — количество объектов веса $\{1 \ldots k\}$, составленных из элементов $A$, а $U=\{u_{1},u_{2}, \ldots ,u_{k}\}$ — соответственно для $B$. Тогда количество пар из объектов суммарного веса $n$ можно вычислить как $D_{n}=\sum_{i=0}^{n}w_{i}u_{n-i}$.

Количество подвешенных неполных двоичных деревьев

Пусть $T_{n}$ — количество таких деревьев с $n$ вершинами, $T_{0} = 1$. $D=Pair(T, T)$ — множество всех пар из данных деревьев. Чтобы получить двоичное дерево из $n$ вершин, достаточно взять $1$ вершину и подвесить к ней левого и правого сына с суммарным количеством вершин $n-1$. Тогда:

$T_{n}=D_{n-1}=\sum_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}$, где $C_{n}$ — $n$-ое число Каталана.

Циклы (Cycle)

Утверждение:

Пусть $A=\{a_{1},a_{2}, \ldots ,a_{z}\}$ — множество из различных объектов, $C=Cycle(A)$ — множество всех циклов из элементов $A$, $W=\{w_{1},w_{2}, \ldots ,w_{m}\}$ — количество объектов веса $\{1 \ldots m\}$. Тогда количество циклов веса $n$ можно вычислить как $C_{n}=\sum_{s=1}^{n}c_{n, s}$, где $c_{n,s}$ — количество циклов веса $n$ длины $s$. По лемме Бёрнсайда $c_{n,s} =\sum_{i=0}^{s-1}\dfrac{|St(\vec{i})|}{s}$, где $|St(\vec{i})|$ — количество стабилизаторов для циклического сдвига на $i$ .

Найдем $|St(\vec{i})|=z_{n,s,i}$ в общем случае.

Пусть $g=\mathrm{gcd}(s,i)$ — наибольший общий делитель$(s, i)$. Заметим, что в $i$-ой перестановке на $j$-ой позиции стоит элемент $(i + j)\bmod s$. Также, заметим, что элемент $a$ переходит в элемент $a + in$, где $i = 1, 2, \ldots k$. Из этого следует, что длина цикла для $i$-ой перестановки равна $\dfrac{\mathrm{lcm}(s, i)}{i} = \dfrac{s}{g}$, где $\mathrm{lcm}(s, i)$ — наименьшее общее кратное$(s, i)$.

Также заметим, что если вес $n$ нельзя равномерно распределить по всей длине цикла, то стабилизатор равен $0$.

$z_{n, s, i} = \left \{\begin{array}{ll} 0, & n \bmod \frac{s}{g} \neq 0 \\ b_{\frac{ng}{s}, g}, & n \bmod \frac{s}{g} = 0 \end{array} \right.$

Где $b_{n,k}$ — число способов упорядочить набор из $k$ элементов суммарного веса $n$ и

$b_{n,k}=\sum_{i=1}^{n}w_{i}b_{n-i, k-1}$, причем $b_{n,1}=w_{n}$.

Задача об ожерельях

Решим данным способом задачу об ожерельях. Пусть необходимый вес $n$ — это количество бусинок, а $k$ — количество цветов. Причем каждая бусинка весит $1$. То есть $W=\{k, 0 \ldots 0\}$.

$C_{n}=\sum_{s=1}^{n}c_{n,s}=c_{n,n}$ так как невозможно набрать вес $n$ менее, чем $n$ бусинами при весе бусин $1$.

$c_{n,n}=\sum_{i=0}^{n-1}\dfrac{|St(\vec{i})|}{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}|St(\vec{i})|=\dfrac{1}{n}\sum_{i=0}^{s-1}b_{\mathrm{gcd}(n,i),\mathrm{gcd}(n,i)}$. Поскольку все бусины имеют одинаковый вес $1$, то $b_{n,k} \neq 0$

В итоге, $C_{n}=\dfrac{1}{n}\sum_{i=0}^{s-1}k^{\mathrm{gcd}(n,i)}$.

Производящие функции

Для анализа свойств таких больших групп часто применяют метод производящих функций. Рассмотренные классы имеют следующие производящие функции:

$Seq(A)$	$\dfrac{1}{1-A(z)}$
$Pset(A)$	$\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}A(z^{k})}{k})$
$Mset(A)$	$\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})$
$Pair(A,B)$	$A(z)B(z)$
$Cycle(A)$	$\ln\dfrac{1}{1-A(z)}$

См.также

• Лемма Бёрнсайда и Теорема Пойа
• Числа Каталана
• Генерация комбинаторных объектов в лексикографическом порядке

Источники информации

• Philippe Flajolet, Robert Sedgewick, Analytic Combinatorics, 15-92, 2008
• Online Course Materials from Robert Sedgewick
• Wikipedia — Generating function