2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: комбинаторные тождества
Сообщение12.06.2018, 23:32 
Модератор
Аватара пользователя


11/01/06
5660
Тождество 10. Для целых чисел $n>m\geq 0$ докажите, что
$$\sum_{k=0}^n (-1)^k\binom{2n+1}{n-k} (2k+1)^{2m+1} = 0.$$

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение13.06.2018, 06:45 
Заслуженный участник


16/02/13
4105
Владивосток
А кто есть $m$? Произвольное число?

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение13.06.2018, 10:08 
Заслуженный участник
Аватара пользователя


09/09/14
6328
iifat в сообщении #1319522 писал(а):
А кто есть $m$? Произвольное число?
Думаю, что целое неотрицательное. Исхожу из этого:
maxal в сообщении #1319484 писал(а):
Для целых чисел $n>m\geq 0$

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение14.06.2018, 22:15 
Модератор
Аватара пользователя


11/01/06
5660
maxal в сообщении #333354 писал(а):
Тождество 4:
$$\sum_{k=1}^n \binom{n}{k}^2 H_k = \binom{2n}{n}(2H_n-H_{2n}),$$
где $H_m$ - гармонические числа.

С виду кажется очень похожим:

Тождество 11. Для $n\geq 1$, докажите:
$$\sum_{k=1}^n (-1)^{n-k}\binom{n}{k}2^k H_k = 2H_n-H_{\lfloor n/2\rfloor}.$$

(Crux Mathematicorum, problem 3886)

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение15.06.2018, 04:37 


21/05/16
4292
Аделаида
maxal в сообщении #334374 писал(а):
caxap
Подсказка для 4-го:
$$H_k = \int_0^1 \frac{1-x^k}{1-x}\,dx$$
Полезно также вспомнить доказательство тождества:
$$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$$
и попробовать его скомбинировать с вышеприведённым интегралом.

Полное решение доступно по ссылке.

А откуда у вас появляется y?

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение15.06.2018, 15:56 
Модератор
Аватара пользователя


11/01/06
5660
kotenok gav в сообщении #1320066 писал(а):
А откуда у вас появляется y?

Как появляется, так и исчезает - через оператор $[y^n]$ взятия коэффициента при $y^n$.

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение06.12.2019, 00:02 
Модератор
Аватара пользователя


11/01/06
5660
Тождество 12. Для всякого целого $n>0$ докажите, что
$$\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k} \frac{2n-3k}{n-k} 2^k = 2^n.$$

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение20.01.2020, 20:18 


26/04/11
90
Заметим, что $2n-3k=(n-k)+(n-2k)$. (Кстати, Mathematica этого не замечает и выдает в качестве ответа гигантскую простыню ${}_4F_3$ функций.) Поэтому исходная сумма приводится к виду
$$
a_n\stackrel{\rm def}{=}
\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\frac{2n-3k}{n-k}\,2^k
=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\,2^k
+\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-1-k}{k}\,2^k.
$$
Поскольку и исходная сумма, и получившиеся слагаемые являются naturally terminating (не знаю, как благозвучно перевести на русский), то можно суммирование делать по всем целым $k$, а биномиальные коэффициенты сами выберут "своих".

Зная ответ, к исходному равенству можно добавить и случай $a_0=1$, т.е. при $n=0$ трактовать неопределённую дробь как
$$
\frac{2n-3k}{n-k}=\frac{2n-3\cdot\tfrac{n}{2}}{n-\tfrac{n}{2}}=1.
$$

Пусть теперь
$$
\lambda_n(x)\stackrel{\rm def}{=}
\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}\,x^k,
$$
т.е. $a_n=\lambda_n(2)+\lambda_{n-1}(2)$.

В принципе, если вспомнить полиномы Чебышёва второго рода
$$
U_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k\binom{n-k}{k}(2x)^{n-2k}
$$
и их производящую функцию
$$
\sum_{n=0}^\infty U_n(x)z^n=\frac{1}{1-2xz+z^2},
$$
то всё легко находится:
$$
\begin{gathered}
U_n(x)=(2x)^n \lambda_n\Bigl(-\frac{1}{4x^2}\Bigr)\quad\Rightarrow\quad 
\lambda_n(x)=\Bigl(\frac{\sqrt x}{i}\Bigr)^n U_n\Bigl(\frac{i}{2\sqrt x}\Bigr),\\
\sum_{n=0}^\infty \lambda_n(x)z^n=\sum_{n=0}^\infty 
U_n\Bigl(\frac{i}{2\sqrt x}\Bigr)\Bigl(\frac{z\sqrt x}{i}\Bigr)^n
=\frac{1}{1-z-xz^2},\\
\sum_{n=0}^\infty a_n z^n
=\sum_{n=0}^\infty \bigl\{\lambda_n(2)+\lambda_{n-1}(2)\bigr\} z^n
=\frac{1+z}{1-z-2z^2}=\frac{1}{1-2z}\quad\Rightarrow\quad a_n=2^n.
\end{gathered}
$$
Мне, однако, больше нравится подход, когда заранее ничего не надо знать:
$$
\begin{gathered}
\sum_{n=0}^\infty \lambda_n(x)z^n
=\sum_{\delta=0,1}\sum_{n=0}^\infty \lambda_{2n+\delta}(x)z^{2n+\delta}
=\sum_{\delta=0,1}\sum_{n=0}^\infty z^{2n+\delta}
\sum_{k=0}^n \binom{2n+\delta-k}{k}\,x^k={}\\
{}=\sum_{\delta=0,1}\sum_{k=0}^\infty \sum_{n=k}^\infty z^{2n+\delta}\binom{2n+\delta-k}{k}\,x^k
=\sum_{\delta=0,1}\sum_{k=0}^\infty \sum_{n=0}^\infty z^{2n+2k+\delta}\binom{2n+\delta+k}{k}\,x^k={}\\
{}=\sum_{n=0}^\infty \sum_{k=0}^\infty z^{n+2k}\binom{n+k}{k}\,x^k
=\sum_{n=0}^\infty z^n\sum_{k=0}^\infty \binom{n+k}{k}(xz^2)^k={}\\
{}=\sum_{n=0}^\infty \frac{z^n}{(1-xz^2)^{n+1}}
=\frac{1}{(1-xz^2)\Bigl(1-\dfrac{z}{1-xz^2}\Bigr)}=\frac{1}{1-z-xz^2}.
\end{gathered}
$$
Теперь вычисляем $\lambda_n(x)$ через обратные корни полинома в знаменателе:
$$
\lambda_n(x)=[z^n]\frac{1}{1-z-xz^2}=[z^n]\frac{1}{(1-z_1z)(1-z_2z)}
=\frac{1}{z_1-z_2}[z^n]\Bigl\{\frac{z_1}{1-z_1z}-\frac{z_2}{1-z_2z}\Bigr\}
=\frac{z_1^{n+1}-z_2^{n+1}}{z_1-z_2}.
$$
При $x=2$ корни полинома $1-z-xz^2$ -- это $\tfrac12$ и $-1$, поэтому обратные корни -- это $z_1=2$ и $z_2=-1$. Ну и дальше всё очевидно.

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение24.01.2020, 02:50 
Модератор
Аватара пользователя


