4. Рекуррентные соотношения и производящие функции

1. Производящие функции и действия над ними

Определение. Пусть a_0,a_1,a_2,\ldots — произвольная (бесконечная) последовательность чисел (целых, рациональных, вещественных или комплексных). Производящей функцией (производящим рядом) называется запись вида

\displaystyle A(s)=a_0+a_1s+a_2s^2+\ldots=\sum_{n=0}^{\infty}a_ns^n .

Замечание. Не следует думать, что мы можем сказать, чему равно значение производящей функции A в точке s=s_0. Переменная s является формальной, и ряд a_0+a_1s_0+a_2s_0^2+\ldots смысла не имеет. Единственное, что мы можем сказать про функцию A(s), это что ее значение в нуле равно a_0. Если, однако, производящий ряд является полиномом (т.е. все его коэффициенты кроме конечного числа равны нулю), то значение этого ряда в любой точке выражается конечной суммой и поэтому имеет смысл.

Определение. Суммой двух производящих функций

A(s)=a_0+a_1s+a_2s^2+\ldots и B(s)=b_0+b_1s+b_2s^2+\ldots

называется производящая функция

A(s)+B(s)=(a_0+b_0)+(a_1+b_1)s+(a_2+b_2)s^2+\ldots

Произведением производящих функций A и B называется производящая функция

A(s)B(s)=a_0b_0+(a_0b_1+a_1b_0)s+(a_0b_2+a_1b_1+a_2b_0)s^2+\ldots

Определение. Пусть A(s)=a_0+a_1s+a_2s^2+\ldots и B(s)=b_1s+b_2s^2+\ldots — две производящие функции, причем B(0)=0. Подстановкой производящей функции B в функцию A называется производящая функция

A(B(s))=a_0+a_1b_1s+ (a_1b_2+a_2b_1^2)s^2+(a_1b_3+2a_2b_1b_2+a_3b_1^3)s^3+\ldots

Если, например B(s)=-s, то A(B(s))=a_0-a_1s+a_2s^2-\ldots

Очевидно, что если обе производящие функции являются многочленами, то определения суммы, произведения и подстановки производящих функций совпадают с определениями суммы, произведения и подстановки многочленов.

2. Элементарные производящие функции

Поскольку неудобно каждый раз записывать производящую функцию в виде ряда, то для некоторых часто встречающихся функций введены сокращенные записи.

Определение.

\displaystyle {\rm 1)}\ (1+s)^{\alpha}=1+\alpha s+{\alpha(\alpha-1)\over 2!}s^2+{\alpha(\alpha-1)(\alpha-2)\over 3!}s^3+\ldots,

где \alpha — произвольное комплексное число.

Коэффициент при s^n в этой записи называется числом сочетаний из \alpha по n и обозначается {\sf C}_{\alpha}^n или \left(\begin{array}{c}<br />
\alpha\\ n<br />
\end{array}\right).

\begin{array}{l}<br />
\displaystyle<br />
{\rm 2)}\ e^s=1+s+{s^2\over 2!}+{s^3\over 3!}+\ldots\\[3mm]<br />
\displaystyle<br />
{\rm 3)}\ \ln{1\over 1-s}=s+{s^2\over 2}+{s^3\over 3}+\ldots\\[3mm]<br />
\displaystyle<br />
{\rm 4)}\ \sin s=s-{s^3\over 3!}+{s^5\over 5!}-\ldots\\[3mm]<br />
\displaystyle<br />
{\rm 5)}\ \cos s=1-{s^2\over 2!}+{s^4\over 4!}-\ldots<br />
\end{array}

При натуральном значении \alpha часть 1) определения совпадает с обычным определением степени многочлена. Пользуясь этим, можно получить простейшие комбинаторные тождества. Подставляя, например, s=1 и s=-1, получаем тождества:

\begin{array}{l}<br />
1+\alpha+{\sf C}_{\alpha}^2+{\sf C}_{\alpha}^3+\ldots+{\sf<br />
C}_{\alpha}^{\alpha}=2^{\alpha},\\<br />
1-\alpha+{\sf C}_{\alpha}^2-{\sf C}_{\alpha}^3+\ldots+(-1)^{\alpha}{\sf C}_{\alpha}^{\alpha}=0.<br />
\end{array}

