Непомеченные комбинаторные объекты
Каждый комбинаторный объект состоит из атомов.
\\
У атомов определен вес [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] является класс, состоящий из объектов A и B.
Обозначается
[math]C=A \cup B=A+B[/math].
При объединении комбинаторных классов одинаковые объекты считаются разными. Это делается так, чтобы не рассматривать внутреннюю структуру, а работать только с считающими послеовательностями и производящими функциями.
[math]c_n=a_n+b_n[/math]
[math]C(t)=A(t)+B(t)[/math]
Такие большие группы часто анализируют с помощью производящих функций. Один из популярных методов — метод символов [1]. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
| Утверждение: |
[math]Seq(A)(t)=\frac{1}{1-A(t)}[/math]. |
| [math]\triangleright[/math] |
|
[math]S_{0} = 1[/math], так как есть единственный способ составить пустую последовательность.
Докажем по индукции.
База [math]n = 1[/math].
- [math]S_{1}=w_{1} S_{0}=w_{1}[/math], что верно, так как единственный способ составить последовательность веса [math]1[/math] — это взять любой элемент веса [math]1[/math].
Переход.
- Пусть для [math]j \lt n[/math] верно. Докажем для [math]n[/math]. Возьмем произвольный элемент из [math]A[/math] веса [math]i \leqslant n[/math], и допишем его к последовательности элементов веса [math]n-i[/math]. Образуется новая последовательность веса [math]n[/math]. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса [math]n[/math] и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.
|
| [math]\triangleleft[/math] |
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
| [math]Seq(A)[/math] |
[math]\dfrac{1}{1-A(z)}[/math]
|
| [math]PSet(A)[/math] |
[math]\prod\limits_{n \geqslant 1}(1+z^{n})^{A_{n}}=\exp(-\sum\limits_{k \geqslant 1}\dfrac{(-1)^{k}A(z^{k})}{k})[/math]
|
| [math]MSet(A)[/math] |
[math]\prod\limits_{n \geqslant 1}\dfrac{1}{(1-z^{n})^{A_{n}}}=\exp(\sum\limits_{k \geqslant 1}\dfrac{A(z^{k})}{k})[/math]
|
| [math]Pair(A,B)[/math] |
[math]A(z)B(z)[/math]
|
| [math]Cycle(A)[/math] |
[math]\sum\limits_{n \geqslant 1}\dfrac{\phi(n)}{n}\ln\dfrac{1}{1 - A(z^n)}[/math], где [math]\phi(n)[/math] — функция Эйлера.
|
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — помеченные графы. С помеченными объектами используется экспоненциальная производящая функция [2]. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:
| [math]Seq(A)[/math] |
[math]\dfrac{1}{1-A(z)}[/math]
|
| [math]Pset(A)[/math] |
[math]\exp(A(z))[/math]
|
| [math]Pair(A,B)[/math] |
[math]A(z)B(z)[/math]
|
| [math]Cycle(A)[/math] |
[math]\ln\dfrac{1}{1-A(z)}[/math].
|
Ограниченные конструкции
Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например, [math]Seq_{k}(A)[/math] — [math]k[/math] компонентов).
Непосредственной формулой для производящих функций является диагональ [math]\Delta[/math] декартова произведения [3] [math]A \times A[/math], определяемая как [math]B \equiv \Delta(A \times A) : \{(a, a) \mid a \in A\}[/math]. Тогда имеет место соотношение [math]B(z)=A(z^{2})[/math].
Диагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из [math]A[/math], то есть к [math]P = PSet_{2}(A)[/math]. Прямое выражение выполняется следующим способом: неупорядоченная пара [math]\langle \alpha, \beta \rangle [/math] связана с двумя упорядоченными парами [math](\langle \alpha, \beta \rangle [/math] и [math]\langle \beta, \alpha \rangle )[/math], кроме тех случаев, когда [math]\alpha = \beta[/math], то есть когда пара лежит на диагонали декартова произведения. Другими словами, [math]PSet_{2}(A) + PSet_{2}(A) + \Delta(A \times A) \cong A \times A[/math].
Это, в свою очередь, означает что [math]2P(z) + A(z^{2}) = A(z)^{2}[/math]. Таким образом можно выразить [math]PSet_{2}(A)[/math]. Аналогично для [math]Seq_{2}(A)[/math], [math]MSet_{2}(A)[/math] и [math]Cycle_{2}(A)[/math]:
| [math]Seq_{2}(A)[/math] |
[math]A(z)^{2}[/math]
|
| [math]PSet_{2}(A)[/math] |
[math]\dfrac{A(z)^{2}}{2}-\dfrac{A(z^{2})}{2}[/math]
|
| [math]MSet_{2}(A)[/math] |
[math]\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}[/math]
|
| [math]Cycle_{2}(A)[/math] |
[math]\dfrac{A(z)^{2}}{2}+\dfrac{A(z^{2})}{2}[/math]
|
Аналогичные рассуждения можно провести и для больших [math]k[/math], однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов — теорема Пойа.
Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа [4]. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:
| [math]Seq_{k}(A)[/math] |
[math]A(z)^{k}[/math]
|
| [math]PSet_{k}(A)[/math] |
[math][u^{k}]\exp(-\sum\limits_{i=1}^{k}\dfrac{(-1)^{i}u^{i}A(z^{i})}{i})[/math]
|
| [math]MSet_{k}(A)[/math] |
[math][u^{k}]\exp(\sum\limits_{i=1}^{k}\dfrac{u^{i}A(z^{i})}{i})[/math]
|
| [math]Cycle_{k}(A)[/math] |
[math][u^{k}]\sum\limits_{i \geqslant 1}\dfrac{\phi(i)}{i}\ln\dfrac{1}{1 - u^{i}A(z^i)}[/math], где [math]\phi(n)[/math] — функция Эйлера.
|
