Викиконспекты - Вклад участника [ru]

Производящая функция

2017-01-06T14:30:44Z

Dantesto:

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<center>
<tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>,
</center>
порождающий(производящий) последовательность <tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>.
* Вычисления бесконечных сумм.

== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod\limits_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых.Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых <tex>(4+1; 3+2)</tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять(второе слагаемое {{---}} <tex>-x^k</tex>) или не взять(первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod\limits_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod\limits_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.

* <tex>\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} число разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod\limits_{n=1}^\infty(1+x^{ n})=\prod\limits_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1}
z^n - 8\sum\limits_{n=2}^\infty a_ { n-2}
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n }
z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n }
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'</tex>

<tex>\sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex>=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>

<tex>=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum\limits z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum\limits (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\limits 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum\limits \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum\limits \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]

Категория:Комбинаторные объекты

2017-01-05T13:02:04Z

Dantesto: Удалено содержимое страницы

Категория:Комбинаторные объекты

2017-01-05T13:01:25Z

Dantesto:

'''З'''
*[[Задача об ожерельях | Задача об ожерельях]]
'''Н'''
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
'''Ч'''
*[[Числа Каталана | Числа Каталана]]
*[[Числа Стирлинга первого рода | Числа Стирлинга первого рода]]
*[[Числа Стирлинга второго рода | Числа Стирлинга второго рода]]
*[[Числа Эйлера I и II рода | Числа Эйлера I и II рода]]

[[Категория: Комбинаторные объекты]]

Производящая функция

2017-01-05T13:00:15Z

Dantesto:

Категория:Комбинаторные объекты

2017-01-05T12:53:55Z

Dantesto: Новая страница: «'''З''' * Задача об ожерельях '''Н''' *[[Нахождение количества разбиений...»

Комбинаторные объекты

2017-01-05T12:36:35Z

Dantesto:

{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}

{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
}}

== Примеры комбинаторных объектов ==
=== Битовые вектора ===
{{Определение
|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') — последовательность нулей и единиц заданной длины.
}}

=== Перестановки ===
{{Определение
|definition='''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' (англ. ''permutations'') — упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.
}}
Примером перестановки может служить задача о рассадке <tex>n</tex> человек за стол по <tex>n</tex> местам.

=== Перестановки с повторениями ===
{{Определение
|definition='''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — те же перестановки, однако некоторые элементы могут встречаться несколько раз.
}}
В пример можно привести следующую задачу: имеется набор книг <tex>\{a_1, a_2, \ldots, a_n\}</tex>, каждая из которых имеется в <tex>k_1, k_2, \ldots, k_n</tex> экземплярах соответственно. Сколько существует способов переставить книги на полке?

=== Размещения ===
{{Определение
|definition='''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> (англ. ''arrangement'') из <tex>n</tex> по <tex>k</tex> — упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
}}
Примером размещения может служить задача о рассадке <tex>k</tex> человек за стол по <tex>n</tex> местам, где <tex>n > k</tex>.

=== Размещения с повторениями ===
{{Определение
|definition='''Размещение с повторениями''' (англ. ''arrangement with repetitions''), составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.
}}
В пример можно привести следующую задачу: имеется <tex>n</tex> книг, каждая в <tex>k</tex> экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

=== Сочетания ===
{{Определение
|definition='''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' (англ. ''combinations'') из <tex>n</tex> по <tex>k</tex> — набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.
}}
Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов.

=== Сочетания с повторениями ===
{{Определение
|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
}}
В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?

=== Разбиение на неупорядоченные слагаемые ===
{{Определение
|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') — представление числа <tex>n</tex> в виде суммы слагаемых.
}}
{{main|Нахождение количества разбиений числа на слагаемые}}

=== Разбиение на подмножества ===
{{Определение
|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
}}
{{main|Числа Стирлинга второго рода}}

== Число комбинаторных объектов ==
{| class="wikitable" border = 1
|'''Тип объекта'''||'''Число объектов'''
|-
|Битовые вектора||<tex>2^{n}</tex>
|-
|Перестановки||<tex>P_n = n!</tex>
|-
|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>
|-
|Размещения||<tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
|-
|Размещения с повторениями||<tex>n^k</tex>
|-
|Сочетания||<tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
|-
|Сочетания с повторениями||<tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
|-
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
|-
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
|}

== См. также ==
*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение следующего объекта | Получение следующего объекта]]
*[[Получение номера по объекту | Получение номера по объекту]]
*[[Получение объекта по номеру | Получение объекта по номеру]]

