Упростить выражение (уменьшить вычислительную сложность)

[Nimza]

Представляется ли возможным существенно уменьшить число операций для вычисления (на компьютере)

$$ f(x_{1},\ldots,x_{n}) = \sum\limits_{\sigma \in S_{n}} \frac{1}{(x_{1}^{\sigma_{1}}\ldots x_{n}^{\sigma_{n}})^\alpha } $$

Всё что мне здесь приходит в голову, так это формула Эйлера дифференцирования однородной функции, но видимо здесь никак это использовать нельзя.

[ИСН]

Ценю Ваше внимание к подробностям, но то, что Ваши зверюшки передвигаются вверх ногами и имеют хвост в виде буквы альфа - не имеет никакого значения для их разведения в неволе.

[Nimza]

А что имеет?

[ИСН]

Всё остальное. Ведь согласитесь, приятнее переопределить там немного и смотреть на
$\sum\limits_{\sigma \in S_{n}} x_{1}^{\sigma_{1}}\ldots x_{n}^{\sigma_{n}}$
Впрочем, по существу ничего хорошего в голову не приходит.

[venco]

А что такое $\sigma \in S_{n}$?

[Хорхе]

Вроде понятно что - перестановки. Ну а ежели написать $f_n(x_1,\dots,x_n) = x_1\cdots x_n\sum_{k=1}^n f_{n-1} (x_i,i\neq k)$, то операций не уменьшится?

[ИСН]

Постойте, это не какой-нибудь определитель Вандермонда вообще?

[Хорхе]

Это перманент Вандермонда. Может, чему-то и равен, кто его знает.

-- Ср окт 26, 2011 23:26:08 --

Хотя вряд ли он чему-то удобоваримому равен (а хотелось Вандермонда не с минусиками, а с плюсиками, но фигушки). Например, для единичек это $n!$.

[ИСН]

Вот чёрт. Я было подумал, что если тот через попарные разности выражается как это самое, то этот будет через суммы так же. Фига!

[Nimza]

Всем спасибо, пока что буду использовать формулу Райзера для перманента http://en.wikipedia.org/wiki/Computation_of_the_permanent_of_a_matrix. Всё-таки $n2^n$, а не факториал. Хотя наверное есть формулы, учитывающие специфику матрицы Вандермонда.

[Хорхе]

Должно быть что-то побыстрее.

Можно попробовать разложить на элементарные симметрические многочлены $s_k$ (Ньютона, не Виета -- чтобы быстрее считать). Как быстро многочлен раскладывается на многочлены Ньютона? Не знаю. (Кстати, эти довольно легко на Виета раскладываются: $\sigma_1$, $\sigma_2\sigma_1$, $\sigma_3(\sigma_1\sigma_2-\sigma_3)$, $\sigma_4(\sigma_1\sigma_2\sigma_3-\sigma_1^2\sigma_4-\sigma_3^2+\sigma_2\sigma_4)$ и так далее).