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

[nn910]

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

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

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

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

Проверьте,Ваша формула дает $K_5 \geq 360$(подставлял r=2) а уже проверено что 270. Где-то ошибка аналогичная моей так и не найденной.
Я тоже совершенно уверен что
В качестве минимального номера максимального коэффициента можно взять $2^r+2^{2r}+...+2^{r(n-r)}$.

[EtCetera]

Действительно, мое предыдущее предположение было следствием невнимательного отношения к сути задачи.
Кажется, сейчас мне удалось найти некую итеративную процедуру, с помощью которой можно получить следующее значение $M_n$ (введу новое обозначение, чтобы не путаться с $a_n$ и $K_n$, использованными выше) на основе предыдущих ($M_1...M_{n-1}$) и ряда дополнительных соображений. Такой подход, к сожалению, не претендует на полное решение (т.к. $M_n$ не получается представить в виде одной более-менее обозримой формулы) и, более того, я до сих пор не уверен, что он может давать абсолютно точные искомые максимальные коэффициенты разложения . Справедливости ради отмечу, что до того $n$, до которого я смог досчитать (а это достаточно скромное $n=8$), получаются правильные значения.
Итак, от перемножения степеней перейдем сразу к сложению показателей $2^k$. Условие задачи, т.о. представляет собой $n$-мерную бесконечную таблицу сложения, в которой предлагается найти количество тех чисел, которые встречаются в ней наиболее часто. Заметим, что "слагаемыми" в этой таблице являются числа, в двоичной записи которых присутствует только одна единица (в старшем разряде), поэтому в результате операции сложения могут получиться только числа с не более чем $n$ единицами в двоичном представлении (а точнее, среди чисел-результатов окажутся числа с 1, 2, 3, ..., $n$ единицами в двоичном представлении). Числа с меньшим, чем $n$, количеством единиц в двоичной записи, образуются в тех случаях, когда среди слагаемых попадаются несколько (групп) одинаковых чисел.
Всю эту ситуацию можно представить в виде дерева, у которого узлы первого яруса расположены на различных расстояниях от корня, а из этих узлов "произрастают" двоичные "ветви". В такой интерпретации корень - сумма, листья - слагаемые, степень $m$ слагаемого (равного $2^m$) связана с номером яруса соответствующего листа и длиной ребра, исходящего из корня и ведущего к данному листу (будем называть данную характеристику листа его уровнем; листья с одинаковым уровнем будут представлять одинаковые по величине слагаемые). См. рис.

рис. 1
Таким образом, нашу задачу можно переформулировать и свести к следующей алгоритмической процедуре:
1. выделить возможные группы деревьев с $n$ листьями и $k$ узлами первого яруса ($1\le k\le n-1$);
2. для каждой из групп найти все возможные деревья указанного выше типа (с $n$ листьями)
3. для каждого из этих деревьев найти число различных способов, которыми можно задать соответствие между листьями дерева и "осями" в $n$-мерной "таблице сложения" (с учетом того, что листья, расположенные на одном уровне, представляют равные числа, число таких способов заметно меньше $n!$), вдоль которых откладываются слагаемые;
4. для каждой из групп найти сумму всех возможных способов;
5. среди полученных сумм выбрать максимальную; это будет число $M_n$ (по видимому, это будет и наш максимальный коэффициент, хотя абсолютно точно без строгого доказательства утверждать не могу).

рис. 2
На рис. 2 приведены все группы деревьев в случае $n=3$.
Подробно разберем именно этот случай:
1. Группа 1, $k=3$.

