32
правки
Изменения
→Числа Лаха
Поделим обе части на <tex dpi=150>n!</tex>, а из правой части уберём слагаемые, равные нулю, {{---}} получим:
:<tex dpi=150>\binom{n+m-1}{n}=\sum_{k=1}^{min(m,k)} \binom{n-1}{n-k}\times\binom{m}{k}</tex>
Это тождество очевидно из комбинаторики, так как обе части равны числу способов выбрать из <tex dpi=150>n+m-1</tex> элементов, разделённых на два множества по <tex dpi=150>n-1</tex> и <tex dpi=150>m</tex> элементов, <tex dpi=150>n</tex> элементов. С одной стороны нельзя не признать, что это левая часть тождества по определению биномасочетания. С другой стороны нельзя не согласиться, что это правая часть тождества, в котором <tex dpi=150>k</tex> означает количество элементов, берущихся из множества размера <tex dpi=150>m</tex>.
Многочлены, стоящие в левой и правой частях тождества, оказались равны в <tex dpi=150>n+1</tex> точке и при этом имеют степень не больше <tex dpi=150>n</tex>, то есть они формально совпадают, что и требовалось доказать.
}}
