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

[maxal]

Найдите максимальный коэффициент (как функцию от натурального $n$) в разложении

$$(x+x^2+x^4+x^8+...)^n = \left(\sum_{j=0}^{\infty} x^{2^j}\right)^n$$

и минимальную степень, при которой он возникает.

[ИСН]

Кажись, $n!$ при $x^{2^n-1}$

[maxal]

ИСН
Нет. Для $n\geq 4$ существует больший коэффициент.

[ИСН]

Чёрт. Действительно. Надо было мне догадаться, что maxal так просто не спросит. Но это казалось так естественно. Чёрт!

-- Пн, 2009-09-21, 23:05 --

Ладно, вторая попытка: при $n\ge 4$ максимум реализуют такие показатели, у которых в двоичном представлении $n-1$ единиц, идущих вразбивку (т.е. не подряд), наименьший же из таковых суть $2^{2n-1}-2\over 3$, а коэффициент при оном - $n!(n-1)\over 2$

-- Пн, 2009-09-21, 23:47 --

А нет, там потом появляются ещё больше. Вот ведь!..

[nn910]

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

Найдите максимальный коэффициент (как функцию от натурального $n$) в разложении

$$(x+x^2+x^4+x^8+...)^n = \left(\sum_{j=0}^{\infty} x^{2^j}\right)^n$$

и минимальную степень, при которой он возникает.

Если

$$f^n(x)=(x+x^2+x^4+x^8+...)^n = \left(\sum_{j=0}^{\infty} x^{2^j}\right)^n=\sum_{m=0}^{\infty} a_m x^{m}$$

то имеются формулы $a_m x^m=\dfrac{1}{2\pi}\int_0^{2\pi}{e^{-im\phi} f^n (xe^{i\phi})d\phi$
$f(x)=x+f(x^2)$ Интересно бы было увидеть решение не комбинаторное,а какое-то такое

[nn910]

Похоже, предпоследнее мнение ИСН было верным и $a_m=n! \dfrac {n-1}{2}$ при n начиная с 3, при n>3 достигается на всех m, у которых в двоичном разложении n-1 единиц но никакие 2 из них не подряд. При n=3 достигается без требования "не подряд", при n=2 максимум=2
Но почти все комбинаторные доказательства либо нестроги либо громоздки, поэтому в обоих случаях труднопроверяемы. Просто скажите - я угадал?

[ИСН]

Вы (мы) угадали формулу для некоторого подмножества, но это не максимум. Это вроде бы даёт максимум только для $n=4$. Дальше возникают числа, у которых больше. К примеру, при $n=5$ есть 292 - это $n-2$ единицы с промежутками в 2 нуля. И так далее. Как обобщить, непонятно.

[nn910]

ИСН в сообщении #246139 писал(а):

Вы (мы) угадали формулу для некоторого подмножества, но это не максимум. Это вроде бы даёт максимум только для $n=4$. Дальше возникают числа, у которых больше. К примеру, при $n=5$ есть 292 - это $n-2$ единицы с промежутками в 2 нуля. И так далее. Как обобщить, непонятно.

Да вот считаю:n=5 m=292=$2^2+2^5+2^8$ $a_m=240$
m=170=$2+2^3+2^5+2^7$ $a_m=240$не меньше.Что правда уже опровергает мое утверждение о достижении равенства

[ИСН]

У меня вместо одного из этих 240 получалось 270.
Также см.:
http://www.research.att.com/~njas/sequences/A007657

[nn910]

Ссылка убедительная. Но у меня есть соображения что при больших n число единиц у m не меньше n-2, еще проверю и доложу.

-- Чт сен 24, 2009 16:00:49 --

Не проверите ли меня в моей терминологии,не всё, конечно, а только место которое противоречит 270ти.

Для всякого n и m c числом единиц от n до (n-2) достаточно разреженных(пусть хоть по n нулей справа от каждой единицы)назовем Формулой $m=\sum_{i=1}^{n}{2^{k_i}} ,k_i$неубывающая. Тогда число вариантов удовлетворить данную формулу зависит только от числа совпадений в ней соседних слагаемых:$n!$при отсутствии совпадений;
$\dfrac{n!}{2}$при одном двойном совпадении;
$\dfrac{n!}{4}$при двух двойных (большее количество или кратность совпадений при таком числе единиц невозможна)Для интересующего случая (n-2) единиц получаем:
-формул с одним совпадением(тогда следующее k за совпадающими больше на 1)$C^1_{n-2}$
-формул с двумя совпадениями $C^2_{n-2}$
Отсюда $a_m=\dfrac{n!}{2}C^1_{n-2}+\dfrac{n!}{4}C^2_{n-2}=n! \dfrac{(n+3)(n-2)}{8}=360$ а не 270

[maxal]

nn910
Почему вас интересуют совпадения только соседних слагаемых? В рассматриваемых представлениях $k_i$ не обязаны быть упорядочены.

[nn910]

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

nn910
Почему вас интересуют совпадения только соседних слагаемых? В рассматриваемых представлениях $k_i$ не обязаны быть упорядочены.

Я уже проверил marploй n=4 $36x^{42}$ и n=5 $270x^{292}$ и вижу что OEIS права а я нет.
Однако на Ваш вопрос я могу ответить: и те и другие интересуют. У меня простой случай n=5 m=292 Число упорядочений хорошо считается $n!$; $n!/2$ ;$n!/4$ в зависимости только от вида набора, а не от самого набора$k_i$Видов наборов для этих m и n только 2. Сколько наборов каждого вида получается из "разреженного"m (а 292 разрежено) -легко посчитал.
В общем,без анализа этой ошибки я не могу теоретизировать дальше,т.к. все на этом построил.
Может есть проще решения?

[EtCetera]

Что-то мне подсказывает, что искомый максимальный коэффициент можно представить в виде $n!a_n$, где $a_n$ - число уникальных двоичных деревьев с $n$ листьями (т.е. что-то вроде "огрызка" чисел Каталана). $a_n$ можно представить как член рекуррентной последовательности
$a_1=1$
$a_2=1$
$a_n=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}a_i a_{n-i}$
(первые члены 1, 1, 1, 2, 3, 6, 11...)
Соответственно последовательность максимальных коэффициентов выглядит следующим образом: 1, 2, 6, 48, 360, 4320, 55440...
Данные коэффициенты появляются при минимальной степени $x^{2^{n-2}+2^{\lfloor\frac{n-1}{2}\rfloor}}$ (для $n\ge 2$). Правда, в последнем пункте сильно сомневаюсь...

[maxal]

EtCetera
Увы, но нет. Сравните свои численные значения с настоящими: A007657

-- Thu Sep 24, 2009 12:22:14 --

Более того, значение максимального коэффициента уже для $n=4$ не делится на $n!$.

[Sonic86]

Продолжая рассуждения nn910 и ИСН нашел такое

$$K_n = n! \max\limits_{r=0..n-1} \{ \sum\limits_{q=1}^r \frac{1}{2^q} \binom{n-r}{q}\}$$

Хотя точно не знаю. Не совсем уверен в сумме и в верхнем ее пределе при $r> \frac{n}{2}$, но мне кажется это маловероятным.
В качестве номера максимального коэффициента можно взять $2^r+2^{2r}+...+2^{r(n-r)}$.
И еще мне показалось что $K_n$ растет не медленнее чем $n! a^n$.

(сообщение исправлено)