Конкретная математика, Упражнение 7.5

[caxap]

Найти производяющую функцию $S(z)$, такую, что

$$[z^n] S(z)=\sum_k \binom r k \binom r {n-2k}$$

В ответе написано, что это свёртка $(1+z^2)^r$ и $(1+z)^r$, поэтому $S(z)=(1+z+z^2+z^3)^r$. Но я вот не могу понять, почему это свёртка и именно этих ПФ?

Ну с множителем $\binom r k$ понятно, ПФ для него $(1+z)^r=\sum_{k\geqslant 0} \binom r k z^k$. А вот со вторым непонятно, более того я не могу найти ПФ для него. $(1+z^2)^r=\sum_{k \geqslant 0} \binom r k z^{2k}}$, а вот как записать в форме $\sum_{k\geqslant 0} a_k z^k$?

И ещё, в Конкретной математике любят не писать явно пределы, а просто пишут $k$ подразумевая суммирование по всем $\mathbb Z$ (т.е. от $-\infty$ до $+\infty$). Вот в первой сумме, я правильно понимаю, что суммирование по $k\geqslant0$ идёт (т.к. бин. коэффициенты при отрицательных k не определены)?

И какой смысл несёт $n$ в сумме?
Вроде бы простая задачка (из разминочных упражнений), а разобраться не могу.

[Хорхе]

Все наоборот. Первый сомножитель как раз отвечает $(1+z^2)^r$. $n$ имеет такой смысл: мы раскрываем скобки, перемножаем и собираем в кучу все члены с $z^n$. Насчет пределов суммирования, обычно полагают ${n\choose k}=0$ при $k<0$ и $k>n$.

[caxap]

Извините, не понял. Можно поподробнее (я только учусь)?

Свёртка $(a_n)$ и $(b_n)$ --- это последовательность $(c_n)$, такая что $c_n=\sum_{k=0}^n a_k b_{n-k}$. ПФ для $(c_n)$ равна произведению двух исходных ПФ.

По виду исходной суммы можно предположить, что $a_k=\binom r k$, $b_k = \binom r {n-2k}$. Так?
Насчёт пределов: первый множитель не равен нулю только при $k\ge 0$, правый при $n-2k \ge 0 \iff k \le \lfloor n/2 \rfloor$ (???). Т. е. получается исходная сумма $\sum\limits_{k\ge 0}^{\lfloor n/2 \rfloor}$, а ведь в определении свёртки должно быть до $n$ суммирование!

-- Сб июл 03, 2010 09:58:20 --

Хорхе в сообщении #336958 писал(а):

мы раскрываем скобки, перемножаем и

Какие скобки?

Хорхе в сообщении #336958 писал(а):

обычно полагают $n\choose k=0$ при $k<0$ и $k>n$.

не понял после "при"

[ИСН]

имелось в виду: $\binom n k = 0$ при...

[meduza]

ИСН в сообщении #336972 писал(а):

имелось в виду: $\binom n k = 0$ при...

Если $n$ не целое, то и при $k>n$ в общем случае $\displaystyle \binom n k =\frac {n^{\underline k}} {k!} \neq 0$. А поскольку в задаче вместо $n$ использован символ $r$, то подразумевается любое вещественное значение.

[caxap]

Ещё есть другое упражнение (7.11). Там просят выразить $C(z)=\sum_n c_n z^n$ через $A(z)=\sum_n a_n z^n$, $B(z)=\sum_n b_n z^n$, если $c_n=\sum\limits_{j+2k=n} a_j b_k$.

Я думаю, $c_n=\sum_{k=0}^n a_{n-2k} b_k$. Т. е. эти задачи похожи. В обоих напоминает свёртку и судя по ответу этим и является), но все портит $2k$.

В ответе, кстати, $C(z)=A(z)B(z)/(1-z)$. Вывести не получается. Те же затруднения, что и с первой задачей (7.5).