== Примечания ==
<references/>

== Источники информации ==
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
[[Категория: Комбинаторные объекты ]]

Комбинаторные объекты

2017-01-05T12:18:51Z

Dantesto: Примеры

Производящая функция

2017-01-04T16:25:44Z

Dantesto: Исправление произведений

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>,
порождающий(производящий) последовательность<tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>.
* Вычисления бесконечных сумм.

== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod\limits_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых.Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых <tex>(4+1; 3+2)</tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять(второе слагаемое {{---}} <tex>-x^k</tex>) или не взять(первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod\limits_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod\limits_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.

* <tex>\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} число разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod\limits_{n=1}^\infty(1+x^{ n})=\prod\limits_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1}
z^n - 8\sum\limits_{n=2}^\infty a_ { n-2}
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n }
z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n }
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'</tex>

<tex>\sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex>=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>

<tex>=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum\limits z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum\limits (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\limits 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum\limits \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum\limits \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Производящая функция

2017-01-04T16:20:52Z

Dantesto: Исправление сумм

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>,
порождающий(производящий) последовательность<tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>.
* Вычисления бесконечных сумм.

== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых.Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых <tex>(4+1; 3+2)</tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять(второе слагаемое {{---}} <tex>-x^k</tex>) или не взять(первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.

* <tex>\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} число разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod_{n=1}^\infty(1+x^{ n})=\prod_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1}
z^n - 8\sum\limits_{n=2}^\infty a_ { n-2}
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n }
z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n }
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'</tex>

<tex>\sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex>=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>

<tex>=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum\limits z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum\limits (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\limits 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum\limits \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum\limits \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Производящая функция

2017-01-04T16:12:30Z

Dantesto:

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий(производящий) последовательность<tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>.
* Вычисления бесконечных сумм.

== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых.Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых <tex>(4+1; 3+2)</tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять(второе слагаемое {{---}} <tex>-x^k</tex>) или не взять(первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.

* <tex>\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} число разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod_{n=1}^\infty(1+x^{ n})=\prod_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_ { n-1}
z^n - 8\sum_{n=2}^\infty a_ { n-2}
z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_ { n }
z^n - 8z^2\sum_{n=0}^\infty a_ { n }
z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{ n = 1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z(\sum_{ n = 2}^\infty z^n)'</tex>

<tex>\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex>=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>

<tex>=\dfrac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum_{n=0}^{\infty}n p(1-p)^{n} + \sum_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}

== См. также ==

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Комбинаторные объекты

2017-01-04T15:48:54Z

Dantesto: Английские термины, ссылки

{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}

{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
}}

== Примеры комбинаторных объектов ==
=== Битовые вектора ===
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') — последовательность нулей и единиц заданной длины.

=== Перестановки ===
'''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' (англ. ''permutations'') — упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.

=== Перестановки с повторениями ===
'''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — те же перестановки, однако некоторые элементы могут встречаться несколько раз.

=== Размещения ===
'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> (англ. ''arrangement'') из <tex>n</tex> по <tex>k</tex> — упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.

=== Размещения с повторениями ===
'''Размещение с повторениями''' (англ. ''arrangement with repetitions''), составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.

=== Сочетания ===
'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' (англ. ''combinations'') из <tex>n</tex> по <tex>k</tex> — набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.

