2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторная сумма произведений
Сообщение24.04.2010, 07:03 
Есть $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$? Есть какие нибудь стандартные подходы?

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение25.04.2010, 04:39 
Рекурентную формулу в принципе тут сразу видно
$SumP(N,m)=SumP(N-1,m)+N\cdot SumP(N-1,m-1)$.

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение25.04.2010, 05:00 
Чему это равно тоже видно - числа Стирлинга первого рода. Но доказывать лень.

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение25.04.2010, 23:35 
Аватара пользователя
venco в сообщении #312992 писал(а):
Но доказывать лень.

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

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение26.04.2010, 04:38 
Есть $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. Для коэффициентов при младших степенях тоже видимо можно выписать рекуррентные формулы.

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение27.04.2010, 21:16 
Аватара пользователя
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-го рода.

 
 
 
 Re: Комбинаторная сумма произведений
Сообщение07.05.2010, 13:16 
Можно без производящей функции обойтись. Рекурренные формулы получились простые и позволяют посчитать коэффициенты и сам полином.
$$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 у всех коэффициентов.

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group