Между введенными функциями имеются соотношения, которые также связаны с комбинаторными тождествами. Докажем, например, что

e^se^{-s}=1.

Действительно, свободный член произведения равен 1, а при n>0 получаем

\displaystyle {1\over n!0!}-{1\over (n-1)!1!}+{1\over (n-2)!2!}-\ldots+{(-1)^n\over 0!n!},

что совпадает с левой частью равенства 2) при \alpha=n, откуда получаем требуемое.

Можно также доказать следующие равенства (сделайте это самостоятельно):

\begin{array}{l}<br />
1)\ \sin^2 s+\cos^2 s=1,\\<br />
2)\ (1+s)^{\alpha}(1+s)^{\beta}=(1+s)^{\alpha+\beta},\\<br />
3)\ e^{\ln(1-s)^{-1}}=(1-s)^{-1},\\<br />
\displaystyle<br />
4)\ \ln(1+s)=s-{1\over 2}s^2+{1\over 3}s^3-\ldots+{(-1)^{n+1}\over n}s^n+\ldots,\\[3mm]<br />
5)\ \ln(1-s)^{-\alpha}=\alpha\ln(1-s)^{-1}<br />
\end{array}

3. Деление производящих функций

С делением производящих функций дело обстоит сложнее. Так, например, не существует формального степенного ряда B(s), такого, что sB(s)=1.

Утверждение. Пусть A(s) — формальный степенной ряд, такой, что A(0)\ne0. Тогда существует единственный формальный степенной ряд B(s), такой, что A(s)B(s)=1.

Доказательство. Проведем доказательство по индукции. b_0=1/a_0. Пусть теперь все коэффициенты ряда B вплоть до степени n однозначно определены. Коэффициент при степени n+1 определяется из условия a_0b_{n+1}+a_1b_n+\ldots+a_{n+1}b_0=0. Это линейное уравнение относительно b_{n+1}, причем a_0\ne0. Поэтому это уравнение имеет единственное решение.

Замечание. Только что доказанное утверждение очевидно неверно, если мы рассматриваем формальные степенные ряды с целыми коэффициентами. Оно будет верно только в том случае, если a_0=\pm1.

4. Производящая функция для последовательности чисел Фибоначчи

Последовательность чисел Фибоначчи определяется соотношением f_0=0,f_1=1, f_{n+2}=f_{n+1}+f_n при n\ge0. Ее члены 0,1,1,2,3,5,8,13,21,\ldots Выведем производящую функцию для этой последовательности.

Определяющее соотношение для последовательности означает, что ее производящая функция Fib(s)=s+s^2+2s^3+3s^4+5s^5+\ldots удовлетворяет соотношению (Fib(s)-s)/s=Fib(s)+Fib(s)s, откуда Fib(s)=s/(1-s-s^2).

Представим дробь в виде суммы простейших дробей:

\begin{array}{l}<br />
\displaystyle<br />
{s\over 1-s-s^2}=-{5+\sqrt{5}\over 10s_1}\cdot{1\over 1-{s\over s_1}}- {5-\sqrt{5}\over 10s_2}\cdot{1\over 1-{s\over s_2}}=\\[5mm]<br />
\displaystyle<br />
=-{5+\sqrt{5}\over 10\cdot{-1-\sqrt{5}\over 2}}\left(1+{s\over s_1}+{s^2\over s_1^2}+\dots\right)-{5-\sqrt{5}\over 10\cdot{-1+\sqrt{5}\over 2}}\left(1+{s\over s_2}+{s^2\over s_2^2}+\ldots\right)=\\[5mm]<br />
\displaystyle<br />
=-{1\over \sqrt{5}}\left(1+{s\over s_1}+{s^2\over s_1^2}+\ldots\right)+ {1\over \sqrt{5}}\left(1+{s\over s_2}+{s^2\over s_2^2}+\ldots\right),<br />
\end{array}

здесь s_1=-(1+\sqrt{5})/2,s_2=(-1+\sqrt{5})/2.

Отсюда

