2014 dxdy logo

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

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


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


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



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


21/11/12
1630
Санкт-Петербург
Добрый день! Можно упростить такую штуку:
$$\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
428
На 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
1630
Санкт-Петербург
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
1630
Санкт-Петербург
Ms-dos4 моего образования к сожалению не хватает чтобы оценить Ваш результат, но всё равно очень интересно. Скопирую с Вашего позволения текст чтобы увязать с первоначальной темой. Задача оказывается решаемой, но не до конца. Надо же...

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


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

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


22/11/13
428
Всё-таки отмечу, что 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
1630
Санкт-Петербург
kthxbye в сообщении #1398309 писал(а):
... ничего нового мы по сути не открыли.

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

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

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



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

Сейчас этот форум просматривают: gris


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

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