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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
В комбинаторике, особенно в аналитической комбинаторике, [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символьный метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения формул их [[Производящая функция|производящих функций]]. Этот метод в основном связан с [https://en.wikipedia.org/wiki/Philippe_Flajolet Филиппом Флайоле] и подробно описан в части A его книги с [https://ru.wikipedia.org/wiki/Седжвик,_Роберт Робертом Седжвиком] "Аналитическая комбинаторика"<ref>[https://en.wikipedia.org/wiki/Analytic_Combinatorics "Аналитическая комбинаторика"]</ref>.
+
В [https://ru.wikipedia.org/wiki/Комбинаторика комбинаторике], особенно в аналитической комбинаторике, [https://en.wikipedia.org/wiki/Symbolic_method_(combinatorics) символический метод] - это метод подсчета [https://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты комбинаторных объектов]. Он использует внутреннюю структуру объектов для получения формул их [[Производящая функция|производящих функций]]. Этот метод в основном связан с [https://en.wikipedia.org/wiki/Philippe_Flajolet Филиппом Флайоле] и подробно описан в части A его книги с [https://ru.wikipedia.org/wiki/Седжвик,_Роберт Робертом Седжвиком] "Аналитическая комбинаторика"<ref>[https://en.wikipedia.org/wiki/Analytic_Combinatorics "Аналитическая комбинаторика"]</ref>.
  
  
Строка 12: Строка 12:
 
Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.
 
Считающей последовательностью называется последовательность <tex dpi="130">\left \{ a_0, a_1, ..., a_n \right \}</tex>, где <tex dpi="130">a_i</tex> {{---}} количество объектов веса <tex dpi="130">i</tex>.
 
}}
 
}}
 
Обозначим <tex dpi="350">[t_n]</tex> как оператор взятия <tex dpi="350">n</tex>-того коэффициента производящей функции.
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Комбинаторным классом <tex dpi="130">A</tex> называется множество комбинаторных объектов, обладающих каким-то свойством.
+
Комбинаторным классом <tex dpi="130">A</tex> называется [https://ru.wikipedia.org/wiki/Множество множество] комбинаторных объектов, обладающих каким-то свойством.
 
}}
 
}}
 
 
=Непомеченные комбинаторные объекты=
 
=Непомеченные комбинаторные объекты=
  
Строка 49: Строка 46:
  
 
Считающая последовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.
 
Считающая последовательность: <tex dpi="130">\left \{ 1, 0, ..., 0 \right \}</tex>.
 +
  
 
Производящая функция последовательности: <tex dpi="130">\varepsilon(t)=1</tex>.
 
Производящая функция последовательности: <tex dpi="130">\varepsilon(t)=1</tex>.
Строка 56: Строка 54:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Объединением комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=A \cup B=A+B</tex>, состоящий из элементов обоих классов, причем равные объекты разных классов объявляются разными.
+
Объединением комбинаторных классов <tex dpi="350">A</tex> и <tex dpi="350">B</tex> называется комбинаторный класс <tex dpi="350">C=A \cup B=A+B</tex>, состоящий из элементов обоих классов, причем равные объекты разных подмножеств объявляются разными.
 
}}
 
}}
 
Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
 
Целью этого уточнения является возможность работать только со считающими последовательностями и производящими функциями.
Строка 64: Строка 62:
 
<tex dpi="350">C(t)=\left ( \sum_{i=0}^{\infty}a_i \cdot t^i \right ) + \left ( \sum_{i=0}^{\infty}b_i \cdot t^i \right ) = \sum_{i=0}^{\infty}(a_i + b_i)\cdot t^i =A(t)+B(t)</tex>
 
<tex dpi="350">C(t)=\left ( \sum_{i=0}^{\infty}a_i \cdot t^i \right ) + \left ( \sum_{i=0}^{\infty}b_i \cdot t^i \right ) = \sum_{i=0}^{\infty}(a_i + b_i)\cdot t^i =A(t)+B(t)</tex>
  