\begin{array}{l}\displaystyle<br />
f_n={1\over \sqrt{5}}(s_2^{-n}-s_1^{-n})={(-1)^n\over<br />
\sqrt{5}}(s_1^n-s_2^n)=\\[5mm]<br />
\displaystyle<br />
={(-1)^n\over \sqrt{5}}\left(\left({-1-\sqrt{5}\over 2}\right)^n-\left({-1+\sqrt{5}\over 2}\right)^n\right).<br />
\end{array}

Здесь мы воспользовались тем, что s_1s_2=-1.

5. Числа Каталана

Еще одна известная последовательность: последовательность Каталана 1,1,2,5,14,42,132,\ldots Она задается соотношением c_0=1, c_{n+1}=c_0c_n+c_1c_{n-1}+c_2c_{n-2}+\ldots+c_nc_0. Так, например, при n=4 получаем c_4=14=1\cdot5+1\cdot2+2\cdot1+5\cdot1.

Рассмотрим производящую функцию для чисел Каталана:

Cat(s)=c_0+c_1s+c_2s^2+c_3s^3+\ldots=1+s+2s^2+5s^3+14s^4+\ldots

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

Cat(s)=sCat(s)Cat(s)+1,

из которого легко найти саму производящую функцию

\displaystyle Cat(s)={1-\sqrt{1-4s}\over 2s}.

Этот вид производящей функции позволяет найти формулу для чисел Каталана. Согласно общей формуле бинома Ньютона имеем

\displaystyle c_n={(1/2)(1/2)(3/2)\ldots((2n-1)/2)4^{n+1}\over 2(n+1)!},

или, умножая числитель и знаменатель на n! и сокращая на 2^{n+1}, получаем

\displaystyle c_n={(2n)!\over n!(n+1)!}={1\over n+1}{\sf C}_{2n}^n.

Эта формула дает и более простое рекуррентное соотношение для чисел Каталана:

\displaystyle c_{n+1}=c_n{4n+2\over n+2}.

6. Рациональные производящие функции

Теорема. Пусть последовательность a_0,a_1,\ldots,a_k,\ldots задается линейным рекуррентным соотношением порядка k

a_{n+k}=c_{k-1}a_{n+k-1}+c_{k-2}a_{n+k-2}+\ldots+c_0a_n,

и числа a_0,a_1,\ldots,a_{k-1} фиксированы. Тогда производящая функция A(s)=a_0+a_1s+a_2s^2+\ldots рациональна, \displaystyle A(s)={P(s)\over Q(s)}, причем степень многочлена Q(s) равна k, а степень P(s) не превосходит k-1.

Доказательство теоремы, по существу, повторяет рассуждение для чисел Фибоначчи. Рекуррентное соотношение можно переписать в виде уравнения на производящую функцию:

\begin{array}{l}<br />
A(s)-a_{k-1}s^{k-1}a_{k-2}s^{k-2}-\ldots-a_0=\\<br />
=c_{k-1}(A(s)-a_{k-2}s^{k-2}-a_{k-3}s^{k-3}-\ldots-a_0)s+\ldots+c_0A(s)s^k.<br />
\end{array}

Разрешая это линейное уравнение относительно A(s), получаем утверждение теоремы.

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

Теорема. Пусть \displaystyle A(s)={P(s)\over Q(s)}, причем степень многочлена Q(s) равна k, а степень P(s) меньше k. Тогда коэффициенты производящей функции A(s) удовлетворяют линейному рекуррентному соотношению с постоянными коэффициентами.

Скажем несколько слов о производящих функциях несколько более общего вида.

Пусть \displaystyle A(s)={P(s)\over Q(s)} и степень многочлена P(s) не меньше степени многочлена Q(s). Тогда A(s) можно представить в виде \displaystyle A(s)=P_1(s)+{P_2(s)\over Q(s)}, и степень многочлена P_2(s) уже меньше степени Q(s). Тем самым, по предыдущей теореме, коэффициенты данной функции удовлетворяют линейному рекуррентному соотношению, начиная с некоторого номера. Обратное утверждение, очевидно, тоже справедливо.

7. Произведение Адамара рациональных производящих функций

Определение. Произведением Адамара производящих функций

A(s)=a_0+a_1s+a_2s^2+\ldots и B(s)=b_0+b_1s+b_2s^2+\ldots

называется производящая функция

A\circ B(s)=a_0b_0+a_1b_1s+a_2b_2s^2+\ldots

