Комбинаторная задача

[0101]

Многоуважаемые.
Даны полиномы $P_{i}=\sum\limits_{j=0}^{N-1}a_{j}\cdot b_{(N-j+i)modN}=\sum\limits_{j=0}^{N-1}b_{j}\cdot a_{(N-j+i)modN}$, где $a_j$ и $b_j$ – элементы 2-х списков длиной $N$, $0 \leqslant i \leqslant N-1$. Нужно получить зависимость количества однотипных слагаемых (комбинаций) каждого типа , входящих в произведение произвольных $k$ полиномов $\prod\limits^{k}P_i$ от $N$. Также нужно доказать справедливость этих зависимостей для $k=4$ и всех $N \geqslant 5$.
Зависимости получены, с доказательством затык.
Вопрос
Как классифицировать эту задачу, и (или) какие могут быть пути ее решения?

[ihq.pl]

0101 в сообщении #1529796 писал(а):

Зависимости получены

А как они выглядят? - вопрос из чистого любопытства. И еще - а почему это называется полиномами? Чем-то напоминает свертку двух массивов чисел. Для меня полином просто - это линейная комбинация мономов разных степеней. В комбинаторике походу это не так.

[0101]

Зависимости, например, такого вида -
для $k=4$ количество слагаемых (мономов), не содержащих степеней равно $(N^3-12\cdot N^2+52\cdot N-82)\cdot N$, $N \geqslant 5$.
Если зависимость есть, ее можно обосновать, надо полагать.

Цитата:

Чем-то напоминает свертку двух массивов чисел

Может и свертка двух массивов чисел, определению многочлена https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%B5%D0%BD, вроде как не противоречит.

[ihq.pl]

не, всё равно не догоняю .. ну, например,

$$(a_1+...+a_k)^n = \sum_{n_1+...+n_k=n} \frac{n!}{n_1!...n_k!}a^{n_1}_1...a^{n_k}_k$$

Здесь типом я бы назвал конкретный набор чисел $n_1,...,n_k$. Соответственно, кол-во однотипных мономов равнялось бы тогда числу $\frac{n!}{n_1!...n_k!}$. Но все мономы здесь имеют одну и ту же общую степень, равную $n$. А где у вас мономы, не содержащие степеней? Покажите хоть один, чтобы понять, плиз

[0101]

Спасибо за проявляемый интерес.
$P_3\cdot P_2\cdot P_1 \cdot P_0=(a_0\cdot b_3+a_1\cdot b_2+a_2\cdot b_1+a_3\cdot b_0+a_4\cdot b_4)\cdot (a_0\cdot b_2+a_1\cdot b_1+a_2\cdot b_0+a_3\cdot b_4+a_4\cdot b_3)\cdot (a_0\cdot b_1+a_1\cdot b_0+a_2\cdot b_4+a_3\cdot b_3+a_4\cdot b_2)\cdot (a_0\cdot b_0+a_1\cdot b_4+a_2\cdot b_3+a_3\cdot b_2+a_4\cdot b_1)$
$N = 5$ .
Раскрываем скобки, получаем $5^4$ произведений или комбинаций или мономов.
Моном $a_0\cdot a_1\cdot a_2\cdot a_4\cdot b_0\cdot b_2\cdot b_3\cdot b_4$ - все элементы в 1-й степени, она не пишется, это подразумевалось без степени, элементы не повторяются. Вышеупомянутая закономерность позволяет получить количество таких мономов.
Моном $a_2 \cdot a_3\cdot a_5\cdot b_0^2\cdot b_1^2$ или $a_0\cdot a_1 \cdot a_4 \cdot a_6 \cdot b_0^3 \cdot b_1$ - со степенями, элементы повторяются.
Для Вашего варианта
$(a_1+a_2+a_3)^2=a_3^2+2 \cdot a_2 \cdot a_3+2 \cdot a_1 \cdot a_3+a_2^2+2 \cdot a_1 \cdot a_2+a_1^2$
это
$2 \cdot a_2 \cdot a_3$
$2 \cdot a_1 \cdot a_3$
$2 \cdot a_1 \cdot a_2$

[ihq.pl]

0101 в сообщении #1529923 писал(а):

Спасибо за проявляемый интерес.

.. или, другими словами, назвался груздем)) В общем и целом, думаю, ясно что имеется в виду. Давайте, так попробуем. Перепишем ваши полиномы в виде

$$P_i = \sum_{j=0}^{n-1}a_jc_{j-i},$$

где $c_{j} = b_{N-j\mod N}$. Тогда

$$\prod_{i=0}^{k-1} P_i = \sum_{k_1+...+k_n = k}\frac{k!}{k_1!...k_n!}C_{k_1...k_n}a^{k_1}_1...a^{k_n}_n $$

где

$$C_{k_1...k_n} = \prod_{i=0}^{k_1-1}c_{1-i} \cdot \prod_{i=0}^{k_2-1}c_{2-i}\cdot...\cdot\prod_{i=0}^{k_n-1}c_{n-i}$$

На первый взгляд вроде верно, или? Не, не то.. но как-то, мне кажется, надо в этом направлении думать.

[0101]

Для $(a_1 +...+a_N)^k$ количество мономомов без степеней

$k! \cdot C^N_k = (N^3-6 \cdot N^2+11 \cdot N-6) \cdot N$,

$N>k, k=4$

Можно полином

$(N^3-12\cdot N^2+52\cdot N-82)\cdot N$

выразить через факториалы и биномиальные коэффициенты и будет ли это подсказкой?

[ihq.pl]

0101 в сообщении #1530051 писал(а):

будет ли это подсказкой?

Не знаю. Смотря для чего. А зачем? Вам же нужны выражения для количества однотипных мономов. Один из способов получить их - представить произведение полиномов в виде ряда. Для $(a_1+...+a_k)^n$, например, этими выражениями будут мультиномиальные коэффициенты. А в вашем случае будет что-то другое)

Я выше неправильно написал, конечно. Правильнее так:

$$\prod_{i=0}^{k-1} P_i = \sum_{k_1+...+k_n = k}C_{k_1...k_n}a^{k_1}_1...a^{k_n}_n $$

$$C_{k_1...k_n} = \sum_{\begin{subarray}{1} 0\le i_{1}^1< ...<i_{k_1}^1< n \\ ...\\0\le i_1^n< ...< i_{k_n}^n< n\end{subarray}}\prod_{m=1}^{k_1}c_{1-i_m^1}...\prod_{m=1}^{k_n}c_{n-i_m^n}$$

Вам надо представить выражение для $C_{k_1...k_n}$ как сумму однотипных мономов. Коэффициенты перед ними и будут по идее тем, что вам нужно. Плохо представляю, если честно, как это можно сделать. Но скорее всего надо использовать периодичность чисел $c_i$.

[0101]

Если полином

$(N^3-12\cdot N^2+52\cdot N-82)\cdot N$

доказать или обосновать, то цель достигается.
Если его выразить через факториалы и биномиальные коэффициенты, или выяснить, что это нельзя делать, может что-то прояснится.
Новый аспект всплыл благодаря Вашему участию.
Очень Вам благодарен!

0101 в сообщении #1530051 писал(а):

$ C^N_k$

тут ошибка, должно быть
$C^k_N$. Запутался, 2 вида записи биномиальных коеффициентов, в одном случае k вверху, в другом внизу.