2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Комбинаторная задача
Сообщение27.08.2021, 19:14 


18/05/09
93
Многоуважаемые.
Даны полиномы $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$.
Зависимости получены, с доказательством затык.
Вопрос
Как классифицировать эту задачу, и (или) какие могут быть пути ее решения?

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение28.08.2021, 20:10 


18/05/15
288
0101 в сообщении #1529796 писал(а):
Зависимости получены

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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение29.08.2021, 15:01 


18/05/09
93
Зависимости, например, такого вида -
для $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, вроде как не противоречит.

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение29.08.2021, 17:55 


18/05/15
288
не, всё равно не догоняю .. ну, например,
$$(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$. А где у вас мономы, не содержащие степеней? Покажите хоть один, чтобы понять, плиз

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение29.08.2021, 19:46 


18/05/09
93
Спасибо за проявляемый интерес.
$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$

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение29.08.2021, 21:56 


18/05/15
288
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}$$
На первый взгляд вроде верно, или? Не, не то.. но как-то, мне кажется, надо в этом направлении думать.

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение30.08.2021, 18:37 


18/05/09
93
Для $(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$

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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение30.08.2021, 20:23 


18/05/15
288
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$.

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.08.2021, 15:45 


18/05/09
93
Если полином

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

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


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

$ C^N_k$

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group