2014 dxdy logo

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

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




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


11/01/06
5660
Докажите, что для всяких целых неотрицательных $n$ справедливо тождество:

Тождество 1:
$$\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}$$

 Профиль  
                  
 
 
Сообщение11.06.2008, 05:41 
Модератор
Аватара пользователя


11/01/06
5660
Тождество 2:
$$\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose k} \left[ {n\choose k} { 2n+1-2k\choose n+2} + {n\choose k+1} {2n-2k\choose n+2}\right] = \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} {2k\choose k} {n+k\choose k+1} 2^{n-1-2k}$$

 Профиль  
                  
 
 
Сообщение26.12.2008, 10:53 
Модератор
Аватара пользователя


11/01/06
5660
Докажите, что для всяких целых неотрицательных $m,n$ справедливо

Тождество 3:
$${}_3F_2(-m,-n,m+n; 1, 1; 1) = \frac{m^2+n^2+mn}{(m+n)^2}\binom{m+n}{m}^2.$$

(см. тут)

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


11/01/06
5660
Докажите, что для всех натуральных $n$ справедливо

Тождество 4:
$$\sum_{k=1}^n \binom{n}{k}^2 H_k = \binom{2n}{n}(2H_n-H_{2n}),$$
где $H_m$ - гармонические числа.

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


02/11/08
1187
Правая часть тождества 3 есть в этом топике http://dxdy.ru/topic17192.html - а что такое стоит в левой части?

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


11/01/06
5660
Yu_K в сообщении #333726 писал(а):
Правая часть тождества 3 есть в этом топике topic17192.html - а что такое стоит в левой части?

Да, ноги у Тождества 3 растут из той самой задачи. В левой части тождества стоит так называемая гипергеометрическая функция.

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


07/01/10
2015
maxal в сообщении #333354 писал(а):
Тождество 4:

А можно получить небольшую подсказку? Я пробовал и пределы менять и суммирование по частям -- ничего не помогает.
P.S. Остальные тождества уже очень стары, может опубликуете решения? Интересно бы было посмотреть :D

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


11/01/06
5660
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}$$
и попробовать его скомбинировать с вышеприведённым интегралом.

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

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


07/01/10
2015

(Оффтоп)

maxal, а Вами предполагается вообще опубликовать решения, если их никто не решит? Например первые 3 тождества уже 2 года висят.

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


11/01/06
5660
caxap в сообщении #335830 писал(а):
maxal, а Вами предполагается вообще опубликовать решения, если их никто не решит? Например первые 3 тождества уже 2 года висят.

Вообще-то я с первого раза вопросы понимаю. Хотел на досуге поискать свои доказательства (доказывать заново нет времени), но раз уж вы такой нетерпеливый - то вот вам вместо доказательств подсказка: вычислите значения выражений для несколький последовательных значений $n$ и найдите по ним соответствующие последовательности в OEIS - там должна быть полезная информация.

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


11/01/06
5660
Тождество 5.
$$
\sum_{k=1}^{n} (-1)^k{n\choose k}{n+k\choose n}(H_{n+k}-H_n)=(-1)^nH_n.
$$

(источник)

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


11/01/06
5660
Тождество 6.
$$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k 2^{n-k}}.$$

(источник)

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


11/01/06
5660
Тождество 7.
$$\sum_{k=0}^{n/2} (-3)^{-k}\binom{n+k}{k}\binom{2n+1-k}{n+1+k}=3^n.$$

(источник)

 Профиль  
                  
 
 тождество для чисел Стирлинга 2-го рода
Сообщение22.03.2017, 03:38 
Модератор
Аватара пользователя


11/01/06
5660
Тождество 8. Докажите, что для всех целых (неотрицательных) $n,k$ справедливо тождество:
$$S(n,k) = \sum_{j=k}^n (-1)^{j-k}\cdot \binom{n}{j}\cdot S(j,k)\cdot k^{n-j},$$
где $S(\cdot,\cdot)$ -- числа Стирлинга 2-го рода.

По возможности дайте комбинаторное доказательство.

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


11/01/06
5660
Тождество 9.
$$\sum_{i=0}^{n}{ \sum_{j=0}^{m}{ \left(-1 \right)^{\left\lfloor\tfrac{i}{2}\right\rfloor+j}2^{n-i}\binom{n-\left\lceil \frac{i}{2} \right\rceil}{j}\binom{n-\left\lceil \frac{i}{2} \right\rceil-j}{\left\lfloor \frac{i}{2} \right\rfloor}\binom{i}{m-j}}} = \left(-1 \right)^{m} \binom{2n+1}{2m+1}.$$

(источник)

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

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



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

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


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

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