Комбинаторная сумма произведений

[Yu_K]

Есть $M$ матрица системы векторов (столбцов) длины $N$, каждый из которых состоит из $m$ единиц и $N-m$ нулей.
Требуется найти сумму

$$\sum_{i=1}^{C(N,m)}\frac{N!}{\prod_{k=1}^{N}k^{M_{k,i}}}$$

Например при $N=4, m=2$ искомая сумма равна

$\frac{4!}{1\cdot 2}+\frac{4!}{1\cdot 3}+\frac{4!}{1\cdot 4}+\frac{4!}{2\cdot 3}+\frac{4!}{2\cdot 4}+\frac{4!}{3\cdot 4}$

${3\cdot 4}+{2\cdot 4}+{3\cdot 2}+{1\cdot 4}+{1\cdot 3}+{1\cdot 2}=35$

Как найти такую сумму, например для $N=40 ,m=28$? Есть какие нибудь стандартные подходы?

[Yu_K]

Рекурентную формулу в принципе тут сразу видно
$SumP(N,m)=SumP(N-1,m)+N\cdot SumP(N-1,m-1)$.

[venco]

Чему это равно тоже видно - числа Стирлинга первого рода. Но доказывать лень.

[Хорхе]

venco в сообщении #312992 писал(а):

Но доказывать лень.

А тут, в принципе, и нечего доказывать. Следует незамедлительно из определения (из того, где числа Стирлинга -- коэффициенты некоторых многочленов).

[Yu_K]

Есть $M$ матрица системы векторов (столбцов) длины $N$, каждый из которых состоит из $m$ единиц и $N-m$ нулей. Матрица содержит все возможные наборы в кол-ве $\binom{N}{m}$ таких векторов. Требуется найти сумму

$$\sum_{i=1}^{C(N,m)}\frac{N!}{\prod_{k=1}^{N}k^{M_{k,i}}}$$

Да это действительно коэффициент при старшей степени полинома, но что-то мало окалось найти этот коэффициент - следущие тоже надо искать. Рекурренная формула немного отличается от формулы для чисел Стирлинга.

Сам полином - есть сумма полиномов и выглядит так

$$\sum_{i=1}^{C(N,m)}{N!}{\prod_{k=1}^{N}{(\frac{x-k}{k})}^{M_{k,i}}}$$

т.е. это сумма $\binom{N}{m}$ полиномов степени $m$ . Под знаком произведения стоит $m$ сомножителей не равных 1. Для коэффициентов при младших степенях тоже видимо можно выписать рекуррентные формулы.

[maxal]

Yu_K в сообщении #313455 писал(а):

Есть $M$ матрица системы векторов (столбцов) длины $N$, каждый из которых состоит из $m$ единиц и $N-m$ нулей. Матрица содержит все возможные наборы в кол-ве $\binom{N}{m}$ таких векторов. Требуется найти сумму

$$\sum_{i=1}^{C(N,m)}\frac{N!}{\prod_{k=1}^{N}k^{M_{k,i}}}$$

Это значение в нулю (т.е. свободный член) многочлена, равного $(N-m)$-ой производной многочлена:

$$N! \prod_{i=1}^N \left( x + \frac{1}{i}\right) = \prod_{i=1}^N (1+ix) = x^N \prod_{i=1}^N (x^{-1}+i).$$

Дальше воспользуйтесь производящей функцией для чисел Стирлинга 1-го рода.

[Yu_K]

Можно без производящей функции обойтись. Рекурренные формулы получились простые и позволяют посчитать коэффициенты и сам полином.

$$P_{N,m}(x)=P_{N-1,m}(x)N+P_{N-1,m-1}(x)(x-N)$$

$$P_{N,0}(x)=N!$$

$$P_{N,N}(x)=\prod_{k=1}^{N}{(x-k)}}}}$$

Удобно в маткаде считать - там в матрице можно хранить в качестве ее элементов вектора (коэффициенты полинома). Умножение на $x$ соответсвует при этом просто сдвигу индекса на 1 у всех коэффициентов.

А что-то по поводу корней таких полиномов известно?