Задача про сумму из комбинаторики

Автор темы Sergey 
ОбъявленияПоследний пост
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
ОбъявлениеПреподаватель из Тайваня выкладывает на Pornhub лекции по математике и их смотрят тысячи людей27.09.2021 00:12
26.01.2003 00:07
Sergey
Задача про сумму из комбинаторики
сумма по k от 0 до n от (С(n,k))^2 * k

C(n,k) - "цэ из n по k" - биноминальный коэффициент.

Есть ли какой-то общий подход?
27.01.2003 02:37
ally of the system
Общего метода, очевидно, нет, но...
n * C(2n-1,n) = (2n-1)! / ((n-1)!^2)

Общего метода, очевидно, нет, но есть приёмы.

C(n,k) * k = n! / k! / (n-k)! * k = n! / (k-1)! / (n-k)! =
= n * (n-1)! / (k-1)! / (n-k)! = n * C(n-1,k-1), откуда:
(C(n,k))^2 * k = n * С(n-1,k-1) * C(n,k),

откуда видно, что n выносится за сумму. Это приём #1.


Теперь приём #2, похитрее. Имеем сумму по k от 0 до n таких штук:

C(n-1,k-1) * C(n,k) = C(n-1,k-1) * C(n,n-k).

Дальше идёт словесное комбинаторное объяснение примерно
следующего содержания. Пусть у нас есть набор из n-1 предмета
и ещё другой набор из n предметов. Одно слагаемое в нашей сумме
- это число способов выбрать из первого набора k-1 предмет и из
второго набора - n-k предметов (заметим, что сумма k-1 и n-k равна
n-1 и НЕ ЗАВИСИТ от k). Теперь, если просуммировать по k от 0 до n,
то получится число способов выбрать из всех 2n-1 предметов
поднабор из n-1 предмета. Но все знают, что это
C(2n-1,n-1) = C(2n-1,n).


Надеюсь, мой ответ своевременен.
Успехов!
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти