Обсуждение:Метод производящих функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (UI)
м (UI)
Строка 160: Строка 160:
 
* <tex dpi="350">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 \}</tex>
 
* <tex dpi="350">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 \}</tex>
  
<tex dpi="350">Set(A)=\prod_{\alpha \in A}(\varepsilon+\left \{ \alpha \right \})</tex>
+
<tex dpi="350">Set(A)=\prod_{\alpha \in A}\left(\varepsilon+\left \{ \alpha \right \}\right )</tex>
  
<tex dpi="350">Set(A)(t)=\prod_{\alpha \in A}(1+t^{w(\alpha)})=\prod_{n=0}^{\infty}(1+t^n)^{a_n}</tex>
+
<tex dpi="350">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}</tex>
  
 
==Мультимножества==
 
==Мультимножества==
Строка 170: Строка 170:
 
Как и с <tex dpi="350">Seq(A)</tex> существует ограничение на <tex dpi="350">A</tex>: <tex dpi="350">a_0=A(0)=0</tex>.
 
Как и с <tex dpi="350">Seq(A)</tex> существует ограничение на <tex dpi="350">A</tex>: <tex dpi="350">a_0=A(0)=0</tex>.
  
<tex dpi="350">MSet(A)=\prod_{\alpha \in A}(Seq(\left \{ \alpha \right \}))</tex>
+
<tex dpi="350">MSet(A)=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})</tex>
  
<tex dpi="350">MSet(A)(t)=\prod_{\alpha \in A}\frac{1}{1-t^{w(\alpha)}}=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n}\right)^{a_n}</tex>
+
<tex dpi="350">MSet(A)(t)=\prod_{\alpha \in A}\frac{1}{1-t^{w(\alpha)}}=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})(t)=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n}\right)^{a_n}</tex>
  
 
----
 
----

Версия 01:21, 24 июня 2020

Непомеченные комбинаторные объекты

Каждый комбинаторный объект состоит из атомов.

У атомов определен вес [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}\frac{1}{1-t^{w(\alpha)}}=\prod_{\alpha \in A}Seq(\left \{ \alpha \right \})(t)=\prod_{n=1}^{\infty}\left(\frac{1}{1-t^n}\right)^{a_n}[/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] функция Эйлера.