Таким образом, произведение Адамара двух последовательностей — это последовательность, состоящая из почленных произведений соответственных членов этих последовательностей.

Лемма. Производящая функция для последовательности a_0,a_1,a_2,\ldots рациональна тогда и только тогда, когда существуют такие числа q_1,q_2,\ldots,q_l и такие многочлены p_1(n),p_2(n),\ldots,p_l(n), что начиная с некоторого номера n

a_n=p_1(n)q_1^n+p_2(n)q_2^n+\ldots+p_l(n)q_l^n .

Выражение в правой части этого равенства называется квазимногочленом от переменной n.

Доказательство. Заметим прежде всего, что производящая функция (1-qs)^{-k} имеет вид

\begin{array}{l}<br />
(1-qs)^{-k}=1-\left(\begin{array}{r}<br />
-k\\ 1<br />
\end{array}\right)qs+\left(\begin{array}{r}<br />
-k\\ 2<br />
\end{array}\right)q^2s^2-\left(\begin{array}{r}<br />
-k\\ 3<br />
\end{array}\right)q^3s^3+\ldots=\\[2mm]<br />
=1+\left(\begin{array}{r}<br />
k\\ 1<br />
\end{array}\right)qs+\left(\begin{array}{c}<br />
k+1\\ 2<br />
\end{array}\right)q^2s^2+\left(\begin{array}{c}<br />
k+2\\ 3<br />
\end{array}\right)q^3s^3+\dots=\\[2mm]<br />
=1+\left(\begin{array}{c}<br />
k\\ k-1<br />
\end{array}\right)qs+\left(\begin{array}{c}<br />
k+1\\ k-1<br />
\end{array}\right)q^2s^2+\left(\begin{array}{c}<br />
k+2\\ k-1<br />
\end{array}\right)q^3s^3+\ldots<br />
\end{array}

Коэффициент при s^n в этой производящей функции равен

\displaystyle {(n+1)(n+2)\ldots(n+k-1)\over (k-1)!}q^n=P_{k-1}(n)q^n,

где P_{k-1}(n) — многочлен от n степени k-1. Всякая рациональная функция от переменной s представляется виде линейной комбинации многочлена и простейших дробей вида (1-qs)^{-k_i}, поэтому коэффициенты соответствующей производящей функции являются квазимногочленами.

Наоборот, предположим, что коэффициенты производящей функции, начиная с некоторого номера, представляются в виде квазимногочлена. Покажем, что в случае квазимногочлена p(n)q^n соответствующая производящая функция рациональна.

Пусть степень многочлена p равна k-1. Многочлены P_0,P_1,\ldots,P_{k-1}, коэффициенты которых определяются равенством, приведенным выше, образуют базис в пространстве многочленов степени не выше k-1. Действительно, любая последовательность многочленов степеней 0,1,\ldots,k-1 образует базис в этом пространстве. Поэтому многочлен p представляется в виде линейной комбинации многочленов P_i, и соответствующая производящая функция есть просто линейная комбинация функций (1-qs)^{-j}, j=\overline{0,k-1}. Для произвольного квазимногочлена мы получаем линейную комбинацию функций такого вида при различных q_i. Лемма доказана.

Теорема. Произведение Адамара двух рациональных производящих функций рационально.

Доказательство. Принимая в расчет лемму, для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы, приведенной в лемме.

8. Дифференцирование и интегрирование производящих функций

Определение. Пусть A(s)=a_0+a_1s+a_2s^2+\ldots — производящая функция. Производной этой функции называется функция

A^{\prime}(s)=a_1+2a_2s+3a_3s^2+\ldots+na_ns^{n-1}+\ldots

Интегралом этой функции называется функция

\displaystyle \int A(s)=a_0s+a_1{s^2\over 2}+a_2{s^3\over 3}+\ldots+a_n{s^{n+1}\over n+1}+\ldots

Замечание. Нетрудно видеть, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

\displaystyle \int A(s)=\int_0^sA(\xi)d\xi.

Это позволяет находить производящие функции для большого числа разнообразных последовательностей. Найдем, например, производящую функцию

\displaystyle f(s)={1\over 1\cdot2}+{s\over 2\cdot3}+{s^2\over 3\cdot4}+\ldots+{s^n\over (n+1)(n+2)}+\ldots

