максимальный коэффициент в (x+x^2+x^4+x^8+...)^n

[nn910]

Sonic86 в сообщении #249678 писал(а):

Для $n=7$ максимальный коэффициент равен 28560. С помощью Maple я нашел минимальную степень, имеющую этот коэффициент - 604.
.......
Но у меня получается тогда число $7! \cdot (\frac{2}{2!}+\frac{6}{2!^2}+\frac{1}{3!}+\frac{6}{2!3!})=15960$ - гораздо меньше, чем 28560.

Вот этим Вы похоже и доказали что $a_{604}=15960$ а не 28560. Косвенные соображения : 1.увеличивая "разреженность" для 604 коэффициент не уменьшаем,и 604 можно существенно разредить.
2.По EtCetera число единиц у оптимального номера при n=7 k=n-3=4 а у 604 их 5
marple может не то чтобы врать,но искренне обманывать пользователя (замечал считая еще для n=5):выделяю мышкой полином не влезающий в экран, она чего-то в нем не поняла и подставила то что было в буфере перед этим

[Sonic86]

Не знаю... там таких степеней с таким коэффициентом много, причем у них двоичное разложение очень похоже - все-таки комп не врет, просто я чего-то не вижу...

-- Ср окт 07, 2009 16:41:17 --

Может быть кто может найти для $n=7$ такую степень, у которой коэффициент равен 28560? Мне только номер нужен и все, остальное я сам увижу.

[maxal]

Sonic86 в сообщении #249806 писал(а):

Может быть кто может найти для $n=7$ такую степень, у которой коэффициент равен 28560? Мне только номер нужен и все, остальное я сам увижу.

Минимальная степень в этом случае равна 34952.

[Sonic86]

(сообщение удалено)

-- Чт окт 08, 2009 12:32:03 --

maxal писал(а):

Минимальная степень в этом случае равна 34952

$34952=1000100010001000$
То есть все-таки наименьший номер равен $2^r+2^{2r}+...+2^{r(n-r)}$?
Тогда $r=3 < \frac{n}{2}$ и все типы решения уравнения $\sum\limits_{j=1}^7 2^{a_j} = 34952$ все же имеют следующий вид:
берем двоичное представление с 4-я цифрами и делаем 3 "удвоения". Поскольку "удвоения" друг на друга "не влияют", то мы можем их получить просто перекомбинацией строк $'1000','0200','0120','0112'$ (чтобы сделать 1-ю строку, надо 0 "удвоений", чтобы сделать 2-ю - надо 1 удвоение и т.п.), причем перекомбинации должно соответствовать ровно 3 удвоения.
Решения такие:
$34952=1000 \ 1000 \ 1000 \ 0112$
$34952=1000 \ 1000 \ 0112 \ 1000$
$34952=1000 \ 0112 \ 1000 \ 1000$
$34952=0112 \ 1000 \ 1000 \ 1000$

$34952=0200 \ 0120 \ 1000 \ 1000$
$34952=0200 \ 1000 \ 0120 \ 1000$
$34952=0200 \ 1000 \ 1000 \ 0120$
$34952=0120 \ 0200 \ 1000 \ 1000$
$34952=1000 \ 0200 \ 0120 \ 1000$
$34952=1000 \ 0200 \ 1000 \ 0120$
$34952=0120 \ 1000 \ 0200 \ 1000$
$34952=1000 \ 0120 \ 0200 \ 1000$
$34952=1000 \ 1000 \ 0200 \ 0120$
$34952=0120 \ 1000 \ 1000 \ 0200$
$34952=1000 \ 0120 \ 1000 \ 0200$
$34952=1000 \ 1000 \ 0120 \ 0200$

$34952=0200 \ 0200 \ 0200 \ 1000$
$34952=0200 \ 0200 \ 1000 \ 0200$
$34952=0200 \ 1000 \ 0200 \ 0200$
$34952=1000 \ 0200 \ 0200 \ 0200$

Всего $4+4 \cdot 3+4=20$ типов. Типы группируются в типы второго порядка - типы2, в рамках каждого типа2 группы автоморфизмов одинаковы. Типов2 всего 3, мощности группы автоморфизмов соответственно равны $\frac{7!}{2!}$, $\frac{7!}{2!^2}$, $\frac{7!}{2!^3}$. Следовательно, всего $7! (\frac{4}{2}+\frac{12}{4}+\frac{4}{8}) = 7! \cdot \frac{11}{2} = 27720 < 28560$. , хотя у меня по формуле получалось меньше, значит в формуле ошибка, так что я пойду еще пересчитаю, может чего и пойму...
(просто $\frac{28560}{7!} = \frac{17}{3}$ - знаменатель - не степень двойки, а у меня двойки в знаменателе вылазят из мощности группы автоморфизмов, и так как есть 3, значит должны быть решения, содержащие 3 одинаковых слагаемых, чего тут вообще нету...)

[EtCetera]

Прошу прощения за некоторое вынужденное отсутствие на форуме.

Sonic86

Sonic86 в сообщении #250026 писал(а):

То есть все-таки наименьший номер равен $2^r+2^{2r}+...+2^{r(n-r)}$?

Не совсем так. Правильнее
$2^{n-k}+2^{n-k+(n-k+1)}+2^{n-k+2\cdot(n-k+1)}+...+2^{n-k+(k-1)(n-k+1)}=2^{n-k}\dfrac{2^{k(n-k+1)}-1}{2^{n-k+1}-1}$,
где $k$ - число единиц в двоичной записи оптимального набора (кстати, у меня в одном из предыдущих постах также приведена неправильная формула минимальной степени).

