Изменения
Нет описания правки
<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>
== Еще примеры ==
{{Задача
| about =
| definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся в <tex>0</tex> и оканчивающихся:
<tex>(a)</tex> в <tex>0</tex>;
<tex>(</tex>б<tex>)</tex> в <tex>0</tex> и не заходящих в отрицательную полупрямую.
}}
=== Решение ===
<tex>(a)</tex> Заметим, что для того, чтобы закончить путь в 0 необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать <tex>\dfrac{n}{2}</tex> позиций для, например, шагов вправо из всего <tex>n</tex> шагов. Тогда ответом будет сумма от нуля до бесконечности по <tex>n</tex> всех <tex>C^{n}_{2n}</tex>. То есть,
<center>
<tex>
g(x) = \sum\limits_{0}^{\infty} C^{n}_{2n}
</tex>
</center>
Рассмотрим <tex>f(x) = \sum\limits_{0}^{\infty} C_n x^n </tex>, где <tex>C_n</tex> {{---}} число Каталана. Тогда, заметим что <tex>f'(x) = \sum\limits_{0}^{\infty} n C_n x^{n-1} </tex>. Т.к. <tex>C_n = \dfrac{1}{n+1} C_{2n}^n </tex>, то справедливо равенство:
<center>
<tex>
g(x) = (n+1)f(x) = xf'(x) + f(x)
</tex>
</center>
Мы знаем, что производящая функция для чисел Каталана равна <tex>f(x) = \dfrac{1-\sqrt{1-4x}}{2x}</tex>. Найдем <tex>f'(x)</tex>.
<center>
<tex>
f'(x) = \dfrac{\dfrac{4x}{\sqrt{1-4x}} - 2 + 2\sqrt{1-4x}}{4x^2} = \dfrac{1 - 2x - \sqrt{1-4x}}{2x^2 \sqrt{1-4x}}
</tex>
</center>
Соответственно, ответом будет производящая функция вида:
<center>
<tex>
g(x) = \dfrac{1 - 2x - \sqrt{1-4x}}{2x \sqrt{1-4x}} + \dfrac{1-\sqrt{1-4x}}{2x}
</tex>
</center>
(б) Заметим, что задача аналогична Правильной скобочной последовательности. Тогда производящей функцией для нашей задачи будет производящая функция для ПСП, а именно:
<center>
<tex>
g(x) = \dfrac{1-\sqrt{1-4x}}{2x}
</tex>
</center>
== Приложения ==
=== Примеры простых производящих функций ===
