2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Сумма биномиальных коэффициентов
Сообщение30.10.2017, 15:37 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Добрый день! Можно упростить такую штуку:
$$\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}\ ?$$
Не приходилось как-то сталкиваться с этим вплотную.

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение05.06.2019, 10:58 
Аватара пользователя


22/11/13
497
На 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)}$$

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение05.06.2019, 11:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение05.06.2019, 19:43 
Заслуженный участник


27/04/09
28128
kthxbye в сообщении #1397841 писал(а):
Генеративная функция
В русской терминологии прижилось «производящая». :-)

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение06.06.2019, 08:50 
Заслуженный участник


25/02/08
2961
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}}$$
Если ещё постараться, возможно удастся выразить ответ через спецфункции (математика подсказывает, что ответ выражается через обобщенную гипергеометрическую функцию, но возиться лень).

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение07.06.2019, 16:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение07.06.2019, 18:07 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение07.06.2019, 18:52 
Аватара пользователя


22/11/13
497
Всё-таки отмечу, что 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)$, статьи про которую могут на что-то пролить свет.

 Профиль  
                  
 
 Re: Сумма биномиальных коэффициентов
Сообщение10.06.2019, 23:05 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
kthxbye в сообщении #1398309 писал(а):
... ничего нового мы по сути не открыли.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group