==Пары комбинаторных классов (декартово произведение комбинаторных классов)==
+
==Пары комбинаторных классов ([https://ru.wikipedia.org/wiki/Прямое_произведение декартово произведение] комбинаторных классов)==
  
 
{{Определение
 
{{Определение
Строка 93: Строка 91:
 
{{Утверждение
 
{{Утверждение
 
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex>
 
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex>
|proof=Докажем по индукции:
+
|proof=Докажем по [[Математическая индукция|индукции]]:
  
 
'''База <tex dpi="350">k=1</tex>'''.
 
'''База <tex dpi="350">k=1</tex>'''.
Строка 99: Строка 97:
  
 
'''Переход'''.
 
'''Переход'''.
:Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для <tex dpi="350">k=n+1</tex>:
+
:Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для  
<tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}</tex>.
+
<tex dpi="350">k=n+1</tex>: <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^n \cdot A(t)=A(t)^{n+1}</tex>.
 
}}
 
}}
  
Строка 107: Строка 105:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Последовательностью объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</tex>.
+
Последовательностью, или базовой последовательностью, объектов из <tex dpi="350">A</tex> называется <tex dpi="350">B=Seq(A)=\sum_{i=0}^{\infty}Seq_i(A)</tex>.
 
}}
 
}}
  
Строка 113: Строка 111:
 
{{Утверждение
 
{{Утверждение
 
|statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex>
 
|statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex>
|proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> (Геометрическая прогрессия)
+
|proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> ([https://ru.wikipedia.org/wiki/Геометрическая_прогрессия Геометрическая прогрессия])
 
}}
 
}}
  
Строка 120: Строка 118:
 
* Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет.
 
* Технически, если <tex dpi="350">a_0>1</tex>, то мы будем делить на отрицательное число; если <tex dpi="350">a_0=1</tex>, то на функцию, у которой свободный член <tex dpi="350">0</tex>, {{---}} что формализм производящих функций сделать не позволяет.
 
* Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
 
* Комбинаторное объяснение заключается в том, что если объектов веса ноль более 0, то мы можем создать бесконечное количество последовательностей веса 0 (комбинируя такие объекты), а мы хотим работать с конечными количествами последовательностей.
 +
  
 
====Примеры====
 
====Примеры====
Строка 129: Строка 128:
 
** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t^2\right )}</tex>
 
** <tex dpi="350">Seq_{\vdots 2}(A)(t)=Seq(Pair(A, A))(t)=\frac{1}{1-A\left (t^2\right )}</tex>
  
==Комбинаторный класс "Натуральные числа"==
+
==Комбинаторный класс "[[Натуральные числа]]"==
  
 
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
 
Вес числа равен его значению. Каждое натуральное число встречается 1 раз.
Строка 138: Строка 137:
  
 
Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>.
 
Класс "Натуральные числа" принято обозначать <tex dpi="350">I</tex>.
Считающая последовательность {{---}}
+
 
 
<tex dpi="350">c_n=\left\{\begin{matrix}
 
<tex dpi="350">c_n=\left\{\begin{matrix}
 
0, n=0\\  
 
0, n=0\\  
Строка 155: Строка 154:
 
===Применение===
 
===Применение===
  
<tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение натуральных чисел на слагаемые]].
+
<tex dpi="350">Seq(I)</tex> {{---}} упорядоченное [[Нахождение количества разбиений числа на слагаемые|разбиение на слагаемые]].
  
Тогда производящая функция {{---}} <tex dpi="350">Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}</tex>
+
<tex dpi="350">Seq(I)(t)=\frac{1}{1-\frac{t}{1-t}}=\frac{1-t}{1-2t}=\frac{1}{1-2t}-\frac{t}{1-2t}</tex>
  
 
<tex dpi="350">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix}
 
<tex dpi="350">\left [ t^n \right ] \frac{1-t}{1-2t} = \left\{\begin{matrix}
Строка 163: Строка 162:
 
\\  
 
\\  
 
1, n = 0
 
1, n = 0
\end{matrix}\right.</tex>, потому что <tex dpi="350">\frac{1}{1-2t}</tex> соответсвует ряду степеней <tex dpi="350">2</tex>, а <tex dpi="350">\frac{1}{1-2t}</tex> {{---}} ряду <tex dpi="350">2^{x-1}</tex>.
+
\end{matrix}\right.</tex>
  
 
==Множества==
 
==Множества==
Строка 217: Строка 216:
  
 
<tex dpi="350">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}</tex>
 
<tex dpi="350">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}</tex>
 +
 +
==[http://en.wikipedia.org/wiki/Cyclic_order Циклы]==
 +
 +
===Ограниченная конструкция===
 +
 +
{{Определение
 +
|definition=Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</tex>.
 +
}}
 +
 +
===Неограниченная конструкция===
 +
 +
{{Определение
 +
|definition=Циклы <tex dpi="350">A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)</tex>.
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
'''почему?''' <tex dpi="350">Cycle(A)(t)=\sum_{n \geq 1} \frac{\phi(n)}{n} ln \left ( \frac{1}{1-A(z^n)} \right )</tex>, где <tex dpi="350">\phi(n)</tex> {{---}} [[функция Эйлера]].
 +
}}
  
 
=Помеченные объекты=
 
=Помеченные объекты=
Строка 231: Строка 249:
 