Единственный вариант дерева этой группы имеет узлы первого яруса, расположенные на различных уровнях. Если пара узлов находится на одном уровне, то мы приходим к группе 2.
Так как все 3 листа располагаются на различных уровнях, то им соответствуют различные числа. Поэтому общее число способов соответствия листьев осям будет равно $3!=6$.
2. Группа 2, $k=2$
Здесь уже имеется 2 различных варианта деревьев. Следует обратить внимание на то, что расстояние между уровнями узлов первого яруса должно быть достаточным, чтобы "вмещать" простейшее бинарное дерево с 2-мя узлами. Иначе некоторые листья (помимо тех, что принадлежат бинарному дереву) будут располагаться на одном уровне, что сократит число способов. Впрочем, оба варианта подразумевают 3 способа (т.к. порядок расположения осей, соответствующих узлам одного уровня, не важен) и, соответственно, общее число способов также равно 6.
3. Группа 3, $k=1$
В некотором смысле данную группу можно рассматривать как экзотический подвид предыдущей. В данном случае рассматриваются результаты сложения с одной единицей в двоичном представлении. Количество способов отождествления равно 3.
Таким образом, максимальное число способов принадлежит первой и второй группе и равно 6.
Теперь посмотрим, при какой степени впервые появляется такой коэффициент. Для группы 1 это будет $2^0+2^1+2^2=7$, а для группы 2 - $2^1+2^3=10$. Отдаем предпочтение первому варианту.
Сделаю небольшое отступление. Так как из узлов первого яруса, не являющихся листьями, могут "произрастать" только двоичные деревья, то следует заранее "запастись" количеством способов, которым можно "развесить" некоторые элементы на листьях всех таких деревьев (с учетом того, что порядок элементов на одном уровне не важен).
На рис. 3 приведены все двоичные деревья с числом листьев, не превышающим 4. Обозначим нужное количество способов $b_n$ для деревьев с числом листьев $n$ и найдем это значение для $n=1...4$:
1. $n=1$
Конечно, это не двоичное дерево. Однако можно считать, что это тот случай, когда узлами первого яруса являются листья. $b_1=1$.
2. $n=2$
Оба листа расположены на одном ярусе (и, соответственно, уровне). Поэтому $b_2=1$.
3. $n=3$
$b_3=3$ (см. выше)
4. $n=4$
Здесь существует 2 типа деревьев. Для одного из них число способов равно 1, для другого - 12, поэтому $b_4=1+12=13$
Замечу, что число двоичных деревьев при $n=5$ равно 3, а число вариантов $b_5=5+10+60=75$. При $n=6$ число деревьев равно 6, а общее число способов $b_6=360+60+60+30+15+15=540$. При $n=7$ число деревьев равно 11, а число способов - $b_7=2520+420+420+420+210+210+210+105+105+35+7=4662$ (если я нигде не ошибся). Дальше считать уже сложновато, и именно этот момент является самым "узким местом" в моем решении. Вообще же последовательность $b_n$ подозрительно напоминает A000670 из OEIS, но, видимо, зря напоминает...
Приступим, наконец, к вычислениям $M_n$. Сначала выделим наиболее элементарные группы деревьев, которые встречаются при любом $n$ (кроме, возможно, самых небольших $n$). Число вариантов в каждой группе будем обозначать $L_n$.
1. Группа $k=1$
$L_n=b_n$. Данная группа сохраняет свои лидирующие позиции только при $n=1$, в дальнейшем же сильно отстает от конкуренток.
2. Группа $k=n$
$L_n=n!$. Данная группа лидирует при $n=2$ и $n=3$.
3. Группа $k=n-1$
Число деревьев в группе - $k=n-1$ (бинарное дерево с 2 листьями поочередно "прививается" на каждый из узлов первого яруса), число вариантов для каждого - $\dfrac{n!}{2!}$, число вариантов в прививке - $b_2=1$. Итог: $L_n=\dfrac{(n-1)n!}{2}$. Эта группа лидирует при $n=4$.
4. Группа $k=n-2$
Здесь возможны 2 варианта: когда на один узел первого яруса прививается бинарное дерево с 3 листьями и когда к двум узлам первого яруса "прививается" по бинарному дереву с 2-мя листьями:
$L_n^1=\binom{n-2}{1}\dfrac{n!}{3!}b_3=\dfrac{(n-2)n!}{2}$
$L_n^2=\binom{n-2}{2}\dfrac{n!}{4!}\binom{4}{2}b_2^2=\dfrac{(n-2)(n-3)n!}{8}$
$L_n=L_n^1+L_n^2=\dfrac{(n+1)(n-2)n!}{8}$
Данная группа лидирует при $n=5$ и $n=6$.
5. Группа $k=n-3$
$L_n^1=\binom{n-3}{1}\dfrac{n!}{4!}b_4=\dfrac{13(n-3)n!}{24}$ ("прививка" из одного дерева с 4-мя листьями)
$L_n^2=\binom{n-3}{1}\binom{n-4}{1}\dfrac{n!}{5!}\binom{5}{3}b_3 b_2=\dfrac{(n-3)(n-4)n!}{4}$ (2 "прививки": на одной 3, а на другой 2 листа)
$L_n^3=\binom{n-3}{3}\dfrac{n!}{6!}\binom{6}{2}\binom{4}{2}b_2^3=\dfrac{(n-3)(n-4)(n-5)n!}{48}$ (3 прививки, на каждой по 2 листа)
$L_n=L_n^1+L_n^2+L_n^3=\dfrac{(n-3)(n^2+3n-2)n!}{48}$
Эта группа занимает лидирующие позиции при $n=7$ и $n=8$.
Стоит сделать несколько замечаний:
1. В некоторых случаях все варианты для данной группы не могут реализоваться. В этом случае число способов $L_n$ для данной группы сокращается, что осложняет сравнение. Например, при $n=7$ группа $k=n-4=3$ недосчитывается одного из вариантов реализации (а именно, когда прививается 4 прививки по 2 листа на каждой).
2. Уже заметно, что, если не брать во внимание явно отстающую группу $k=1$, то $L_n$ для любой группы можно представить в виде
$L_n=\dfrac{P_{n-k}^k n!}{C_k}$, где $C_k$ - некоторый коэффициент, а $P_{n-k}^k$ - полином степени $n-k$ с целочисленными коэффициентами, вид которого зависит от группы. Из этого вида выражения можно сделать один важный вывод: при увеличении $n$ становится возможным существование групп, у которых полином $P$ будет иметь все большую степень, а поэтому такие группы будут рано или поздно "обгонять" старые группы с полиномами небольших порядков. Поэтому вопрос о существовании некоей единой формулы для $M_n$ можно поставить под определенное сомнение.
P.S. Прошу прощения за невнятные картинки (а также их количество). Если будет время, перерисую их более наглядно, а также дорисую рисунки для различных групп при различных $n$.
P.P.S. Сейчас считаю общую формулу для группы $k=n-4$. Когда досчитаю, выложу на форум.
P.P.P.S. Все мое решение пока выглядит не очень убедительно в связи с тем, что числа $b_n$ приходится считать практически вручную. Все остальные моменты достаточно легко формализуются и даже алгоритмизируются.

