2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение21.09.2009, 21:09 
Модератор
Аватара пользователя


11/01/06
5710
Найдите максимальный коэффициент (как функцию от натурального $n$) в разложении
$$(x+x^2+x^4+x^8+...)^n = \left(\sum_{j=0}^{\infty} x^{2^j}\right)^n$$
и минимальную степень, при которой он возникает.

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение21.09.2009, 21:15 
Заслуженный участник
Аватара пользователя


18/05/06
13440
с Территории
Кажись, $n!$ при $x^{2^n-1}$

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение21.09.2009, 21:24 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение21.09.2009, 21:32 
Заслуженный участник
Аватара пользователя


18/05/06
13440
с Территории
Чёрт. Действительно. Надо было мне догадаться, что 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 --

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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение23.09.2009, 19:21 


25/05/09
231
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)$ Интересно бы было увидеть решение не комбинаторное,а какое-то такое

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 12:22 


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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 12:44 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 13:07 


25/05/09
231
ИСН в сообщении #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$не меньше.Что правда уже опровергает мое утверждение о достижении равенства :wink:

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 13:20 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 13:38 


25/05/09
231
Ссылка убедительная. Но у меня есть соображения что при больших 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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 16:43 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 17:46 


25/05/09
231
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 разрежено) -легко посчитал.
В общем,без анализа этой ошибки я не могу теоретизировать дальше,т.к. все на этом построил.
Может есть проще решения?

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 20:12 
Заслуженный участник


28/04/09
1933
Что-то мне подсказывает, что искомый максимальный коэффициент можно представить в виде $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$). Правда, в последнем пункте сильно сомневаюсь...

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение24.09.2009, 20:20 
Модератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: максимальный коэффициент в (x+x^2+x^4+x^8+...)^n
Сообщение26.09.2009, 09:32 
Заслуженный участник


08/04/08
8564
Продолжая рассуждения 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$.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу 1, 2, 3  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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