34952 можно представить еще 4-мя способами:
$34950 = 1000\ 1000\ 1000\ 0040$
$34950 = 1000\ 1000\ 0040\ 1000$
$34950 = 1000\ 0040\ 1000\ 1000$
$34950 = 0040\ 1000\ 1000\ 1000$
что дает искомые $4\cdot \dfrac{7!}{4!}=840$ единиц, которых не хватает до 28560. Т.е. в своих рассуждениях Вы не учли строку $'0040'$.
Кстати, я со случаем $n=7$ сильно намучился, т.к. варианты $k=3$, $k=5$, $k=6$ (явно отстающие $k=1$ и $k=n$ я тогда уже не рассматривал), которые я рассчитал, не давали правильного значения максимального коэффициента, а $k=5$ вдобавок еще и очень хорошо к нему приблизился ($L_7^{(5)}=25200$, что мне показалось страшно подозрительным), так что я даже усомнился в правильности всего метода, но потом все-таки решил посчитать и для $k=4$. После этого я уже практически не сомневался и для $n=8$ с третьей попытки нашел правильное значение (до правильного $k=5$ рассмотрев $k=7$ и $k=6$). Ну а дальше за меня считала программа...

maxal

maxal в сообщении #247864 писал(а):

Вот пара статей оттуда для сравнения:
post195293.html#p195293
post151012.html#p151012
По-моему, у вас материала вполне достаточно для сравнимой по уровню и размеру статьи.

Проглядел эти статьи, там действительно все довольно подробно разжевывается. Но у этих авторов рассуждения строятся по классическому принципу: аксиомы (точнее, уже просто известные факты и ранее доказанные теоремы) - леммы - теоремы - выводы (что, в общем-то, и неудивительно). У меня же сплошь одни догадки. Например, я даже приблизительно не представляю как можно доказать утверждение о необходимой "разреженности" (т.е. о том, что листья на одной "прививке" не должны располагаться на тех же уровнях, на которых располагаются листья других "прививок", т.к. для таких конфигураций уменьшается число возможных способов представления) для степени, при которой располагается максимальный коэффициент. Хотя, разве что если вынести подобные утверждения в леммы...

maxal в сообщении #247864 писал(а):

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

Это было бы весьма неплохо, т.к. я не только не являюсь математиком-профессионалом (что, наверное, ясно по моей "терминологии"), но и любителем меня назвать довольно сложно.

maxal в сообщении #247864 писал(а):

Надо для порядка все-таки аккуратно проверить ваши выкладки.

Для начала их надо сильно формализовать (впрочем, я полагаю, что в ближайшее время этим займусь).

maxal в сообщении #247864 писал(а):

А послать обновление - это плевое дело:
http://www.research.att.com/~njas/sequences/Submit.html

Спасибо, этот момент я при первом знакомстве с сайтом как-то проглядел.

Кстати, недавно попытался построить (пока вручную, без программы) последовательность $b_k$, соответствующую разложениям $\left(\sum\limits_{i=0}^{\infty}x^{m^i}\right)^n$ при $m=3$ (в дальнейшем буду обозначать ее $b_k^{(3)}$). Вот что у меня получилось:
$k$ $b_k^{(3)}$
1 1 (это просто условность)
2 0 (логично, т.к. троичное дерево с 2-мя листьями не построишь)
3 1 (единственный вариант - троичное дерево)
4 0 (аналогично $k=2$)
5 10 (1 вариант дерева), $\binom{5}{2}$
6 0
7 217 (2 варианта), $\binom{7}{2}\binom{5}{2}+\binom{7}{1}$
8 0
9 8353 (4 варианта), $\binom{9}{2}\binom{7}{2}\binom{5}{2}+\binom{9}{1}\binom{8}{3}+\binom{9}{2}\binom{8}{1}+\binom{9}{9}$
В OEIS такой последовательности, по-видимому, нет. Этих членов в принципе достаточно для нахождения по крайней мере такого же количества членов соответствующей последовательности максимальных коэффициентов. Как я уже выше отмечал, формула для $L_n^{(k)}$ в принципе должна остаться без изменений. Итак, первые члены последовательности $M_n^{(3)}$ будут выглядеть следующим образом:
$n$ $M_n^{(3)}$
1 1
2 2
3 6
4 24 (8)*
5 120 (60, 10)
6 720 (480, 140)
7 5040 (4200, 1320, 217)
8 40320 (40320, 20160, 3472)
9 423360 (362880, 252000, 63672, 8353) (ну, наконец-то! а то $n!$ уже совсем замучил )
*В скобках записаны альтернативные варианты. В OEIS такой последовательности тоже, по-видимому, нет.

[Sonic86]

EtCetera писал(а):

Т.е. в своих рассуждениях Вы не учли строку $'0040'$.

Ура! Маразму конец! Спасибо! Надо же было так затупить ...

-- Пт окт 09, 2009 07:26:50 --

EtCetera писал(а):

Не совсем так. Правильнее $2^{n-k}+2^{n-k+(n-k+1)}+2^{n-k+2(n-k+1)}+...+2^{n-k+(k-1)(n-k+1)}=2^{n-k} \frac{2^{k(n-k+1)}-1}{2^{n-k+1}}$

Да, это я ошибся