[nn910]

EtCetera
Желаю Вам, чтобы Ваше исследование закончилось предложением $b_n$ в OEIS. Во всяком случае ИМХО Вы уже дали независимое определение (формализовать бы его еще попроще) и установили связь с http://www.research.att.com/~njas/sequences/A007657

[EtCetera]

nn910

nn910 в сообщении #246706 писал(а):

Желаю Вам, чтобы Ваше исследование закончилось предложением $b_n$ в OEIS.

Сегодня я пересчитал значения $b_n$ при $n=6$ и $n=7$ и оказалось, что $b_n$ - это одна уже известная последовательность. Какая, сейчас объясню.
Для нахождения $n$-го члена последовательности $b_n$ необходимо произвести следующие действия:
1. Для всех $1\le i< n$ должна быть известна матрица $B_{k,l}^i$. $B^1=(0)$.
2. Находим матрицу $B^n$: для всех $1\le j\le\lfloor\frac{n}{2}\rfloor$ находим вектор $\beta^m=B_k^j + B_l^{n-j}$ для всех возможных пар $(k, l)$. В $B^n$ заносим только уникальные (вот что меня и подвело! уникальность я вчера не распознал...) вектора вида $(0 \ \beta^m)$.
3. На основе полученных данных $b_n$ можно найти по следующей формуле:

$$b_n=\sum\limits_{\forall m}\,\prod\limits_{\forall i, B_{m,i}^n\ne 0}\dbinom{n-\sum\limits_{j=1}^{i-1}B_{m,j}^n}{B_{m,i}^n}$$

Руководствуясь данными соображениями я составил программку, которая выдала следующий ряд чисел:

         n b(n)
         1 1
         2 1
         3 3
         4 13
         5 75
         6 525
         7 4347
         8 41245
         9 441675
        10 5259885
        11 68958747
        12 986533053
        13 15292855019
        14 255321427725
        15 4567457001915

До этого момента последовательность $b_n$ полностью совпадает с A007178. Более того, определение A007178 гласит следующее:

Цитата:

Number of ways to write 1 as ordered sum of n powers of 1/2, allowing repeats.

Т.е. как раз то, что я имел в виду (правда, я подразумевал все способы представления $2^{n-1}$ с помощью степеней $2^k, \,0\le k<n-1$, но это по сути то же). Более того, в статье про ту же последовательность отмечен способ нахождения $b_n$:

