Как упростить произведение многочленов?

[Leox]

Пусть

$$ Q_n(z)=1+z+z^2+\ldots+z^{n-1}=\frac{1-z^n}{1-z}. $$

Рассмотрим произведение

$$ P_{n,k}(z)=Q_n(z) Q_n(z^2) Q_n(z^3)\cdots Q_n(z^k). $$

Нужно найти или явное выражение для многочлена $P_{n,k}(z)$, или рекурентную формулу или хотя бы сильно упростить чтобы можно было его вычислять при достаточно больших $n$ и $k.$

[maxal]

Пусть $p(n,k,m)$ - это коэффициент при $z^m$ в $P_{n,k}(z)$.
Тогда $p(n,0,m) = \delta_{0m}$ и для $k>0$

$$p(n,k,m) = \sum_{j=0}^{\min\{n-1,\lfloor m/k\rfloor\}} p(n,k-1,m-jk).$$

Добавлено спустя 12 минут 38 секунд:

Что же касается самого многочлена $P_{n,k}(z)$, то его можно записать в виде отношения q-символов Похгаммера:

$$P_{n,k}(z) = \lim_{a\to 1} \frac{(a;z^n)_{k+1}}{(a;z)_{k+1}}$$

[Leox]

maxal писал(а):

Пусть $p(n,k,m)$ - это коэффициент при $z^m$ в $P_{n,k}(z)$.
Тогда $p(n,0,m) = \delta_{0m}$ и для $k>0$

$$p(n,k,m) = \sum_{j=0}^{\min\{n-1,\lfloor m/k\rfloor\}} p(n,k-1,m-jk).$$

Добавлено спустя 12 минут 38 секунд:

Что же касается самого многочлена $P_{n,k}(z)$, то его можно записать в виде отношения q-символов Похгаммера:

$$P_{n,k}(z) = \lim_{a\to 1} \frac{(a;z^n)_{k+1}}{(a;z)_{k+1}}$$

Спасибо, попробую повозиться с рекурентной формулой, может удастся сделать алгоритм нахождения коеффициентов который будет работать быстрее чем через умножение многочленов

[Dandan]

А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?

[Профессор Снэйп]

Dandan писал(а):

А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?

Кстати, тоже об этом думал. Там корни довольно легко находятся.

Но при больших $n$ и $k$ вычисления будут идти чересчур долго. Явно не быстрее, чем через простое перемножение многочленов.

Мне вот, кстати, интересно, что автору в конечном счёте требуется. Выписывать сам многочлен $P_{n,k}$ или быстро находить его значения при заданных значениях переменной.

[Leox]

Профессор Снэйп писал(а):

Мне вот, кстати, интересно, что автору в конечном счёте требуется. Выписывать сам многочлен $P_{n,k}$ или быстро находить его значения при заданных значениях переменной.

Автору нужно совсем другое. Пусть имеется многочлен

$$ P_{n,k}(z)=\sum a_i z^i. $$

Требуется как-то эфективно вычислить "подмногочлен"

$$ \sum a_{ni} z^{ni}. $$

Один из способов есть - нужно найти

$$ \frac{1}{n}\sum_i P_{n,k}(z\,\zeta^i), $$

$\zeta$ -- первообразный корень степени $n.$

Но при больших $n$ $(n>30)$ это уже не так просто-много умножений, поэтому надеюсь, что можно найти явную формулу для коэфициентов$a_{ni}.$

Добавлено спустя 5 минут 4 секунды:

Dandan писал(а):

А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?

нужно подумать