Легко видеть, что

\displaystyle (s^2f(s))^{\prime}=s+{1\over 2}s^2+{1\over 3}s^3+\dots=\ln(1-s)^{-1},

поэтому

\displaystyle f(s)=s^{-2}\int\ln(1-s)^{-1} =s^{-2}\left((s-1)\ln(1-s)^{-1}+s\right).

Задачи.

1. Решите последовательности

а) a_n=-2a_{n-1}+a_{n-2}+2a_{n-3}, a_1=-2, a_2=6, a_3=-8.

б) a_n=a_{n-1}+a_{n-2}-a_{n-3}, a_1=-1, a_2=5, a_3=3.

2. Докажите равенства (3)–(7).

3. Найдите производящие функции для последовательностей

а) 1,q,q^2,q^3,\ldots;

б) 1,2,3,4,5,6,\ldots;

в) 2,6,12,\ldots,(k+1)(k+2),\ldots.

4. Рациональны ли производящие функции для последовательностей

а) 1,4,9,16,\ldots,k^2,\ldots;

б) 1,1/4,1/9,1/16,\ldots,1/k^2,\ldots?

5. Пусть A(s)=a_0+a_1s+a_2s^2+\ldots — производящая функция для последовательности a_0,a_1,a_2,\ldots Найдите производящие функции для последовательностей

а) a_0+a_1,a_1+a_2,a_2+a_3,a_3+a_4,\ldots;

б) a_0,a_0+a_1,a_0+a_1+a_2,a_0+a_1+a_2+a_3,\ldots

6. Пользуясь производящей функцией для чисел Фибоначчи, доказать для них тождества

а) f_0+f_1+\ldots+f_n=f_{n+2}-1;

б) f_0+f_2+\ldots+f_{2n}=f_{2n+1}-1;

в) f_1+f_3+\ldots+f_{2n-1}=f_{2n};

г) f_0^2+f_1^2+\ldots+f_n^2=f_nf_{n+1}.

7. Пусть \displaystyle a_n=\sum_{r=0}^n{1\over {\sf C}_n^r}. Докажите, что

\displaystyle a_n=1+a_{n-1}{n+1\over 2n}.

Докажите, что \displaystyle\lim_{n\to\infty}a_n=2.

8. Последовательность a_n такова, что

\displaystyle a_0=\alpha, a_1=\beta, a_{n+1}=a_n+{a_{n-1}-a_n\over 2n}.

Найдите \displaystyle\lim_{n\to\infty}a_n.

9. Пусть a_n=(n^2+1)3^n. Найдите рекуррентное уравнение

a_n+pa_{n+1}+qa_{n+2}+ra_{n+3}=0.

Оцените сходимость и вычислите \displaystyle \sum_{n=0}^{\infty}a_nx^n.

10. Пусть

\displaystyle<br />
{1\over 1-2x-x^2}=s_0+s_1x+s_2x^2+\ldots

Доказать, что для некоторого f(n) s_n^2+s_{n+1}^2=s_{f(n)}.

11. Доказать, что при любых натуральных k

\displaystyle \varphi_k={(2k-2)!\over k!(k-1)!}={1\over 2k-1}{\sf C}_{2k-1}^k

— целые числа, удовлетворяющие рекуррентному соотношению

\varphi_n=\sum_{i=1}^{n-1}\varphi_i\varphi_{n-i}.

12. Пусть

\displaystyle {(1+x)^n\over (1-x)^3}=a_0+a_1x+a_2x^2+\ldots

Докажите, что

\displaystyle a_0+a_1+a_2+\ldots+a_{n-1}={n\over 3}(n+2)(n+7)\cdot2^{n-4}.

Источник: С.К. Ландо “Лекции о производящих функциях”, МЦНМО, Москва, 2004.