Цитата:

coefficient of z^2^n in (z+z^2+z^4+...+z^2^(n-1))^n

за авторством Кнута. Получается, что определенная связь между максимальными коэффициентами и этой последовательностью уже известна и несомненна (что, впрочем, и неудивительно).
Теперь перейдем к формуле для $L_n^{(k)}$, которую мне тоже удалось получить (правда, выглядит она довольно страшненько). Под этим обозначением я понимаю общее количество способов соответствия для одной группы деревьев, учитывающее все варианты деревьев (т.е. это $L_n$ из предыдущего поста). Итак, вот эта формула:

$$L_n^{(k)}=\sum\limits_{\begin{array}{c}\forall c_m,d_m,N_c\in \mathbb{N}\\ \sum\limits_{m=1}^{N_c}c_m d_m=n\\ \sum\limits_{m=1}^{N_c}c_m=k\end{array}}\left(\dfrac{n!}{(n-c_1)!}\prod\limits_{i=2}^{N_c}\left(\binom{k-\sum\limits_{j=2}^{i-1}c_j}{c_i}\left(\prod\limits_{l=0}^{c_i-1}\binom{n-\sum\limits_{j=1}^{i-1}c_j d_j-ld_i}{d_i}\right)\left(b_{d_i}\right)^{c_i}\right)\right)$$

Здесь $d_m$ - количество листьев в бинарных деревьях-"прививках" (в частности, если на какой-либо узел первого яруса не привито бинарное дерево, этот коэффициент равен 1), $c_m$ - количество "прививок" с одинаковым числом листьев (кратность "прививок"), $N_c$ - количество привитых деревьев с разным числом листьев. Сумма берется по всем наборам $c_1,c_2...c_{N_c},d_1,d_2...d_{N_c}$, которые допускаются указанными условиями.
К сожалению, данная формула не учитывает возможности нереализации некоторых вариантов деревьев в группах. Это ограничение можно (как мне кажется) обойти, если условиться, что $\binom{x}{y}=0$ при $x<y$.
Сейчас пишу программу, которая проверила бы эту формулу (т.к. сомневаюсь в некоторых моментах ее записи).
В связи с этим хочу задать вопрос maxal. Насколько я понимаю, ключевое слово more в статье OEIS, посвященной искомой последовательности, означает, что все известные ее члены представлены в самой статье (т.е. она является открытой)? Или уже известны дальнейшие члены, а информация о них есть в ссылках, приведенных в статье?
Итак, остается только выразить $M_n$ (т.е. искомый максимальный коэффициент):

$$M_n=\max\limits_{1\le k\le n}L_n^{(k)}$$

P.S. Вот общее выражение для $L_n$ группы $k=n-4$:
$L_n=(n-4)n!\left(\dfrac{5}{8}+\dfrac{13(n-5)}{48}+\dfrac{n-5}{8}+\dfrac{(n-5)(n-6)}{16}+\dfrac{(n-5)(n-6)(n-7)}{384}\right)$
Она лидирует только при $n=9$.
Upd: Поправил формулу для $L_n^{(k)}$.

[Sonic86]

nn910 писал(а):

Проверьте,Ваша формула дает $K_5 \geq 360$(подставлял r=2) а уже проверено что 270. Где-то ошибка аналогичная моей так и не найденной

Извините, я исправил.
(Пока Ваши посты не прочел, могу только сказать, что оптимальное $r^*=\alpha n$, где $\alpha = \frac{110}{512}$ примерно. В Maple сумма такая:

Maple писал(а):

(\frac{3}{2})^{n-r}-1 - \frac{1}{2^{r+1}} \binom{n-r}{r+1} hypergeom([1, -n+2r+1],[r+2],- \frac{1}{2})

)

[maxal]

EtCetera в сообщении #246992 писал(а):

В связи с этим хочу задать вопрос maxal. Насколько я понимаю, ключевое слово more в статье OEIS, посвященной искомой последовательности, означает, что все известные ее члены представлены в самой статье (т.е. она является открытой)? Или уже известны дальнейшие члены, а информация о них есть в ссылках, приведенных в статье?

Первое. Впрочем без серьезного исследования литературы я бы называть задачу "открытой" не стал. Отсутствие какой-либо информации в OEIS не значит её отсутствие вообще.

