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

Автор темы Sergey 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
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).


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

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