=== Сочетания с повторениями ===
'''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.

=== Разбиение на неупорядоченные слагаемые ===
[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') — представление числа <tex>n</tex> в виде суммы слагаемых.
{{main|Нахождение количества разбиений числа на слагаемые}}

=== Разбиение на подмножества ===
[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
{{main|Числа Стирлинга второго рода}}

== Число комбинаторных объектов ==
{| class="wikitable" border = 1
|'''Тип объекта'''||'''Число объектов'''
|-
|Битовые вектора||<tex>2^{n}</tex>
|-
|Перестановки||<tex>P_n = n!</tex>
|-
|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>
|-
|Размещения||<tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
|-
|Размещения с повторениями||<tex>n^k</tex>
|-
|Сочетания||<tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
|-
|Сочетания с повторениями||<tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
|-
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
|-
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
|}

== См. также ==
*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение следующего объекта | Получение следующего объекта]]
*[[Получение номера по объекту | Получение номера по объекту]]
*[[Получение объекта по номеру | Получение объекта по номеру]]

== Примечания ==
<references/>

== Источники информации ==
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-31T14:56:12Z

Dantesto:

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>.
==Применение алгоритма==
{{Задача
|definition = Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
}}
===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в отрезке <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(a[i], a[random(1..n)])
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(a[random(1..n)], a[random(1..n)])

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex>, следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[[Методы генерации случайного сочетания | Методы генерации случайного сочетания]]
==Источники информации==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия — Тасование Фишера-Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Производящая функция

2016-12-31T14:26:31Z

Dantesto:

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий(производящий) последовательность<tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности;
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;
* Исследования асимптотического поведения последовательности;
* Доказательства тождеств с последовательностями;
* Решения задачи подсчета объектов в комбинаторике.Например, в доказательстве[[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>;
* Вычисления бесконечных сумм.
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых.Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых (<tex>4+1</tex>; <tex>3+2</tex>) и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять(второе слагаемое {{---}} <tex>-x^k</tex>) или не взять(первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex>{{---}}
количество разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex>{{---}}
количество разбиений на различные слагаемые.

* <tex>\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex>{{---}}
количество разбиений на нечётные слагаемые.С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod_{n=1}^\infty(1+x^{ n})=\prod_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению.Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде.Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_ { n-1}
z^n - 8\sum_{n=2}^\infty a_ { n-2}
z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_ { n }
z^n - 8z^2\sum_{n=0}^\infty a_ { n }
z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{ n = 1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z(\sum_{ n = 2}^\infty z^n)'</tex>

<tex>\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex>=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=</tex>

<tex>=\dfrac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum_{n=0}^{\infty}n p(1-p)^{n} + \sum_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| Последовательность || Производящая функция в виде ряда || Производящая функция в замкнутом виде
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Комбинаторные объекты

2016-12-31T13:09:05Z

Dantesto: Удаление вывода формул, добавление таблицы

Комбинаторные объекты

2016-12-12T21:11:45Z

Dantesto:

{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}

{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''.
}}

== Примеры комбинаторных объектов ==
=== Битовые вектора ===
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' — последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.

=== Перестановки ===
'''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' — это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно <tex>P_n = n!</tex>. Получить эту формулу можно следующим образом: поставим один из <tex>n</tex> элементов на первое место, далее поставим на второе один из <tex>n - 1</tex> оставшихся элементов,... один из <tex>1</tex> элемента на последнее. Всего таких выборов можно совершить <tex>n \times (n - 1) \times ... \times 1 = n!</tex>.

=== Перестановки с повторениями ===
'''Перестановки с повторениями''' — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов <tex>{a_1, a_2, ..., a_n}</tex>, в которых эти элементы повторяются соответственно <tex>k_1, k_2, ..., k_n</tex> раз, равно <tex dpi = "150">\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}</tex>. Выведем формулу. Всего перестановок <tex>(k_1 + k_2 + ... + k_n)!</tex>, однако среди них есть и повторяющиеся. Такие попадаются, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в <tex>k_1!k_2!...k_n!</tex> раз. В итоге получаем необходимую формулу.

=== Размещения ===
'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> из <tex>n</tex> по <tex>k</tex> — это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества. Таких наборов <tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>n</tex> элементов, на следующее один из <tex>n - 1</tex>,... и на последнее один из <tex>n - k + 1</tex>. Всего получится <tex dpi = "150">n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}</tex>.

