|
Краткие сообщения
О некоторых тождествах с биномиальными коэффициентами
В. А. Воблый
Всероссийский институт научной и технической информации РАН, г. Москва
Ключевые слова:
биномиальный коэффициент, тождество, гамма-функция, гипергеометрическая функция.
Поступило: 15.05.2022
Различные комбинаторные тождества часто возникают при перечислении графов [1], [2]. В заметке единообразно получены несколько тождеств с биномиальными коэффициентами.
Для действительного числа $a$ биномиальный коэффициент $\binom{a}{n}$ понимается как отношение соответствующих гамма-функций [3; с. 757]
$$
\begin{equation*}
\binom{a}{n}=\frac{\Gamma(a+1)}{\Gamma(n+1)\Gamma(a-n+1)}\,.
\end{equation*}
\notag
$$
Теорема 1. Для любого целого числа $n\geqslant 0$ и любого действительного числа $q\geqslant 0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\binom{n-s+q}{q}2^{-s} =\frac{2^n\Gamma(n+q/2+1)}{n!\,\Gamma(q/2+1)}\,.
\end{equation}
\tag{1}
$$
Доказательство. Введем обозначение
$$
\begin{equation*}
S_n(q,x)=\sum_{s=0}^n\binom{n+s}{s}\binom{n-s+q}{q}x^s.
\end{equation*}
\notag
$$
$$
\begin{equation*}
\begin{aligned} \, S_n(q,x)&=\frac{1}{n!\,q!}\sum_{s=0}^n\frac{(n+s)!\,(n-s+q)!}{s!\,(n-s)!}\,x^s \\ &=\frac{1}{(n!)^2q!}\sum_{s=0}^n\binom{n}{s}\Gamma(n+s+1)\Gamma(n-s+q+1)x^s. \end{aligned}
\end{equation*}
\notag
$$
$$
\begin{equation*}
B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} =\int_0^1t^{x-1}(1-t)^{y-1}\,dt,
\end{equation*}
\notag
$$
$$
\begin{equation*}
\begin{aligned} \, S_n(q,x) &=\frac{(2n+q+1)!}{(n!)^2q!}\sum_{s=0}^n\binom{n}{s}B(n+s+1,n-s+q+1)x^s \\ &=\frac{(2n+q+1)!}{(n!)^2q!}\sum_{s=0}^n\binom{n}{s}x^s \int_0^1t^{n+s}(1-t)^{n-s+q}\,dt. \end{aligned}
\end{equation*}
\notag
$$
$$
\begin{equation*}
\begin{aligned} \, S_n(q,x) &=\frac{(2n+q+1)!}{(n!)^2q!} \int_0^1t^n(1-t)^{n+q}\sum_{s=0}^n\binom{n}{s} \biggl(\frac{tx}{1-t}\biggr)^s\,dt \\ &=\frac{(2n+q+1)!}{(n!)^2q!} \int_0^1t^n(1-t)^q(1-t(1-x))^n\,dt. \end{aligned}
\end{equation*}
\notag
$$
$$
\begin{equation*}
F(a,b;c;z)=\frac{\Gamma(c)}{\Gamma(b)\Gamma(c-b)} \int_0^1t^{b-1}(1-t)^{c-b-1}(1-tz)^{-a}\,dt.
\end{equation*}
\notag
$$
$$
\begin{equation}
S_n(q,x)=\binom{2n+q+1}{n}F(-n,n+1;n+q+2;1-x).
\end{equation}
\tag{2}
$$
$$
\begin{equation*}
F\biggl(a,1-a;b;\frac{1}{2}\biggr) =\frac{2^{1-b}\Gamma(b)\Gamma(1/2)}{\Gamma((a+b)/2)\Gamma((b-a+1)/2)}
\end{equation*}
\notag
$$
$$
\begin{equation*}
S_n\biggl(q,\frac{1}{2}\biggr) =\frac{(2n+q+1)!}{n!\,(n+q+1)!} \frac{2^{-n-q-1}\Gamma(n+q+2)\sqrt{\pi}}{\Gamma(q/2+1)\Gamma((2n+q+3)/2)}\,.
\end{equation*}
\notag
$$
$$
\begin{equation*}
\Gamma(2z)=\frac{2^{2z-1}}{\sqrt{\pi}}\,\Gamma(z)\Gamma\biggl(z+\frac{1}{2}\biggr)
\end{equation*}
\notag
$$
$$
\begin{equation*}
S_n\biggl(q,\frac{1}{2}\biggr) =\frac{2^{-n-q-1}2^{2n+q+1}\Gamma(n+q/2+1)\Gamma((2n+q+3)/2)} {n!\,\Gamma(q/2+1)\Gamma((2n+q+3)/2)} =\frac{2^n\Gamma(n+q/2+1)}{n!\,\Gamma(q/2+1)}\,.
\end{equation*}
\notag
$$
Следствие 1. Для любых целых чисел $n\geqslant 0$, $q\geqslant0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\binom{n-s+q}{q}2^{-s} =\frac{(2n+q)!!}{n!\,q!!}\,.
\end{equation}
\tag{3}
$$
Доказательство. С учетом тождества для гамма-функции [4; с. 17]
$$
\begin{equation}
\Gamma(z+n)=z(z+1)\dotsb(z+n-1)\Gamma(z)
\end{equation}
\tag{4}
$$
$$
\begin{equation*}
\begin{aligned} \, \frac{2^n\Gamma(n+q/2+1)}{n!\,\Gamma(q/2+1)} &=\frac{2^n(q/2+1)(q/2+2)\dotsb(q/2+1+n-1)\Gamma(q/2+1)}{n!\,\Gamma(q/2+1)} \\ &=\frac{(2n+q)!!}{n!\,q!!}\,. \end{aligned}
\end{equation*}
\notag
$$
Отметим, что формула (3) была получена в диссертации автора [5] с помощью гипергеометрической функции, а В. К. Леонтьев доказал ее другим путем [6; с. 20, 91–92].
Следствие 2. Для любого целого числа $n\geqslant 0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\frac{(2n-2s+1)!!}{(n-s)!} =\frac{1\cdot 5\cdot 9\dotsb(4n+1)}{n!}\,.
\end{equation}
\tag{5}
$$
Доказательство. Из формулы (1) при $q=1/2$ имеем
$$
\begin{equation*}
\sum_{s=0}^n\binom{n+s}{s} \begin{pmatrix} n-s+\dfrac{1}{2} \\ \dfrac{1}{2} \end{pmatrix}2^{-s} =\frac{2^n\Gamma(n+1/4+1)}{n!\,\Gamma(1/4+1)}\,.
\end{equation*}
\notag
$$
$$
\begin{equation*}
\Gamma\biggl(n+\frac{1}{2}\biggr) =\frac{\sqrt{\pi}}{2^n}(2n-1)!!, \qquad \Gamma\biggl(n+\frac{1}{4}\biggr) =\frac{1\cdot 5\cdot 9\dotsb(4n-3)}{4^n}\,\Gamma\biggl(\frac{1}{4}\biggr).
\end{equation*}
\notag
$$
$$
\begin{equation*}
\begin{gathered} \, \begin{pmatrix} n-s+\dfrac{1}{2} \\ \dfrac{1}{2} \end{pmatrix} =\frac{\Gamma(n-s+1+1/2)}{(n-s)!\,\Gamma(1/2+1)} =\frac{\sqrt{\pi}}{2^{n-s+1}}\frac{(2n-2s+1)!!}{(n-s)!\,(1/2)\sqrt{\pi}}\,, \\ \frac{2^n\Gamma(n+1/4+1)}{n!\,\Gamma(1/4+1)} =\frac{2^n1\cdot 5\cdot9\dotsb(4n+1)\Gamma(1/4)}{n!\,4^{n+1}(1/4)\Gamma(1/4)}\,, \\ \sum_{s=0}^n\binom{n+s}{s}\frac{(2n-2s+1)!!}{2^{n-s}(n-s)!\,2^s} =\frac{1\cdot 5\cdot 9\dotsb(4n+1)}{2^nn!}\,. \end{gathered}
\end{equation*}
\notag
$$
Теорема 2. Для любого целого числа $n\geqslant 0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\binom{2n-s}{n}(-1)^s =\frac{\Gamma(3n/2+1)}{n!\,\Gamma(n/2+1)}\frac{1+(-1)^n}{2}\,.
\end{equation}
\tag{6}
$$
Доказательство. Из формулы (2) при $q=n$ и $x=-1$ имеем
$$
\begin{equation*}
S_n(n,-1)=\binom{3n+1}{n}F(-n,n+1;2n+2;2).
\end{equation*}
\notag
$$
$$
\begin{equation*}
F(-n,a;2a;2)=\frac{n!\,2^{-n-1}\Gamma(a+1/2)(1+(-1)^n)}{(n/2)!\,\Gamma(a+(n+1)/2)}\,.
\end{equation*}
\notag
$$
$$
\begin{equation*}
\begin{aligned} \, S_n(n,-1) &=\frac{n!\,\Gamma(n+1+1/2)(1+(-1)^n)\Gamma(3n+2)} {2^{n+1}\Gamma(n/2+1)\Gamma(3n/2+1+1/2)n!\,\Gamma(2n+2)} \\ &=\frac{\Gamma(n+1+1/2)(1+(-1)^n)(1/\sqrt{\pi})\, 2^{3n+1}\Gamma(3n/2+1)\Gamma(3n/2+1+1/2)} {2^{n+1}\Gamma(n/2+1)\Gamma(3n/2+1+1/2)n!\,(1/\sqrt{\pi})2^{2n+1}\Gamma(n+1+1/2)} \\ &=\frac{\Gamma(3n/2+1)}{n!\,\Gamma(n/2+1)}\,\frac{1+(-1)^n}{2}\,. \end{aligned}
\end{equation*}
\notag
$$
Отметим, что формула (6) является следствием тождества 3.36, данного в книге Гулда [7; с. 26] без доказательства.
Теорема 3. Для любого целого числа $n\geqslant 0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\binom{2n-s}{n}2^s =\frac{2^{2n}\Gamma(3n/2+1)}{n!\,\Gamma(n/2+1)}\,.
\end{equation}
\tag{7}
$$
Доказательство. Из формулы (2) при $q=n$ и $x=2$ имеем
$$
\begin{equation*}
S_n(n,2)=\binom{3n+1}{n}F(-n,n+1;2n+2;-1).
\end{equation*}
\notag
$$
$$
\begin{equation*}
F(-n,a;a+1+n;-1) =\frac{2^{2n}\Gamma(a/2+1/2+n)\Gamma(a+n+1)}{\Gamma(a/2+1/2)\Gamma(2n+a+1)}\,.
\end{equation*}
\notag
$$
$$
\begin{equation*}
S_n(n,2) =\frac{(3n+1)!\,2^{2n}\Gamma(3n/2+1)\Gamma(2n+2)} {n!\,(2n+1)!\,\Gamma(n/2+1)\Gamma(3n+2)} =\frac{2^{2n}\Gamma(3n/2+1)}{n!\,\Gamma(n/2+1)}\,.
\end{equation*}
\notag
$$
Следствие 3. Для любого целого числа $n\geqslant 0$ верно тождество
$$
\begin{equation}
\sum_{s=0}^n\binom{n+s}{s}\binom{2n-s}{n}2^s =\frac{2^n(3n)!!}{n!\,n!!}\,.
\end{equation}
\tag{8}
$$
Доказательство. С помощью тождества (4) из формулы (7) получим
$$
\begin{equation*}
\frac{2^{2n}\Gamma(3n/2+1)}{n!\,\Gamma(n/2+1)} =\frac{2^{2n}(n/2+1)(n/2+2)\dotsb(n/2+1+n-1)\Gamma(n/2+1)}{n!\,\Gamma(n/2+1)} =\frac{2^n(3n)!!}{n!\,n!!}\,.
\end{equation*}
\notag
$$
В заключение отметим, что тождества (1), (3), (5), (7), (8) отсутствуют в известных книгах, содержащих множества тождеств с биномиальными коэффициентами [7], [9]–[21].
|
|
|
|
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
|
|
| |
| 1. |
В. А. Воблый, Матер. XVI Международ. семин. “Комбинаторные конфигурации и их приложения”, КНТУ, Кропивницкий, 2019, 30–31 |
| 2. |
В. А. Воблый, Материалы Воронежской международной весенней математической школы “Современные методы теории краевых задач. Понтрягинские чтения–XXXII” Воронеж, 3–9 мая 2021 г. Часть 1, Итоги науки и техн. Сер. Соврем. матем. и ее прил. Темат. обз., 208, ВИНИТИ РАН, М., 2022, 11–14   |
| 3. |
А. П. Прудников, Ю. А. Брычков, О. И. Маричев, Интегралы и ряды. Дополнительные главы, Наука, М., 1986  |
| 4. |
Г. Бейтмен, А. Эрдейи, Высшие трансцендентные функции. Т. 1, Наука, М., 1966 |
| 5. |
В. А. Воблый, Асимптотическое перечисление графов некоторых типов, Дис. $\dots$ к.ф.-м.н., ВЦАН, М., 1985 |
| 6. |
В. К. Леонтьев, Избранные задачи комбинаторного анализа, Изд-во МГТУ им. Н. Э. Баумана, М., 2001 |
| 7. |
H. W. Gould, Combinatorial Identities, West Virginia University, Morgantown, 1972 |
| 8. |
A. Ebisu, Mem. Amer. Math. Soc., 248:1177 (2017)  |
| 9. |
А. П. Прудников, Ю. А. Брычков, О. И. Маричев, Интегралы и ряды. Элементарные функции, Наука, М., 1981 |
| 10. |
Дж. Риордан, Комбинаторные тождества, Наука, М., 1982 |
| 11. |
J. Kaucky, Combinatoricke Identity, Veda, Bratislava, 1975 |
| 12. |
Г. П. Егорычев, Интегральное представление и вычисление комбинаторных сумм, Наука, Новосибирск, 1977 |
| 13. |
А. Грэхем, Д. Кнут, О. Паташник, Конкретная математика, Мир, М., 1998 |
| 14. |
И. С. Градштейн, И. М. Рыжик, Таблицы интегралов сумм, рядов и произведений, Наука, М., 1971 |
| 15. |
Г. П. Гаврилов, А. А. Сапоженко, Задачи и упражнения по дискретной математике, Физматлит, М., 2009 |
| 16. |
Комбинаторный анализ. Задачи и упражнения, ред. К. А. Рыбников, Наука, М., 1982 |
| 17. |
Я. Гульден, Д. Джексон, Перечислительная комбинаторика, Наука, М., 1990 |
| 18. |
В. Н. Сачков, Введение в комбинаторные методы дискретной математики, МЦНМО, М., 2004 |
| 19. |
Ch. A. Charalambides, Enumerative Combinatorics, CRC Press, Boca Raton, 2018 |
| 20. |
L. Lovasz, Combinatorial Problems and Exercises, AMS Chelsea publ., Providence RI, 2007 |
| 21. |
I. Tomescu, Problems in Combinatorics and Graph Theory, Wiley, New York, 1985 |
Образец цитирования:
В. А. Воблый, “О некоторых тождествах с биномиальными коэффициентами”, Матем. заметки, 113:3 (2023), 461–465; Math. Notes, 113:5 (2023), 453–457
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm13585https://doi.org/10.4213/mzm13585 https://www.mathnet.ru/rus/mzm/v113/i3/p461
|
| Статистика просмотров: |
| Страница аннотации: | 177 | | PDF полного текста: | 25 | | HTML русской версии: | 115 | | Список литературы: | 35 | | Первая страница: | 56 |
|
Цитирование в формате AMSBIB
Обратная связь: