3. Комбинаторные тождества.

Рассмотрим некоторые тождества, связанные с биноминальными коэффициентами.

арифметический биномиальный комбинаторный тождество

·

· (правило симметрии)

·

·

·

·

· (свёртка Вандермонда)

· Мультисекция ряда (1 + x)ⁿ дает следующее тождество, выражающее суммы биномиальных коэффициентов с произвольным шагом s в виде замкнутой суммы из s слагаемых:

Применим последовательно формулу сложения:

получили тождество

?C_n+k^m = C_n+m^m,

C_n⁰ + C_n+1¹ + C_n+2² + … + C_n+m-1^m-1 = C_n+m^m

Применим формулу сложения иначе (пусть m ? n):

C_n+m^m+1 = C_n+m-1^m + C_n+m-1^m+1 = C_n+m-1^m + C_n+m-2^m + C_n+m-2^m+1 = C_n+m-1^m + C_n+m-2^m-1 + C_n+m-3^m + C_n+m-3^m+1 = ... = C_n+m-1^m + C_n+m-2^m-1 + ... + C_n^m

получили тождество ?C_n+k^m = C_n+m^m,

C_n^m ₊ C_n+1^m + C_n+2^m + ... + C_n+m-1^m = C_n+m^m

в частности,

C₁¹ + C₂¹ + C₃¹ + ... + C_n¹ = C_n+1²

то есть,