=== Размещения с повторениями ===
'''Размещение с повторениями''', составленное из данных <tex>n</tex> элементов по <tex>k</tex> — это отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, ..., k</tex> в данное множество <tex>\{a_1, a_2, ..., a_n\}</tex>. Всего таких элементов <tex>n^k</tex>. Формула выводится так же, как и для битовых векторов.

=== Сочетания ===
'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' из <tex>n</tex> по <tex>k</tex> — это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для <tex>k</tex> мест. Тогда <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>.

=== Сочетания с повторениями ===
'''Сочетания с повторениями''' — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего <tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>. Чтобы вывести формулу, давайте различные элементы в перестановке разделим перегородками, а каждый элемент назовем <tex>1</tex>, тогда, чтобы получить новую перестановку просто будем менять местами перегородки и <tex>1</tex>, причем таких перегородок будет <tex>n - 1</tex>, даже если мы не брали некоторые типы элементов. Таких перестановок <tex>(n - 1 + k)!</tex>, а за вычетом перестановок одинаковых элементов (перегородок и <tex>1</tex>), коих в <tex>k!(n - 1)!</tex> раз больше необходимых, получаем необходимую формулу.

=== Разбиение на неупорядоченные слагаемые ===
[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] — это представление числа <tex>n</tex> в виде суммы слагаемых. Всего таких разбиений:
:
<tex>P_{n,k} = \left \{
\begin{array}{ll} P_{n,k - 1} + P_{n - k, k}, & 0 < k \leqslant n \\
P_{n, n}, & k > n \\
1, & n = 0, k = 0 \\
0, & n \neq 0 , k = 0, \end{array} \right.</tex>

где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = n</tex>. Вывод формулы можно найти [[Нахождение количества разбиений числа на слагаемые | здесь]].

=== Разбиение на подмножества ===
[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
Если задано множество из <tex>n</tex> элементов, которое необходимо разбить на <tex>k</tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть (<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых <tex>n-1</tex> элементов по <tex>k</tex> непустым частям дает <tex>k</tex> подмножеств, с которыми можно объединить последний элемент).

<tex>\begin{Bmatrix}
n \\
k
\end{Bmatrix} = \begin{cases}
k\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix} + \begin{Bmatrix}
n-1 \\
k-1
\end{Bmatrix}, 0<k<n \\
0, k = 0 \\
0, n = 0 \\
0, k > n \\
1, k = n
\end{cases}
</tex>

Подробнее можно прочитать на странице о [[Числа Стирлинга второго рода | числах Стирлинга второго порядка]].

== Источники информации ==
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Размещения, перестановки, сочетания с повторениями]

== Примечания ==
<references/>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]

Комбинаторные объекты

2016-12-12T20:06:27Z

Dantesto:

{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}

{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''.
}}

== Примеры комбинаторных объектов ==
=== Битовые вектора ===
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' — последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.

