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

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

Внимание! Вы не авторизовались на сайте. Ваш 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/Множество множество] комбинаторных объектов, обладающих каким-то свойством.
 
}}
 
}}
 
 
=Непомеченные комбинаторные объекты=
 
=Непомеченные комбинаторные объекты=
  
Строка 107: Строка 104:
 
{{Определение
 
{{Определение
 
|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>.
 
}}
 
}}
  
Строка 308: Строка 305:
 
# В каждой паре перебирает все возможные способы перенумеровать атомы. Нумерация идёт в том же порядке, что и изначальная. То есть для каждого цикла при фиксированном наборе номеров есть ровно 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>
Строка 332: Строка 329:
 
{{Утверждение
 
{{Утверждение
 
|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/Геометрическая_прогрессия Геометрическая прогрессия])
 
}}
 
}}
  
Строка 339: Строка 336:
 
====Пример====
 
====Пример====
  
'''Перестановки'''
+
'''[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>.
Строка 378: Строка 375:
 
Можно рассматривать <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>.
  
==Циклы==
+
==[http://en.wikipedia.org/wiki/Cyclic_order Циклы]==
  
 
===Ограниченная конструкция===
 
===Ограниченная конструкция===
  
 
{{Определение
 
{{Определение
|definition=
+
|definition=Цикл <tex dpi="350">A=Cycle_k(B)</tex> {{---}} ориентированная циклическая последовательность из <tex dpi="350">k</tex> объектов класса <tex dpi="350">B</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>.
+
{{Утверждение
 +
|statement=Циклов нулевой длины <tex dpi="350">0</tex>. То есть, <tex dpi="350">c_0=0</tex>.
 
}}
 
}}
  
Строка 403: Строка 401:
 
|definition=Циклы <tex dpi="350">A=Cycle(B)=\sum_{k=0}^{\infty}Cycle_k(B)</tex>.
 
|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> (Разложение натурального логарифма в ряд Тейлора)
+
<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>
  
 
=См.также=
 
=См.также=

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

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

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