|}
 
|}
  
Далее под производящей функцией будет подразумеваться и использоваться экспоненциальная производящая функция, потому что формулы с ней более просты в работе.
+
Далее под производящей функцией будет подразумеваться экспоненциальная производящая функция.
  
 
==Свойства экспоненциальной производящей функции==
 
==Свойства экспоненциальной производящей функции==
Строка 244: Строка 262:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
<tex dpi="350">\left (\int A(t) \right )'=A(t)</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref>
+
<tex dpi="350">\left (\int A(t) \right )'=A(t)</tex>
 
}}
 
}}
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex dpi="350">A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\{ a_0, a_1, ..., a_n, ... \}</tex>, тогда <tex dpi="350">\int A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ 0, a_0, a_1, a_2, ..., a_n, ... \}</tex><ref>[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e&t=2131 Youtube {{---}} Помеченные объекты]</ref>
+
Пусть <tex dpi="350">A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">\{ a_0, a_1, ..., a_n, ... \}</tex>, тогда <tex dpi="350">\int A(t)</tex> {{---}} экспоненциальная производящая функция последовательности <tex dpi="350">B=\{ 0, a_0, a_1, a_2, ..., a_n, ... \}</tex>
 
}}
 
}}
  
Строка 308: Строка 326:
 
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе <tex dpi="350">A \star B</tex> будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-4-5.png|50px]]<tex dpi="350">)</tex>, но не будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-5-4.png|50px]]<tex dpi="350">)</tex>.
 
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 1 способ занумеровать. Таким образом, в классе <tex dpi="350">A \star B</tex> будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-4-5.png|50px]]<tex dpi="350">)</tex>, но не будет лежать <tex dpi="350">(</tex> [[Файл:1-2.png|50px]] <tex dpi="350">,</tex>[[Файл:3-5-4.png|50px]]<tex dpi="350">)</tex>.
  
