Сумма биномиальных коэффициентов

[Andrey A]

Добрый день! Можно упростить такую штуку:

$$\begin{pmatrix} n \\ m \end{pmatrix}+\begin{pmatrix} n+k \\ m-1 \end{pmatrix}+\begin{pmatrix} n+2k \\ m-2 \end{pmatrix}+...+\begin{pmatrix} n+(m-1)k \\ 1 \end{pmatrix}+\begin{pmatrix} n+mk \\ 0 \end{pmatrix}\ ?$$

Не приходилось как-то сталкиваться с этим вплотную.

[kthxbye]

На MSE есть один товарищ, некий Markus Scheuer, который ворочает такими вот штуками. Однако в большинстве случаев его можно отметить, как популяризатора оператора coefficient of, то бишь коэффициента при $z^n$ из разложения заданной функции $A(z)$ в бесконечный ряд.

Чем чаще на глаза попадаются его ответы, тем сильнее возникает желание и самому провернуть что-нибудь эдакое. А почему бы и нет? Давайте попробуем.

Поскольку $(1+z)^n=\sum\limits_{q=0}^n \binom{n}{q}z^q$ мы можем сказать, что

$$\begin{align*} [z^q](1+z)^n=\binom{n}{q} \end{align*}$$

Собственно, приступаем:

$$\begin{align*} \color{blue}{\sum_{q=0}^m}&\color{blue}{\binom{n+(m-q)k}{q}}\\ &=\sum_{q=0}^m[z^q](1+z)^{n+mk-qk}\\ &=[z^0](1+z)^{n+mk}\sum_{q=0}^m(z(1+z)^k)^{-q}\\ &=[z^0]\frac{(1+z)^{n+mk}}{(z(1+z)^k)^m}\frac{1-(z(1+z)^k)^{m+1}}{1-z(1+z)^k}\\ &\,\,\color{blue}{=[z^m]\frac{(1+z)^n(1-(z(1+z)^k)^{m+1})}{1-z(1+z)^k}} \end{align*}$$

Пояснения:

• В 1-ом тождестве мы применяем этот самый оператор.
  
• Во 2-ом используем $[z^{p-q}]A(z)=[z^p]z^qA(z)$.
  
• В 3-ем находим сумму конечной геометрической прогрессии $\sum\limits_{q=0}^nz^q=\frac{1-z^{n+1}}{1-z}$.
  
• В 4-ом опять $[z^{p-q}]A(z)=[z^p]z^qA(z)$, ну и сокращаем.

Что же на теперь со всем этим ужасом делать? Посмотрим вниз, на знаменатель. Что ты такое? Подставим $k=1$. Та-дам! Генеративная функция чисел Фибоначчи (смещенных на единицу). Но как это нам поможет? А вот как:

$$[z^m]\frac{(1+z)^n(1-(z(1+z))^{m+1})}{1-z-z^2}=[z^m](1+z)^n\sum_{p=0}^{\infty}F_{p+1}z^p=\sum_{q=0}^{\min(n,m)}\binom{n}{q}F_{m-q+1}$$

Куда же делся второй множитель в числителе? Все очень просто - скрипач не нужен в нем больше нет необходимости. При умножении на него всего остального нам полезна только единица. Оставшаяся часть $-(z(1+z))^{m+1}$ влияет на $[z^m]$ только если мы умножаем её на $z^q$ где $q<0$, а таких членов в нашей преобразованной версии нет.

Осталось только отметить, что

$$a_k(n)=\begin{cases} 0,&\text{если $n<0$;}\\ 1,&\text{если $n=0$;}\\ \sum\limits_{p=0}^k\binom{k}{p}a_k(n-p-1),&\text{если $n>0$.} \end{cases}$$

$$\color{blue}{\sum_{q=0}^m}&\color{blue}{\binom{n+(m-q)k}{q}}=\color{blue}{\sum_{q=0}^{\min(n,m)}}&\color{blue}{\binom{n}{q}a_k(m-q)}$$

[Andrey A]

kthxbye спасибо, интересно. Помнится, тема возникла отсюда. Исходя из Вашего результата, видимо там возможны обобщения (касается последней формулы, да и предыдущего поста). Я к сожалению давно этим не занимался, нужно время подумать.

[arseniiv]

kthxbye в сообщении #1397841 писал(а):

Генеративная функция

В русской терминологии прижилось «производящая».

[Ms-dos4]

Andrey A
Можно использовать представление биномиального коэффициента через вычеты
$$C_n^k = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(1 + z)}^n}} \over {{z^{k + 1}}}}dz} $ $
Тогда искомая сумма

$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}} = {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {\sum\limits_{j = 0}^m {{{{{(1 + z)}^{n + jk}}} \over {{z^{m - j + 1}}}}} dz} = - {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^n}} \over {{z^{m + 1}}[z{{(z + 1)}^k} - 1]}}dz} + {1 \over {2\pi i}}\int\limits_{\left| z \right| = \varepsilon } {{{{{(z + 1)}^{n + k(m + 1)}}} \over {z{{(z + 1)}^k} - 1}}dz} $$

Второй интеграл равен нулю, что окончательно даёт

$$\sum\limits_{j = 0}^m {C_{n + jk}^{m - j}} = {1 \over {m!}}{\left. {{{{\partial ^m}} \over {\partial {z^m}}}[{{{{(z + 1)}^n}} \over {1 - z{{(z + 1)}^k}}}]} \right|_{z = 0}}$$

Если ещё постараться, возможно удастся выразить ответ через спецфункции (математика подсказывает, что ответ выражается через обобщенную гипергеометрическую функцию, но возиться лень).

[Andrey A]

Ms-dos4 моего образования к сожалению не хватает чтобы оценить Ваш результат, но всё равно очень интересно. Скопирую с Вашего позволения текст чтобы увязать с первоначальной темой. Задача оказывается решаемой, но не до конца. Надо же...

[B@R5uk]

С вычетами, конечно, всё красиво и хорошо, но с вычислительной точки зрения один сложный крокодил заменяется ещё более сложным и страшным крокодилом. Потому что вычислять энную производную от простой дроби не айс, а здесь дробь с полиномами произвольной степени. Хотя запись выглядит красиво, чего есть, того не отнять.

[kthxbye]

Всё-таки отмечу, что OEIS намекнул на связь $a_k(n)$ с вашим $F^{(k)}_{n}$, а именно $a_k(n)=F^{(k+1)}_{nk+1}$, и учитывая, что

$$F^{(k)}_{n}=F^{(k)}_{n-1}+F^{(k)}_{n-k}=\sum\limits_{p=0}^q\binom{q}{p}F^{(k)}_{n-q+p(1-k)}$$

ничего нового мы по сути не открыли. Ну разве что саму $a_k(n)$, статьи про которую могут на что-то пролить свет.

[Andrey A]

kthxbye в сообщении #1398309 писал(а):

... ничего нового мы по сути не открыли.

Очередная красивая закономерность. Одна из... Как этим воспользоваться не представляю. Что ж, всем спасибо за участие.