=== Перестановки ===
'''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' — это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно <tex>P_n = n!</tex>. Получить эту формулу можно следующим образом: поставим один из <tex>n</tex> элементов на первое место, далее поставим на второе один из <tex>n - 1</tex> оставшихся элементов,... один из <tex>1</tex> элемента на последнее. Всего таких выборов можно совершить <tex>n \times (n - 1) \times ... \times 1 = n!</tex>.

=== Перестановки с повторениями ===
'''Перестановки с повторениями''' — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов <tex>{a_1, a_2, ..., a_n}</tex>, в которых эти элементы повторяются соответственно <tex>k_1, k_2, ..., k_n</tex> раз, равно <tex dpi = "150">\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}</tex>. Выведем формулу. Всего перестановок <tex>(k_1 + k_2 + ... + k_n)!</tex>, однако среди них есть и повторяющиеся. Такие попадаются, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в <tex>k_1!k_2!...k_n!</tex> раз. В итоге получаем необходимую формулу.

=== Размещения ===
'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> из <tex>n</tex> по <tex>k</tex> — это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества. Таких наборов <tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>n</tex> элементов, на следующее один из <tex>n - 1</tex>,... и на последнее один из <tex>n - k + 1</tex>. Всего получится <tex dpi = "150">n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}</tex>.

=== Размещения с повторениями ===
'''Размещение с повторениями''', составленное из данных <tex>n</tex> элементов по <tex>k</tex> — это отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, ..., k</tex> в данное множество <tex>\{a_1, a_2, ..., a_n\}</tex>. Всего таких элементов <tex>n^k</tex>. Формула выводится так же, как и для битовых векторов.

=== Сочетания ===
'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' из <tex>n</tex> по <tex>k</tex> — это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для <tex>k</tex> мест. Тогда <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>.

=== Сочетания с повторениями ===
'''Сочетания с повторениями''' — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество. Способов таких выборов всего <tex dpi = "150">\tilde{\sf_C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>.

=== Разбиение на неупорядоченные слагаемые ===
[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] — это представление числа <tex>n</tex> в виде суммы слагаемых. Всего таких разбиений:
:
<tex>P_{n,k} = \left \{
\begin{array}{ll} P_{n,k - 1} + P_{n - k, k}, & 0 < k \leqslant n \\
P_{n, n}, & k > n \\
1, & n = 0, k = 0 \\
0, & n \neq 0 , k = 0, \end{array} \right.</tex>

где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = n</tex>. Вывод формулы можно найти [[Нахождение количества разбиений числа на слагаемые | здесь]].

=== Разбиение на подмножества ===
[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
Если задано множество из <tex>n</tex> элементов, которое необходимо разбить на <tex>k</tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть (<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых <tex>n-1</tex> элементов по <tex>k</tex> непустым частям дает <tex>k</tex> подмножеств, с которыми можно объединить последний элемент).

<tex>\begin{Bmatrix}
n \\
k
\end{Bmatrix} = \begin{cases}
k\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix} + \begin{Bmatrix}
n-1 \\
k-1
\end{Bmatrix}, 0<k<n \\
0, k = 0 \\
0, n = 0 \\
0, k > n \\
1, k = n
\end{cases}
</tex>

Подробнее можно прочитать на странице о [[Числа Стирлинга второго рода | числах Стирлинга второго порядка]].

== Примечания ==
<references/>

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]

Комбинаторные объекты

2016-12-12T18:47:25Z

Dantesto:

Комбинаторные объекты

2016-12-12T18:25:14Z

Dantesto:

Комбинаторные объекты

2016-12-12T17:47:57Z

Dantesto:

Комбинаторные объекты

2016-12-11T19:53:04Z

Dantesto:

Комбинаторные объекты

2016-12-11T15:59:52Z

Dantesto:

Комбинаторные объекты

2016-12-11T14:42:27Z

Dantesto:

Производящая функция

2016-12-10T22:50:59Z

Dantesto: /* Источники информации */

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности;
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;
* Исследования асимптотического поведения последовательности;
* Доказательства тождеств с последовательностями;
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>;
* Вычисления бесконечных сумм.
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex dpi = "180">\prod_{n=1}^\infty (1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых. Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых (<tex>4+1</tex>; <tex>3+2</tex>) и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое {{---}} <tex>-x^k</tex>) или не взять (первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex dpi = "180"> \prod_{n=1}^\infty \frac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые.

* <tex dpi = "180">\prod_{n=1}^\infty (1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} количество разбиений на различные слагаемые.

* <tex dpi = "180">\prod_{n=1}^\infty (1+x^{2n-1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} количество разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n=l_n</tex>:
<tex dpi = "180"> \prod_{n=1}^\infty (1+x^{n})=\prod_{n=1}^\infty \frac{1-x^{2n}}{1-x^n}=\frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}...=</tex>

<tex dpi = "180">=\frac{1}{1-x}\frac{1}{1-x^3}\frac{1}{1-x^5}...=\prod_{n=1}^\infty (1+x^{2n-1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=...,</tex>
#: <tex>a_1=...,</tex>
#: <tex>...</tex>
#: <tex>a_{k-1}=...,</tex>
#: <tex>a_{n}=..., n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы <tex>\sum</tex> к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0=1,</tex>

<tex>a_1=2,</tex>

<tex>a_n=6a_{n-1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_{n-1}z^n - 8\sum_{n=2}^\infty a_{n-2}z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_{n}z^n - 8z^2\sum_{n=0}^\infty a_{n}z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n=(1, 1, 1, ...)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex dpi = "150">zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{n=1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex dpi = "150">\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z (\sum_{n=2}^\infty z^n)'</tex>

<tex dpi = "150">\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}</tex>

<tex dpi = "150">z (\frac{z^2}{1-z})'=\frac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex dpi = "150">G(z)=1-4z+6zG(z) - 8z^2G(z)+\frac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex dpi = "180">G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей<ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex dpi = "180">G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты<ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex dpi = "160">\frac{1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex dpi = "160">=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n</tex>

<tex dpi = "160">G(z)=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}=</tex>

<tex dpi = "160">=\frac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\frac{7}{9}\sum_{n=0}^{\infty} z^n - \frac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \frac{7}{18}\sum_{n=0}^{\infty} 4^n z^n</tex>

<tex dpi = "160">a_n=\frac{n+1}{3}+\frac{7}{9}-\frac{2^n}{2}+\frac{7 \cdot 4^n}{18}=\frac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятностей. Например, в геометрическом распределении<ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex dpi = "160">\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} </tex>

*<tex dpi = "160"> \operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3...</tex> и <tex>1, 4, 9...</tex>:

* <tex dpi = "160">\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} = </tex>

<tex dpi = "160">= \sum_{n=0}^{\infty}(n+1) p (1-p)^{n} = </tex>

<tex dpi = "160">= \sum_{n=0}^{\infty}n p (1-p)^{n} + \sum_{n=1}^{\infty} p (1-p)^{n-1} = </tex>

<tex dpi = "160">= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \frac{1}{p}</tex>

* <tex dpi = "160"> \operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex dpi = "160"> =p\sum_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum_{n=1}^{\infty}(1-p)^{n+1} + p\frac{\operatorname{d}}{\operatorname{d}p}\sum_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{n=0}^{\infty}(1-p)^{n} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{n=0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{1}{1-(1-p)} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{(1-p)^2}{p}\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1-p}{p}\right) =</tex>

<tex dpi = "160"> = p\cdot\frac{2}{p^3} - p\cdot\frac{1}{p^2} = \frac{2}{p^{2}} - \frac{1}{p} = \frac{2-p}{p^{2}}</tex>.

Тогда:

<tex dpi = "160">\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \frac{2-p}{p^{2}}-\frac{1}{p^2}=\frac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций<ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы <tex dpi="110">\sum</tex> выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| Последовательность || Производящая функция в виде ряда || Производящая функция в замкнутом виде
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,...)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, ..., 0, 1, 0, 0...)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,...)</tex> || <tex>\sum z^n</tex> || <tex dpi="160">\frac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, ..., 0, 1, 0, 0, ... 0, 1, 0, 0...)</tex> (повторяется через <tex>m</tex>) || <tex>\sum z^{nm}</tex> || <tex dpi="160">\frac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,...)</tex> || <tex>\sum (-1)^nz^n</tex> || <tex dpi="160">\frac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,...)</tex> || <tex>\sum (n+1)z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,...)</tex> || <tex>\sum 2^nz^n</tex> || <tex dpi="160">\frac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,...)</tex> || <tex>\sum r^nz^n</tex> || <tex dpi="160">\frac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(0, 1, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{4},...)</tex> || <tex dpi="160">\sum \frac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24},...)</tex> || <tex dpi="160">\sum \frac{1}{n!}</tex> <tex>z^n</tex> || <tex dpi="140">e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia - Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Производящая функция

2016-12-10T22:48:58Z

Dantesto:

{{Определение
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<tex>G(z)=\sum_{n=0}^\infty a_n z^n</tex>,
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, ...)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности;
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи;
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу;
* Исследования асимптотического поведения последовательности;
* Доказательства тождеств с последовательностями;
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n</tex> × <tex>n</tex>;
* Вычисления бесконечных сумм.
== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex dpi = "180">\prod_{n=1}^\infty (1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых. Например коэффициент при <tex>x^5</tex> {{---}} <tex>+1</tex>, потому-что существует два разбиение на четное число различных слагаемых (<tex>4+1</tex>; <tex>3+2</tex>) и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое {{---}} <tex>-x^k</tex>) или не взять (первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex dpi = "180"> \prod_{n=1}^\infty \frac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые.

* <tex dpi = "180">\prod_{n=1}^\infty (1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} количество разбиений на различные слагаемые.

* <tex dpi = "180">\prod_{n=1}^\infty (1+x^{2n-1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} количество разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n=l_n</tex>:
<tex dpi = "180"> \prod_{n=1}^\infty (1+x^{n})=\prod_{n=1}^\infty \frac{1-x^{2n}}{1-x^n}=\frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}...=</tex>

<tex dpi = "180">=\frac{1}{1-x}\frac{1}{1-x^3}\frac{1}{1-x^5}...=\prod_{n=1}^\infty (1+x^{2n-1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=...,</tex>
#: <tex>a_1=...,</tex>
#: <tex>...</tex>
#: <tex>a_{k-1}=...,</tex>
#: <tex>a_{n}=..., n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы <tex>\sum</tex> к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0=1,</tex>

<tex>a_1=2,</tex>

<tex>a_n=6a_{n-1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum_{n=2}^\infty (6a_{n-1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum_{n=2}^\infty a_{n-1}z^n - 8\sum_{n=2}^\infty a_{n-2}z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum_{n=1}^\infty a_{n}z^n - 8z^2\sum_{n=0}^\infty a_{n}z^n+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n=(1, 1, 1, ...)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex dpi = "150">zB'(z)=z(\sum_{n=0}^\infty b_n z^n)'=z\sum_{n=1}^\infty nb_n z^{n-1}=\sum_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex dpi = "150">\sum_{n=2}^\infty n z^n=z \sum_{n=2}^\infty n z^{n-1}= z (\sum_{n=2}^\infty z^n)'</tex>

<tex dpi = "150">\sum_{n=2}^\infty z^n=\sum_{n=0}^\infty z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}</tex>

<tex dpi = "150">z (\frac{z^2}{1-z})'=\frac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом наше последнее слагаемое примет вид:

<tex dpi = "150">G(z)=1-4z+6zG(z) - 8z^2G(z)+\frac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex dpi = "180">G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей<ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex dpi = "180">G(z)=\frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты<ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex dpi = "160">\frac{1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n=</tex>

<tex dpi = "160">=\sum_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum_{n=0}^{\infty}(n+1)z^n</tex>

<tex dpi = "160">G(z)=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}=</tex>

<tex dpi = "160">=\frac{1}{3}\sum_{n=0}^{\infty} (n+1)z^n +\frac{7}{9}\sum_{n=0}^{\infty} z^n - \frac{1}{2}\sum_{n=0}^{\infty} 2^n z^n + \frac{7}{18}\sum_{n=0}^{\infty} 4^n z^n</tex>

<tex dpi = "160">a_n=\frac{n+1}{3}+\frac{7}{9}-\frac{2^n}{2}+\frac{7 \cdot 4^n}{18}=\frac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения математического ожидания и дисперсии различных распределений в теории вероятностей. Например, в геометрическом распределении<ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex dpi = "160">\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} </tex>

*<tex dpi = "160"> \operatorname{E}(\xi^2) = \sum_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3...</tex> и <tex>1, 4, 9...</tex>:

* <tex dpi = "160">\operatorname{E}(\xi)=\sum_{n=1}^{\infty}n p (1-p)^{n-1} = </tex>

<tex dpi = "160">= \sum_{n=0}^{\infty}(n+1) p (1-p)^{n} = </tex>

<tex dpi = "160">= \sum_{n=0}^{\infty}n p (1-p)^{n} + \sum_{n=1}^{\infty} p (1-p)^{n-1} = </tex>

<tex dpi = "160">= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \frac{1}{p}</tex>

* <tex dpi = "160"> \operatorname{E}(\xi^2) = p\sum_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex dpi = "160"> =p\sum_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum_{n=1}^{\infty}(1-p)^{n+1} + p\frac{\operatorname{d}}{\operatorname{d}p}\sum_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum_{n=0}^{\infty}(1-p)^{n} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\sum_{n=0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{1}{1-(1-p)} \cdot (1-p)^2\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex dpi = "160"> = p\frac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\frac{(1-p)^2}{p}\right) +p\frac{\operatorname{d}}{\operatorname{d}p}\left(\frac{1-p}{p}\right) =</tex>

<tex dpi = "160"> = p\cdot\frac{2}{p^3} - p\cdot\frac{1}{p^2} = \frac{2}{p^{2}} - \frac{1}{p} = \frac{2-p}{p^{2}}</tex>.

Тогда:

<tex dpi = "160">\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \frac{2-p}{p^{2}}-\frac{1}{p^2}=\frac{1-p}{p^2}</tex>
== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций<ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы <tex dpi="110">\sum</tex> выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| Последовательность || Производящая функция в виде ряда || Производящая функция в замкнутом виде
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,...)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, ..., 0, 1, 0, 0...)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,...)</tex> || <tex>\sum z^n</tex> || <tex dpi="160">\frac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, ..., 0, 1, 0, 0, ... 0, 1, 0, 0...)</tex> (повторяется через <tex>m</tex>) || <tex>\sum z^{nm}</tex> || <tex dpi="160">\frac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,...)</tex> || <tex>\sum (-1)^nz^n</tex> || <tex dpi="160">\frac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,...)</tex> || <tex>\sum (n+1)z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,...)</tex> || <tex>\sum 2^nz^n</tex> || <tex dpi="160">\frac{1}{(1-2z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,...)</tex> || <tex>\sum r^nz^n</tex> || <tex dpi="160">\frac{1}{(1-rz)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="160">(</tex><tex dpi="130">1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},...</tex><tex dpi="160">)</tex> || <tex dpi="140">\sum {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex dpi="160">\frac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(0, 1, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{4},...)</tex> || <tex dpi="160">\sum \frac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex dpi="140">(1, 1, \frac{1}{2}, \frac{1}{6}, \frac{1}{24},...)</tex> || <tex dpi="160">\sum \frac{1}{n!}</tex> <tex>z^n</tex> || <tex dpi="140">e^z</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ genfunc.ru]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia - Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T21:33:02Z

Dantesto: /* Обоснование */

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия — Тасование Фишера-Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T21:13:39Z

Dantesto: /* Источники информации */

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия — Тасование Фишера-Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T21:13:02Z

Dantesto: /* Источники информации */

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера-Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T21:12:11Z

Dantesto:

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера–Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T20:56:54Z

Dantesto: /* Обоснование */

'''Тасование Фишера – Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера – Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера–Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

2016-12-10T20:51:10Z

Dantesto: /* Решение: */

'''Тасование Фишера – Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера – Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
==Применение алгоритма==
===Задача:===
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.

===Решение:===

Пусть 
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> 
Следующий алгоритм решает задачу:

'''int[n]''' randomPermutation(a: '''int[n]'''): // '''n''' {{---}} длина перестановки 
'''for''' i = n '''downto''' 1
j = random(1..i)
swap(a[i], a[j])
'''return''' a

==Обоснование==
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент ... <tex> 1</tex> способ выбрать последний элемент. Таким образом, последовательность длины <tex> n</tex> мы можем получить <tex> $$n \times (n - 1) \times \ldots \times 1 = n! $$ </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.

==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

===Пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

===Другой пример неправильной реализации:===
'''for''' i = n '''downto''' 1
swap(random(1..n), random(1..n))

Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> ,следовательно некоторые перестановки будут появляться еще чаще.

==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
==Источники информации==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера–Йетса]
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Генерация комбинаторных объектов]]