11/01/06
5660
Farest2, похоже на правду. У меня тождество 12 вылезло из этой задачки, где оно получается подстановкой $x=1$.

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение30.05.2020, 21:05 
Заслуженный участник


04/03/09
906
Что-то тождества мало поддаются народу. Попробую использовать для доказательства такой подход: придумать комбинаторную задачу, в которой ответ можно посчитать двумя способами, одним способом получится левая часть тождества, другим способом - правая.
maxal в сообщении #120593 писал(а):
$$\sum_{k=0}^{2n} {n\choose k} {4n-2k\choose 2n-k} (-3)^k = \sum_{k=0}^{\lfloor 2n/3\rfloor} {n\choose k}{n\choose 2n-3k}$$

Рассмотрим таблички из 4 строк и $n$ столбцов, в клетках которых стоят 0 либо 1, и количество нулей равно количеству единиц. Назовем столбец хорошим, если в первых трех клетках стоят одинаковые числа, либо три нуля, либо три единицы. Задача: сколько существует таких табличек, в которых все столбцы хорошие?
Решим эту задачу первым способом. Для начала маленькая подзадача: найдем, сколько существует табличек, в которых первые $k$ столбцов - нехорошие. В каждом нехорошем столбце в верхних трех элементах обязательно есть ровно 1 нолик, ниже которого расположена единичка, причем мы считаем, что после третьей строчки идет первая. Например, в столбце $(1,0,1,0)$ после нолика на втором месте идет единичка на третьем месте, а в столбце $(1,1,0,1)$ мы считаем, что после нолика на третьем месте идет единичка на первом месте. Если мы выберем положение такого нолика одним из трех способов, то это автоматически определяет, что в клетке ниже (в упомянутом ранее смысле) стоит единичка, а остальные две клетки в столбце могут быть какими угодно. Так вот, если мы в каждом из $k$ нехороших столбцов выберем положение такого нолика одним из трех способов, то во всей табличке будет зафиксировано содержимое $2k$ клеток, в которых будет $k$ ноликов и $k$ единичек. Остается в остальных $4n-2k$ клетках расположить поровну ноликов и единичек. Т.е. ответом к этой маленькой подзадаче будет $\displaystyle {3^k \cdot {4n-2k \choose 2n-k}$. А теперь вернемся к нашей основной задаче. Количество табличек только с хорошими столбцами по формуле включений и исключений равно $\displaystyle {4n \choose 2n} - 3 {n\choose 1}{4n-2 \choose 2n-1}+ 3^2 {n\choose 2}{4n-4 \choose 2n-2} -  \dots = \sum_{k=0}^{n} {n\choose k} {4n-2k\choose 2n-k} (-3)^k$. Получили левую часть тождества.
Теперь решим задачу вторым способом. Рассматривать будем только таблички с хорошими столбцами. Пусть у нас $k$ столбцов, в которых на первых трех местах стоят единички. Значит, среди первых трех строк будет $3k$ единичек и $3n-3k$ ноликов. Поскольку всего в таблице $2n$ единичек, то в нижней строчке должно быть $2n-3k$ единичек. Мы можем выбрать независимо $k$ столбцов с единицами на первых трех местах и $2n-3k$ столбцов с единицами на последнем месте. Итого, у нас получится, что количество таблиц со всеми хорошими столбцами равно $\displaystyle \sum_{k=0}^{n} {n\choose k}{n\choose 2n-3k}$. Вот и правая часть тождества.
Кстати, у этой задачи с табличками есть эквивалентная, более короткая формулировка: чему равно количество последовательностей длины $n$, элементы которой принадлежат множеству $\{-2,-1,1,2\}$, и у которой сумма элементов равна нулю.

 Профиль  
                  
 
 Re: комбинаторные тождества
Сообщение30.05.2020, 21:37 
Модератор
Аватара пользователя


11/01/06
5660
12d3 в сообщении #1466051 писал(а):
Кстати, у этой задачи с табличками есть эквивалентная, более короткая формулировка: чему равно количество последовательностей длины $n$, элементы которой принадлежат множеству $\{-2,-1,1,2\}$, и у которой сумма элементов равна нулю.

Да, тождество 1 происходит из последовательности A092765, для которой есть несколько разных методов подсчёта (и формул).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2

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



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

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


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

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