[nn910]

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

(Пока Ваши посты не прочел, могу только сказать, что оптимальное $r^*=\alpha n$, где $\alpha = \frac{110}{512}$ примерно. В Maple сумма такая:
$(\frac{3}{2})^{n-r}-1 - \frac{1}{2^{r+1}} \binom{n-r}{r+1} hypergeom([1, -n+2r+1],[r+2],- \frac{1}{2})$

Вы применили конверсию marple> latex но видимо другая версия latex .Так я Вашей формулы и не вижу( в marple у меня нет hypergeom)
В этом топике надо читать не меня,а EtCetera

[Sonic86]

А gypergeom наверное нигде нету. Просто так понятнее было.

[EtCetera]

В связи с тем, что я закончил программу для нахождения $M_n$ и имеются кое-какие результаты, дополню информацию из своего предыдущего поста.
Программой получены следующие значения последовательности $M_n$:

         n M(n)
         1 1
         2 2
         3 6
         4 36
         5 270
         6 2520
         7 28560
         8 361200
         9 5481000
        10 88565400
        11 1654052400
        12 32885455680
        13 721400359680
        14 17024709461760
        15 429108154675200
        16 11721695953968000

Вплоть до 14 члена данные значения совпадают со значениями последовательности OEIS. Последние 2 члена в OEIS просто отсутствуют. Если я, формула и программа нигде не ошибаемся (что отнюдь не исключено), это новые члены данной последовательности.
Кроме того, довольно любопытной оказывается последовательность индексов групп деревьев ($k$), которые соответствуют группам с максимальным числом способов:

         n Kmax(n)
         1 1
         2 2
         3 2
         4 3
         5 3
         6 4
         7 4
         8 5
         9 5
        10 5
        11 6
        12 6
        13 7
        14 7
        15 8
        16 8

Впрочем, приблизительно такую картину я и ожидал (т.е. "максимальные" группы будут попадаться чаще именно посередине между 1 и $n$). Аномальным в данном случае является $n=8$. При данном $n$ $L_n^{(k)}$ равны:

L:
         1 41245
         2 135982
         3 260820
         4 355320
         5 361200
         6 272160
         7 141120
         8 40320

Впрочем, и при других $n$ в "центре" значения довольно близкие. Поэтому считать, что $M_n=L_n^{\left(\lceil\frac{n+1}{2}\rceil\right)}$ (при $n\ne 8$), наверное, будет неверно...
Пока писал программу, немного подправил формулу для $L_n^{(k)}$ из предыдущего поста. Более того, оказалось, что все нереализуемые варианты деревьев заведомо отбрасываются при процедуре подготовки наборов $c_1...c_m,d_1...d_m$ по указанным условиям. Так что не нужны никакие другие искусственные "подгонки" (которые предполагались по данному поводу) числа сочетаний.
К вопросу о минимальной степени, при которой впервые появляется максимальный коэффициент. Здесь все зависит от группы деревьев. Так, в группе $k$ бинарное дерево из $n-k+1$ узлов может быть "подвешено" за любой узел первого яруса. Поэтому расстояние (в уровнях) между соседними узлами первого яруса должно быть, по меньшей мере, на единицу больше "высоты" (в уровнях) этого дерева (а она равна $n-k$). Итак, минимальная степень будет равна $\sum\limits_{i=1}^{k_{max}}2^{(n-k_{max}+1)i}=\dfrac{2^{(k_{max}+1)(n-k_{max}+1)}-1}{2^{n-k_{max}+1}-1}$ (т.к. именно узлы первого яруса являются конечными слагаемыми степени).
И, последний момент. Насколько я понимаю, формула для $L_n^{(k)}$ будет пригодна для нахождения максимальных коэффициентов во всех выражениях вида $\left(\sum\limits_{i=0}^{\infty}x^{m^i}\right)^n$ ($m=2,3,...$). Только в нее (формулу) нужно подставлять не $b_n$, а аналогичную последовательность для $m=3,4,...$. Причем, алгоритм для нахождения $b_n$ будет почти тот же, только во втором пункте надо брать сумму не 2-х, а 3-х слагаемых...
maxal
А Вам известно строгое решение этой задачи? Хотя, судя по разделу, это, наверное, глупый вопрос?
Sonic86
Кажется, Ваша формула дает расхождение при $n=7$ (и далее, соответственно).

[maxal]

EtCetera в сообщении #246992 писал(а):

$$L_n^{(k)}=\sum\limits_{\begin{array}{c}\forall c_m,d_m,N_c\in \mathbb{N}\\ \sum\limits_{m=1}^{N_c}c_m d_m=n\\ \sum\limits_{m=1}^{N_c}c_m=k\end{array}}\left(\dfrac{n!}{(n-c_1)!}\prod\limits_{i=2}^{N_c}\left(\binom{k-\sum\limits_{j=2}^{i-1}c_j}{c_i}\left(\prod\limits_{l=0}^{c_i-1}\binom{n-\sum\limits_{j=1}^{i-1}c_j d_j-ld_i}{d_i}\right)\left(b_{d_i}\right)^{c_i}\right)\right)$$

Формулу можно упростить:

$$L_n^{(k)}= \sum_{\sum_{i=1}^n i c_i = n\atop \sum_{i=1}^n c_i = k} \prod\limits_{i=1}^n \binom{k-\sum\limits_{j=1}^{i-1}c_j}{c_i}\cdot b_i^{c_i}\cdot\prod\limits_{\ell=0}^{c_i-1}\binom{n-\sum\limits_{j=1}^{i-1}c_j j-\ell i}{i}$$

Другими словами, сумма здесь берется по всем разбиениям числа $n$ размера $k$, а $c_i$ - это кратность числа $i$ в разбиении.
Пример реализации на PARI/GP:

M(n) = P=partitions(n); L=vector(n); for(z=1,#P, p=P[z]; c=vector(n); k=0; for(j=1,#p,c[p[j]]++;k++); L[k] += prod(i=1,n, binomial(k-sum(j=1,i-1,c[j]),c[i]) * prod(l=0,c[i]-1, binomial(n-sum(j=1,i-1,c[j]*j)-l*i,i)) * b[i]^c[i] ) ); vecmax(L)

Используя 21 значение последовательности A007178, моментально получаем такое же количество значений $M(n)$:

? b = [1, 1, 3, 13, 75, 525, 4347, 41245, 441675, 5259885, 68958747, 986533053, 15292855019, 255321427725, 4567457001915, 87156877087069, 1767115200924299, 37936303950503853, 859663073472084315, 20505904049009202685, 513593410566661282347];
? vector(#b,n,M(n))
%3 = [1, 2, 6, 36, 270, 2520, 28560, 361200, 5481000, 88565400, 1654052400, 32885455680, 721400359680, 17024709461760, 429108154675200, 11721695953968000, 333806974560259200, 10358856500289897600, 331148326165228091520, 11429645706428485536000, 407641141014720316704000]

-- Mon Sep 28, 2009 21:23:31 --

EtCetera в сообщении #247241 писал(а):

maxal
А Вам известно строгое решение этой задачи? Хотя, судя по разделу, это, наверное, глупый вопрос?

Честно говоря, у меня не было времени подумать над этой задачей. Но она мне показалась относительно простой и я ее поместил сюда.
И, судя по всему, я не ошибся в оценке её сложности.

-- Mon Sep 28, 2009 21:38:12 --

EtCetera
Кстати, ваше решение на первый взгляд вполне может претендовать на публикацию в журнале типа American Mathematical Monthly - там любят задачи с хитрыми, но элементарными методами решения.

[EtCetera]

maxal

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

Формулу можно упростить:

$$L_n^{(k)}= \sum_{\sum_{i=1}^n i c_i = n\atop \sum_{i=1}^n c_i = k} \prod\limits_{i=1}^n \binom{k-\sum\limits_{j=1}^{i-1}c_j}{c_i}\cdot b_i^{c_i}\cdot\prod\limits_{\ell=0}^{c_i-1}\binom{n-\sum\limits_{j=1}^{i-1}c_j j-\ell i}{i}$$

Другими словами, сумма здесь берется по всем разбиениям числа $n$ размера $k$, а $c_i$ - это кратность числа $i$ в разбиении.

Собственно говоря, в своей программе я как раз пользовался подобной формулой (т.к. проще использовать один массив кратностей $c_i$ вместо двух $c_i$ и $d_i$). Но здесь выписал вариант, который мне показался проще (по ряду причин). Только я никак не мог "закатать" $\dfrac{n!}{(n-c_1)!}$ в общее произведение. Единственное, что мне немного не нравится в Вашей формуле, это коэффициент $\binom{k}{c_1}$, который вроде бы не входит в мой вариант. Однако, я внимательно посмотрел Ваш код

M(n) = P=partitions(n); L=vector(n); for(z=1,#P, p=P[z]; c=vector(n); k=0; for(j=1,#p,c[p[j]]++;k++); L[k] += prod(i=1,n, binomial(k-sum(j=1,i-1,c[j]),c[i]) * prod(l=0,c[i]-1, binomial(n-sum(j=1,i-1,c[j]*j)-l*i,i)) * b[i]^c[i] ) ); vecmax(L)

который на 100% совпадает с Вашей формулой (если я верно разобрался в синтаксисе GP), и, раз он выдал правильную последовательность $M_n$, значит у меня в каком-то месте логическая неувязка. Никак не пойму в каком.
Кстати, мне тоже приходила в голову мысль использовать уже "готовую" последовательность $b_n$ из OEIS (т.к. именно ее моя программа почему-то рассчитывала неприлично долго; сами максимальные коэффициенты считались мгновенно), но меня задержала граница в 64 бит на целый тип (а она приблизительно проходит как раз в районе 16-18 членов).
В связи с тем, что был глубоко поражен размером Вашего кода (а он меньше моего приблизительно в 40 раз), а также поддержкой "длинной" арифметики данной системой, срочно перехожу с традиционных языков (C/C++) на PARI/GP!

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

...она мне показалась относительно простой и я ее поместил сюда.
И, судя по всему, я не ошибся в оценке её сложности.

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

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

Кстати, ваше решение на первый взгляд вполне может претендовать на публикацию в журнале типа American Mathematical Monthly - там любят задачи с хитрыми, но элементарными методами решения.

Ну, я бы не сказал, что решение такое уж хитрое. К тому же оно сильно "непричесанное" и не сказать чтобы хорошо формализованное. Хотя, с другой стороны Вы (с nn910) что-то в нем разобрали?
К тому же, у этого журнала наверняка довольно строгие требования к стилю содержания и оформления текста, которые непросто с точностью соблюсти (особенно при не слишком хорошем знании языка, как у меня). Хотя, если будет время, почему бы и не заняться этим (правда, я немного не представляю, что может быть ценного в таком решении для публикации)?
P.S. Продолжение последовательности A007657, наверное, надо отправить в OEIS (вместе с формулкой $M_n$). Только, если честно, я такими вещами никогда не занимался (строго говоря, о существовании самой OEIS я узнал всего несколько месяцев назад и, в основном, благодаря этому форуму).
P.S.S. Очень хочу заняться аналогами последовательностей $M_n$ и $b_n$ для степеней 2, 3 и т.д. (собственно, достаточно, как я уже писал, получить только аналог для $b_n$, $M_n$ же остается прежней), но пока нет времени. Когда (если) появятся результаты - сразу сообщу.

[Sonic86]



EtCetera писал(а):

Sonic86

Кажется, Ваша формула дает расхождение при $n=7$ (и далее, соответственно).

Да, действительно, я не сразу заметил.

Хотел было пересчитать, но прочел Ваше

EtCetera писал(а):

Из этого вида выражения можно сделать один важный вывод: при увеличении $n$ становится возможным существование групп, у которых полином $P(n)$ будет иметь все большую степень, а поэтому такие группы будут рано или поздно "обгонять" старые группы с полиномами небольших порядков. Поэтому вопрос о существовании некоей единой формулы для $M_n$ можно поставить под определенное сомнение.

и поэтому тем более в затруднении - я предполагал несколько очень простых групп перестановок порядка $\binom{n}{2 \ 2 \ ... \ 2 \ 1 \ 1 \ ... \ 1}$, а оказалось вон как сложно. Можно было бы еще понадеятся на какую-то хорошую асимптотическую формулу, но я не знаю ...

Хотелось бы еще знать какой-нибудь показатель, при котором коэффициент максимален.

[EtCetera]

Sonic86

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

Хотел было пересчитать, но прочел Ваше

EtCetera писал(а):

Из этого вида выражения можно сделать один важный вывод: при увеличении $n$ становится возможным существование групп, у которых полином $P(n)$ будет иметь все большую степень, а поэтому такие группы будут рано или поздно "обгонять" старые группы с полиномами небольших порядков. Поэтому вопрос о существовании некоей единой формулы для $M_n$ можно поставить под определенное сомнение.

и поэтому тем более в затруднении - я предполагал несколько очень простых групп перестановок порядка $\binom{n}{2 \ 2 \ ... \ 2 \ 1 \ 1 \ ... \ 1}$, а оказалось вон как сложно.
Можно было бы еще понадеятся на какую-то хорошую асимптотическую формулу, но я не знаю...

Строго говоря, при написании той фразы я руководствовался известными мне на тот момент соображениями. Прогноз же отчасти подтвердился, а отчасти - нет. Подтвердился в том, что при возрастании $n$ лидирующие позиции занимают группы с все большими $k$ (это достаточно очевидно); кроме того, до сих пор мне непонятно каким образом $k_{max}$ зависит от $n$ (пока очевидно лишь, что $k_{max}$ находится вблизи $\lceil\frac{n}{2}\rceil$, но при некоторых $n$ наблюдаются аномальные отклонения от этого эмпирического "закона"; можно ли их каким-то образом объяснить, на данный момент мне не известно...). Не подтвердился же он (прогноз) в том, что общую формулу для $M_n$, пригодную для расчета максимальных коэффициентов при любом $n$, все-таки удалось получить (чтобы ее увидеть, пролистайте тему до последних постов, где приведен мой вариант и более простой и логичный вариант от maxal).

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

Хотелось бы еще знать какой-нибудь показатель, при котором коэффициент максимален.

Мне тоже очень хотелось бы знать такой показатель, но - увы...
Так что не прекращайте своих поисков (мой способ решения, хотя и позволяет получить $M_n$, но вряд ли претендует на полноту и абсолютное проникновение в глубины задачи)!

[maxal]

EtCetera в сообщении #247553 писал(а):

Хотя, с другой стороны Вы (с nn910) что-то в нем разобрали?

Детально проверить не было времени, но на первый взгляд все вполне разумно.

EtCetera в сообщении #247553 писал(а):

К тому же, у этого журнала наверняка довольно строгие требования к стилю содержания и оформления текста, которые непросто с точностью соблюсти (особенно при не слишком хорошем знании языка, как у меня). Хотя, если будет время, почему бы и не заняться этим (правда, я немного не представляю, что может быть ценного в таком решении для публикации)?

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

EtCetera в сообщении #247553 писал(а):

P.S. Продолжение последовательности A007657, наверное, надо отправить в OEIS (вместе с формулкой $M_n$). Только, если честно, я такими вещами никогда не занимался (строго говоря, о существовании самой OEIS я узнал всего несколько месяцев назад и, в основном, благодаря этому форуму).

Надо для порядка все-таки аккуратно проверить ваши выкладки. А послать обновление - это плевое дело:
http://oeis.org/Submit.html

[Sonic86]

Помогите мне, я так и не смог найти ошибку Я вроде так же и решал, но текст EtCetera полностью не понял
Для $n=7$ максимальный коэффициент равен 28560. С помощью Maple я нашел минимальную степень, имеющую этот коэффициент - 604. Каждому произведению степеней $x^{2^k}$ в $f^7(x)$, равному $x^{604}$ соответствует решение уравнения $604 = \sum\limits_{\sum x_j = 7}2^jx_j$В двоичном виде $604 = 2^8+2^6+2^4+2^3+2^2=101011100$ имеет 5 единиц (причем такое представление одно), а мы ищем решения с 7-ю единицами. Я их получал из двоичного представления 604 путем "удвоений" $2^a \to 2 \cdot 2^{a-1}$, например $101011100 \to 021011100 \to 013011100$ (всего $7-5=2$ "удвоения"). У меня получилось всего 15 типов решений:
$604=01300011100$
$604=02020011100$
$604=02100003100$
$604=02100010300$
$604=02100011020$
$604=10012011100$
$604=10020003100$
$604=10020010300$
$604=10020011020$
$604=10100002020$
$604=10100002200$
$604=10100002300$
$604=10100003020$
$604=10100010220$
$604=10100011012$
И тогда если взять сумму мощностей всех групп перестановок для каждого из типа решений, то мы должны получить максимальный коэффициент. Но у меня получается тогда число $7! \cdot (\frac{2}{2!}+\frac{6}{2!^2}+\frac{1}{3!}+\frac{6}{2!3!})=15960$ - гораздо меньше, чем 28560. То есть я какое-то представление числа 604 пропустил? Можете указать, какое?