Комбинаторная формула с разбиениями числа

[Sonic86]

Если хочецца, докажите, что

$$ \binom{n + m}{n \ \ m} = \sum\limits_{\begin{array}{c}m=c_0+...+c_m, \\ c_0\leqslant ... \leqslant c_m \end{array}} \binom{n+1}{d_0 \ \dots \ d_m}, \ \ \ d_j=\#\{c_i:c_i=j\} $$

здесь $\binom{p}{q_1 ... q_s} = \dfrac{p!}{q_1!...q_s!}$ - биномиальный коэффициент.

(источник)

навеяно задачей https://leetcode.com/problems/number-of ... -same-bst/

[maxal]

Вероятно, вы имеете в виду $m=c_0 + \cdots + c_n$.

[Sonic86]

Да, надо поправить так:

$$ \binom{n + m}{n \ \ m} = \sum\limits_{\begin{array}{c}n+1=c_0+...+c_n, \\ c_0\leqslant ... \leqslant c_n \end{array}} \binom{n+1}{d_0 \ \dots \ d_m}, \ \ \ d_j=\#\{c_i:c_i=j\} $$

(пример)

Например, возьмем $n=5, m=3, n+1=6$, выпишем таблицу разложений $6=c_0+c_1+c_2+c_3+c_4+c_5+c_6$

$$ \begin{array} . \\ 3=0+0+0+0+0+3\\ 3=0+0+0+0+1+2\\ 3=0+0+0+1+1+1\\ \end{array} \leftrightarrow \ \ \begin{array}{cccc} d_0 & d_1 & d_2 & d_3\\ 5 & 0 & 0 & 1\\ 4 & 1 & 1 & 0\\ 3 & 3 & 0 & 0\\ \end{array} $$

И тогда

$$\binom{8}{5 \ 3} = \binom{6}{5 \ 1} + \binom{6}{4 \ 1 \ 1} + \binom{6}{3 \ 3} \Leftrightarrow 7\cdot 8 = 56 = 6 + 30 +20$$

[maxal]

Ваш пример показывает, что все-таки $m=c_0+\dots+c_n$, а не $n+1=c_0+\dots+c_n$.

-- Sun Jun 18, 2023 13:45:25 --

Связь с полиномами Белла здесь такая:
Положим $j_i := d_{i-1}$. Тогда

$$\begin{cases} j_1 + \dots + j_{m+1} = n + 1;\\ 1\cdot j_1 + 2\cdot j_2 + \dots + (m+1)\cdot j_{m+1} = m + n + 1.\end{cases}$$

.
Тогда правая часть данного тождества - это частное значение полиномов Белла:

$$\hat B_{m+n+1,n+1}(1,1,\dots) = \frac{(n+1)!}{(m+n+1)!} B_{m+n+1,n+1}(1!,2!,\dots) = \binom{m+n}n,$$

ч.т.д.