Комментариев: 16

  1. 1 Ербол:

    Здесь одно простое применение ПФ:Алданов Е.С., Базарбаев С.К., Нурлыбай Н.А. ПРИМЕНЕНИЕ МЕТОДА ПРОИЗВОДЯЩИХ ФУНКЦИЙ ДЛЯ РЕШЕНИЯ РАЗНОСТНЫХ УРАВНЕНИЙ // Материалы V Международной студенческой электронной научной конференции «Студенческий научный форум» URL: http://www.scienceforum.ru/2013/94/4208 (дата обращения: 19.02.2013).

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Ербол, к сожалению, там формул не видно. Или это только у меня?

    [Ответить]

  2. 2 Igor:

    в интернете много материала о решении рекуррентных соотношений одной переменной. Но я вот наткнулся на такое: f(m,n) = f(m,n-1) + f (m-1,n). f(m,0) = 0, f (o,n) = 0 . Не подскажите, как решить? )

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Igor, посмотрите функциональные уравнения. Например, здесь: http://ermine.narod.ru/MATH/STAT/Funceq/sect0.html#vved
    Только там что-то не все стало корректно отображаться (

    А здесь я бы уменьшала m (или n) до получения f(0,n) (или f(m,0)) и искала бы закономерность.

    [Ответить]

    zbl Reply:

    Эйлер придумал: линейным уравнениям удовлетворяют экспоненты, поэтому ищем решение в виде f(m,n)=a^m b^n тогда a^m b^n = \frac{a^m b^n}{b} + \frac{a^m b^n}{a}. Отсюда характеристическое уравнение: 1 = \frac{1}{b} + \frac{1}{a}. Для любых a и b, которые удовлетворяют характеристическому уравнению, a^m b^n удовлетворяет рекуррентному. Но такие начальные условия не выполнимы: наверно, имелось в виду f(m,0)=f(0,n)=1?.

    [Ответить]

    zbl Reply:

    Ах да, и f(m,0) не может быть константой-то вообще ж.

    [Ответить]

    Геннадий Reply:

    Уважаемые Igor и Елизавета Александровна! Наткнулся на Ваш пример и не мог не ответить (если, конечно, еще не поздно).
    Проще начать с меньших значений m и n.
    Если f(1,0)=0, f(0,1)=0, то f(1,1) = 0.
    Далее f(2,1) = f (1,1) + f(2,0) = 0.
    Подключая индукцию, получаем f(m,n)=0
    для целочисленных положительных аргументов.

    [Ответить]

  3. 3 Igor:

    спасибо за помощь) уже разобрался

    [Ответить]

  4. 4 Александр:

    это действительно для школьников? то есть на олимпиадах такие задания???

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Для школьников и студентов. Зависит от уровня олимпиады, иногда может оказаться полезным.

    [Ответить]

  5. 5 jem:

    А посоветуете литературу?
    А для многих переменных?

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Посмотрите книгу С.К. Ландо “Лекции о производящих функциях”, МЦНМО, Москва, 2004. Там есть и для многих переменных. И ссылки в этой книге тоже гляньте, может, что-то поможет.

    [Ответить]

    Александр Reply:

    Скажите, вы нашли литературу по производящим функциям нескольких переменных.

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Увы, нет. Ничего кроме С.К. Ландо посоветовать не могу.

    [Ответить]

  6. 6 Меня терзают смутные сомнения...:

    Кому-то может помочь книга Herbert Wilf “generatingfunctionology”. Второе издание есть в свободном доступе, например на сайте автора
    http://www.math.upenn.edu/~wilf/DownldGF.html
    Там есть два примера с двумя переменными – главы 1.5 и 1.6.
    Книга открывается следующим определением: “Производящая функция это бельевая веревка на которую мы вывешиваем последовательность чисел напоказ”.

    [Ответить]

  7. 7 Геннадий:

    Немного о числах Каталана (см. раздел 5). Последнее рекуррентное соотношение для чисел Каталана действительно очень простое. И что интересно, с его помощью можно получить более простую и наглядную формулу общего члена последовательности Каталана
     c_n = 2^n \cdot \frac {(2n-1)!!} {(n+1)!}
    В числителе дроби двойной факториал – произведение нечетных чисел  1 \cdot 3 \cdot 5 \cdots (2n-1).
    Вывод формулы можно посмотреть здесь http://eremin.magekit.com/catalan/sample-page/
    Эта аналитическя зависимость получила название формула факторизации, поскольку используется для факторизации чисел Каталана. Например, из формулы видно “невооруженным глазом”, что все простые числа из открытого интервала числовой оси  (n+1; 2n) гарантированно попадают в разложение числа Каталана с индексом n.

    [Ответить]

Оставьте свой отзыв

Добавить изображение