Непомеченные комбинаторные объекты
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес [math]w[/math].
[math]w(\bullet)=1[/math]
[math]w(\circ)=0[/math]
| Определение: |
| Считающей последовательностью называется последовательность [math]\left \{ a_0, a_1, ..., a_n \right \}[/math], где [math]a_i[/math] — количество объектов веса [math]i[/math]. |
Производящую функцию класса [math]A[/math] обозначим [math]A(t)=\sum_{i=0}^{\infty }a_i t^i[/math].
| Определение: |
| Комбинаторным объектом [math]Z[/math] называется комбинаторный объект, состоящий из одного атома веса [math]1[/math].
[math]Z=\left \{ \bullet \right \}[/math] |
Считающая последовательность: [math]\left \{ 0, 1, 0, ..., 0 \right \}[/math].
Производящая функция последовательности: [math]Z(t)=t[/math].
| Определение: |
| Комбинаторным объектом [math]\varepsilon[/math] называется комбинаторный объект, состоящий из одного атома веса [math]0[/math].
[math]\varepsilon=\left \{ \circ \right \}[/math]. |
Считающая последовательность: [math]\left \{ 1, 0, ..., 0 \right \}[/math].
Производящая функция последовательности: [math]\varepsilon(t)=1[/math].
| Определение: |
| Комбинаторным классом [math]A[/math] называется множество комбинаторных объектов, обладающих каким-то свойством. |
Объединение комбинаторных классов
| Определение: |
| Объединением комбинаторных классов [math]A[/math] и [math]B[/math] называется комбинаторный класс [math]C=A \cup B=A+B=\left \{ c \mid c \in A \vee c \in B \right \}[/math]. |
При объединении комбинаторных классов одинаковые объекты разных классов считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру классов, а работать только со считающими последовательностями и производящими функциями.
[math]c_n=a_n+b_n[/math]
[math]C(t)=A(t)+B(t)[/math]
Пары комбинаторных классов (декартово произведение комбинаторных классов)
| Определение: |
| Парой комбинаторных классов [math]A[/math] и [math]B[/math] называется комбинаторный класс [math]C=Pair(A, B)=A \times B=\left \{ (\alpha, \beta) \mid \alpha \in A, \beta \in B \right \}[/math]. |
[math]w\left ( \left ( \alpha, \beta \right ) \right )=w(\alpha) + w(\beta)[/math]
[math]c_n=\sum_{k=0}^{n}a_k b_{n-k}[/math]
| Утверждение: |
[math]C(t)=A(t) \cdot B(t)[/math] |
| [math]\triangleright[/math] |
|
Верно, потому что коэффициенты производящей функции описываются описываются равенством выше) |
| [math]\triangleleft[/math] |
Последовательности комбинаторных классов
| Определение: |
| Последовательностью [math]k[/math] объектов из [math]A[/math] называется [math]B=Seq_k(A)=\left \{ (\alpha_1, ..., \alpha_k) \mid \alpha_i \in A \right \}[/math].
[math]w(\left \{ (\alpha_1, ..., \alpha_k) \mid \alpha_i \in A \right \})=\sum_{i=0}^{k}\alpha_i[/math] |
| Утверждение: |
[math]Seq_k(A)(t)=A(t)^k[/math] |
| [math]\triangleright[/math] |
|
Докажем по индукции:
База [math]k=1[/math].
- Для [math]k=1[/math] верно, потому что [math]Seq_1(A)=A \Rightarrow Seq_1(A)(t)=A(t)=A(t)^1[/math].
Переход.
- Пусть для [math]k=n[/math] верно [math]Seq_n(A)(t)=A(t)^n[/math]. Докажем для
[math]k=n+1[/math]: [math]Seq_{n+1}(A)(t)=A(t)^{n+1}[/math]. Рассмотрим [math]Seq_{n+1}(A)[/math] как [math]Pair(Seq_n(A), A)[/math]. Тогда [math]Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}[/math]. |
| [math]\triangleleft[/math] |
| Определение: |
| Последовательностью (всех возможных длин) объектов из [math]A[/math] называется [math]B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)[/math]. |
| Утверждение: |
[math]Seq(A)(t)=\frac{1}{1 - A(t)}[/math] |
| [math]\triangleright[/math] |
|
[math]Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}[/math] (Геометрическая прогрессия) |
| [math]\triangleleft[/math] |
Ограничение: [math]a_0=0[/math]. Этому есть как техническое, так и комбинаторное объяснение.
- Технически, если [math]a_0\gt 1[/math], то мы будем делить на отрицательное число; если [math]a_0=1[/math], то на функцию, у которой свободный член [math]0[/math], — что формализм производящих функций сделать не позволяет.
- Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
[math]A(0)=0[/math]
Примеры:
- Последовательночти из не менее 3 объектов:
- [math]Seq_{\geq 3}=Pair(Seq_3(A), Seq(A))=Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A)[/math]
- [math]Seq_{\geq 3}(t)=Pair(Seq_3(A), Seq(A))(t)=A(t)^3 \cdot \frac{1}{1-A(t)}=\frac{A(t)^3}{1-A(t)}=(Seq(A)-Seq_0(A)-Seq_1(A)-Seq_2(A))(t)=\frac{1}{1-A(t)}-0-A(t)-A(t)^2[/math]
- Последовательности чётной длины:
- [math]Seq_{\vdots 2}(A)=Seq(Pair(A, A))[/math]
- [math]Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A(t)^2}[/math]
Комбинаторный объект "Натуральные числа"
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Считающая последовательность: [math]\left \{ 0, 1, ..., 1 \right \}[/math]
[math]w(n)=n[/math]
[math]c_n=\left\{\begin{matrix}
0, n=0\\
1, n\gt 0
\end{matrix}\right.[/math]
[math]I(t) = \frac{t}{1 - t}[/math]
[math]Seq(I)[/math] — упорядоченное разбиение на слагаемые.
[math]Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}[/math]
[math]\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix}
2 ^ n - 2 ^ {n - 1} = 2 ^ {n - 1}, n \gt 0
\\
1, n = 0
\end{matrix}\right.[/math]
Множества
Множества [math]Set(A)[/math] — последовательности без повторений и порядка элементов.
Пример:
- [math]A = \left \{ \alpha, \beta, \gamma \right \}[/math]
- [math]Set(A) = \left \{ \varnothing, \left \{ \alpha \right \}, \left \{ \beta\right \}, \left \{ \gamma \right \}, \left \{ \alpha, \beta\right \}, \left \{ \alpha, \gamma \right \}, \left \{ \beta, \gamma \right \}, \left \{ \alpha, \beta, \gamma \right \} \right \}[/math]
[math]Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )[/math]
[math]Set(A)(t)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )(t)=\prod_{\alpha \in A}(1+t^{w(\alpha)})=\prod_{n=0}^{\infty}(1+t^n)^{a_n}[/math]
Мультимножества
Мультимножества [math]MSet(A)[/math] — последовательности с повторениями, но без порядка элементов.
Как и с [math]Seq(A)[/math] существует ограничение на [math]A[/math]: [math]a_0=A(0)=0[/math].
[math]MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})[/math]
[math]MSet(A)(t)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})(t)=\prod_{\alpha \in A}\frac{1}{1-t^{w(\alpha)}}=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n}\right)^{a_n}[/math]
Помеченные объекты
Экспоненциальные функции
| Обычная |
[math]ogf(t) = \sum_{i=0}^{\infty}a_it^i[/math], где [math]\left \{ a_i \right \}[/math] — считающая последовательность
|
| Экспоненциальная |
[math]egf(t) = \sum_{i=0}^{\infty}\frac{a_it^i}{n!}[/math]
|
Помеченные комбинаторные объекты отличаются тем, что все атомы имеет разные значки, а именно — если вес объекта [math]n[/math], то все атомы пронумерованы различными целыми числами от [math]1[/math] до [math]n[/math].
[math]w(①)=1[/math]
[math]w(\circ)=0[/math]
Экспоненциальной роизводящую функцию класса [math]A[/math] обозначим [math]A(t)=\sum_{i=0}^{\infty }a_i t^i[/math].
| Определение: |
| Комбинаторным объектом [math]Z[/math] называется комбинаторный объект, состоящий из одного атома веса [math]1[/math].
[math]Z=\left \{ ① \right \}[/math] |
Считающая последовательность: [math]\left \{ 0, 1, 0, ..., 0 \right \}[/math].
Производящая функция последовательности: [math]Z(t)=t[/math].
| Определение: |
| Комбинаторным объектом [math]\varepsilon[/math] называется комбинаторный объект, состоящий из одного атома веса [math]0[/math].
[math]\varepsilon=\left \{ \circ \right \}[/math]. |
Считающая последовательность: [math]\left \{ 1, 0, ..., 0 \right \}[/math].
Производящая функция последовательности: [math]\varepsilon(t)=1[/math].