<tex dpi="350">c_n=\sum_{k=0}^na_kb_{n-k}\binom{n}{k}=\sum_{k=0}^na_kb_{n-k}\frac{n!}{k!(n-k)!}=n! \cdot \sum_{k=0}^n\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}</tex>
+
<tex dpi="350">c_n=\sum_{k=0}^na_kb_{n-k}\binom{n}{k}</tex>''([https://ru.wikipedia.org/wiki/Сочетание Сочетания])''<tex dpi="350">=\sum_{k=0}^na_kb_{n-k}\frac{n!}{k!(n-k)!}=n! \cdot \sum_{k=0}^n\frac{a_k}{k!}\frac{b_{n-k}}{(n-k)!}</tex>
  
 
<tex dpi="350">C(t)=A(t) \cdot B(t)</tex>
 
<tex dpi="350">C(t)=A(t) \cdot B(t)</tex>
Строка 318: Строка 336:
 
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:  
 
Последовательности длины <tex dpi="350">k</tex>, как и в непомеченных комбинаторных объектах, формируются следующим образом:  
 
* Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>
 
* Cоставляются все возможные последовательности из <tex dpi="350">k</tex> объектов из <tex dpi="350">A</tex>
* Перенумеруются всеми возможными способами.
+
* Затем они всеми возможными способами их перенумеруются.
  
 
Их принято обозначать <tex dpi="350">Seq_k(A)</tex>.
 
Их принято обозначать <tex dpi="350">Seq_k(A)</tex>.
Строка 328: Строка 346:
 
===Неограниченная конструкция===
 
===Неограниченная конструкция===
  
Определение <tex dpi="350">Seq(A)</tex> не изменилось.
+
Определение <tex dpi="350">Seq(A)</tex> и соответствующая производящая функция не изменились.
 
 
{{Утверждение
 
|statement=<tex dpi="350">Seq(A)(t)=\frac{1}{1 - A(t)}</tex>
 
|proof=<tex dpi="350">Seq(A)(t)=\sum_{i=0}^{\infty}Seq_i(A)(t)=\sum_{i=0}^{\infty}A(t)^i=\frac{1}{1 - A(t)}</tex> (Геометрическая прогрессия)
 
}}
 
  
 
Действует ограничение на <tex dpi="350">b_0=B(0)=0</tex>, как и на <tex dpi="350">Seq(A)</tex> и <tex dpi="350">MSet(A)</tex> в формализме непомеченных объектов.
 
Действует ограничение на <tex dpi="350">b_0=B(0)=0</tex>, как и на <tex dpi="350">Seq(A)</tex> и <tex dpi="350">MSet(A)</tex> в формализме непомеченных объектов.
Строка 339: Строка 352:
 
====Пример====
 
====Пример====
  
'''Перестановки'''
+
'''[https://ru.wikipedia.org/wiki/Перестановка Перестановки]'''
 
* <tex dpi="350">P=Seq(Z)</tex>
 
* <tex dpi="350">P=Seq(Z)</tex>
 
* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>.
 
* Экспоненциальной производящей функцией является <tex dpi="350">P(t)=\frac{1}{1-t}</tex>.
Строка 352: Строка 365:
 
==Множества==
 
==Множества==
  
В формализме помеченных объектов <tex dpi="350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах.
+
В помеченном мире <tex dpi="350">MSet=Set</tex>, потому что не бывает одинаковых элементов в множествах.
  
 
===Ограниченная конструкция===
 
===Ограниченная конструкция===
  
{{Определение
+
<tex dpi="350">A=Set_k(B)</tex> {{---}} множество из <tex dpi="350">k</tex> объектов (порядок не важен).
|definition=Ограниченным множеством <tex dpi="350">A=Set_k(B)</tex> назовём множество из <tex dpi="350">k</tex> объектов (порядок не важен).
 
}}
 
  
 
Рассмотрим <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex> и разобьем последовательности в <tex dpi="350">Seq_k(B)</tex> на классы эквивалентности по признаку равенства множеств элементов в них.
 
Рассмотрим <tex dpi="350">\left \{ a_1, a_2, ..., a_k \right \} \in Set_k(B)</tex> и разобьем последовательности в <tex dpi="350">Seq_k(B)</tex> на классы эквивалентности по признаку равенства множеств элементов в них.
Строка 376: Строка 387:
 
<tex dpi="350">Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}</tex>
 
<tex dpi="350">Set(A)(t)=\sum_{k=0}^{\infty}\frac{A(t)^k}{k!}=e^{A(t)}</tex>
  
Можно рассматривать <tex dpi="350">Set(A)</tex> как композицию урны и <tex dpi="350">A</tex>, другими словами, можно вместо атомов в урне взять объекты класса <tex dpi="350">A</tex>.
+
Можно рассматривать <tex dpi="350">Set(A)</tex> как композицию урны и <tex dpi="350">A</tex>, то есть вместо атомов взяты объекты класса <tex dpi="350">A</tex>.
  
 
==Циклы==
 
==Циклы==
Строка 382: Строка 393:
 
===Ограниченная конструкция===
 
===Ограниченная конструкция===
  
{{Определение
+
{{Утверждение
|definition=
+
|statement=Циклов нулевой длины <tex dpi="350">0</tex>. То есть, <tex dpi="350">c_0=0</tex>.
Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</tex>.
 
 
 
Циклов нулевой длины <tex dpi="350">0</tex>, то есть, <tex dpi="350">c_0=0</tex>.
 
 
}}
 
}}
  
Строка 400: Строка 408:
 
===Неограниченная конструкция===
 
===Неограниченная конструкция===
  
{{Определение
+
<tex dpi="350">Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(A)(t)=0+\sum_{k=1}^{\infty}\frac{A(t)^k}{k}=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex><ref>[https://www.wolframalpha.com/input/?i=series+-ln%281-x%29 Wolphram Alpha {{---}} Разложение в ряд]</ref>
|definition=Циклы <tex dpi="350">A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)</tex>.
 
}}
 
<tex dpi="350">Cycle(A)(t)=\sum_{k=0}^{\infty}Cycle_k(A)(t)=0+\sum_{k=1}^{\infty}\frac{A(t)^k}{k}=-ln \left (1+\left (-A(t)\right ) \right )=-ln \left (1-A(t) \right )=ln\left (\frac{1}{1-A(t)}\right )</tex> (Разложение натурального логарифма в ряд Тейлора)
 
  
=См.также=
+
==См.также==
 
*[[Конструирование комбинаторных объектов и их подсчёт]]
 
*[[Конструирование комбинаторных объектов и их подсчёт]]
 
*[[Функция Эйлера]]
 
*[[Функция Эйлера]]
Строка 414: Строка 419:
 
*[[Подсчет деревьев]]
 
*[[Подсчет деревьев]]
  
=Примeчания=
+
==Примeчания==
 
<references/>
 
<references/>
  
=Источники информации=
+
==Источники информации==
 
*[https://youtu.be/J2L-vdytqC0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, unmarked objects]
 
*[https://youtu.be/J2L-vdytqC0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, unmarked objects]
 
*[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, marked objects]
 
*[https://youtu.be/UwOjanKAMt0?list=PLrV7qfjOKnis2aCBAVcirxr_oxhNKoO6e Artem Vasilyev {{---}} Descrete maths lectures, marked objects]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)