Комбинаторная задача на сумму элементов множества

[atlakatl]

Yadryara в сообщении #1286734 писал(а):

что за идеальные кортежи?

В данном случае это $1,2,3..., 8,9,10$. Я ожидал чего-то более хитрого. Спасибо.

[DeBill]

Для арифметической прогрессии с четным $n$: организуем $\frac{n}{2}$ равных сумм (первое плюс последнее, и т.д., равные $S$). Сложив вместе половину этих сумм, получим $s=\frac{nS}{4}$ , так что $m_{s,4}=C^{\frac{n}{4}}_{\frac{n}{2}}$ - суммы из четверок. Но можно еще сочинять ту же сумму из большего количества слагаемых - из первой половины прогрессии. Это даст еще что-то такого же типа - но поменьше...И т.д.
Однако до очевидной оценки сверху $m\leqslant C^{\frac{n}{2}}_n$ еще довольно далеко... Да и грубовата она - ибо достигается на одинаковых слагаемых (что запрещено) - так что нужна более аккуратная оценка.

-- 23.01.2018, 16:29 --

Экспоненциальный рост оценка снизу дает, да.

[B@R5uk]

Yadryara в сообщении #1286734 писал(а):

Максимум достигается в точке $s=[\dfrac{n(n+1)}4]$.

Ух ты, какая точность! А это где-нибудь доказывается? Можете предложить что-нибудь почитать по теме не слишком заумное?

[atlakatl]

Не, я опять ничего не понимаю. Речь уже только об арифметической прогрессии. А другие кортежи искали? - Которые дадут большее число дублей.

[Yadryara]

B@R5uk, наверное можно доказать, но мне лень. Прогнал свою прогу несколько раз и просто увидел, что $m_s$ симметричны:

(Пример для $n = 8; max = 14; s_{max} = 18$)

$s\;m_s$
1 1
2 1
3 2
4 2
5 3
6 4
7 5
8 6
9 7
10 8
11 9
12 10
13 11
14 12
15 13
16 13
17 13
18 14
19 13
20 13
21 13
22 12
23 11
24 10
25 9
26 8
27 7
28 6
29 5
30 4
31 3
32 2
33 2
34 1
35 1
36 1

Очевидно, что количество различных ненулевых сумм равно треугольному числу $C^2_{n+1} = \dfrac{n(n+1)}2$. Ну а максимум в центре, то бишь берётся число вдвое меньшее.

Что почитать? Сравнительно недавно, кстати, была похожая тема «Явные формулы для количества разбиений». Там ещё интереснее было. И ссылки на литературу есть.

[B@R5uk]

Yadryara, спасибо за ссылку.

Yadryara в сообщении #1286809 писал(а):

...и просто увидел, что $m_s$ симметричны:

Не совсем (не хватает ведущей единички), но если добавить нулевую сумму из нулевого числа слагаемых, то будут действительно абсолютно симметричны. Весьма забавное наблюдение. С другой стороны, если исходное множество симметрично, то и множество сумм тоже должно быть таким же.

atlakatl в сообщении #1286802 писал(а):

А другие кортежи искали? - Которые дадут большее число дублей.

Пока этот вопрос открыт. Хотелось бы конкретный пример множества, для которого это так.

[Yadryara]

B@R5uk в сообщении #1286816 писал(а):

Не совсем (не хватает ведущей единички), но если добавить нулевую сумму из нулевого числа слагаемых, то будут действительно абсолютно симметричны.

Конечно. Я просто не стал проговаривать этот шаг ввиду его тривиальности.

[grizzly]

B@R5uk
На страничке OEIS есть упоминаются статьи, в которых присутствует формула Yadryara (так, на всякий случай -- я не вникал). Что результат достигается в центре -- вполне естественно, и симметрия справа / слева центра там наблюдается, конечно.

B@R5uk в сообщении #1286816 писал(а):

Пока этот вопрос открыт. Хотелось бы конкретный пример множества, для которого это так.

Если вопрос чисто прикладной, предлагаю его закрыть. Трудно поверить, что какое-то множество даст больше.
Формул для общего члена последовательности, похоже, нет. Задача переборная, NP-полная (говорят). Upd. Глупости, рекурсивные есть, кажется.

[DeBill]

Асимптотика:
Пусть случайные величины $\xi_k$ независимы, $\xi_k$ принимает значения 0 и $k$ с равными вероятностями, $\eta_n=\xi_1+...+\xi_n$ . Применим ЦПТ в форме Ляпунова
($a_k = M\xi_k =\frac{k}{2}, b_k^2 = D\xi_k = \frac{k^2}{4}, c_k^3 = M|\xi_k-a_k|^3=\frac{k^3}{8}$ ,
$A_n =a_1+...+a_n, B_n^2 = b_1^2 +...+b_n^2, C_n^3 =c_1^3+...+c_n^3$, так что $A_n=\frac{n(n+1)}{4}, B_n^2 = \frac{n(n+1)(2n+1)}{24}, C_n^3 =\frac{n^2(n+1)^2}{32}$. Условие $\frac{C_n}{B_n} \to 0$ выполняется). Имеем: дробь $\frac{\eta_n - A_n}{B_n}$ принадлежит отрезку $[-\varepsilon,\varepsilon]$ с вероятностью $2\Phi_0(\varepsilon)$ (асимптотически). Так что с такой вероятностью $\eta_n$ попадает на отрезок длины $2\varepsilon B_n$. Так что на этом отрезке есть значения, принимаемые $\eta_n$ с вероятностью $\frac{c}{n^{\frac{3}{2}}}$. Эти значения (ну, мы думаем про $A_n$) встретятся порядка $\frac{2^n}{n^{\frac{3}{2}}}$ раз.

-- 24.01.2018, 01:25 --

Ну, на самом деле, я уверен, что коэффициент при указанном главном члене - такой же, как и в локальной теоереме Муавра-Лапласа (т.е., $\sqrt{\frac{6}{\pi}}$).

[grizzly]

DeBill в сообщении #1286951 писал(а):

Ну, на самом деле, я уверен, что коэффициент при указанном главном члене - такой же, как и в локальной теоереме Муавра-Лапласа (т.е., $\sqrt{\frac{6}{\pi}}$).

Сильно! А я только что нашёл эту асимптотику как раз с таким коэффициентом в похожем (типа, частном) случае здесь: A063865.

DeBill
Там сказано, что формулу в качестве гипотезы предложили в 2002-м и за каких-нибудь 11 лет её удалось доказать. Если всё действительно можно так просто сделать, то может это повод опубликовать простое доказательство?

B@R5uk
Нарыл в какой-то статье доказательство того, что множество первых $n$ натуральных чисел оптимально (в нашем понимании). Так что вопрос можно считать закрытым. По Вашей просьбе ссылку на статью не даю -- там всё не просто сложно, а просто очень сложно

[B@R5uk]

grizzly в сообщении #1286957 писал(а):

По Вашей просьбе ссылку на статью не даю -- там всё не просто сложно, а просто очень сложно

Ну, хотя бы для полноты раскрытия темы же можно. Вдруг кто-нибудь нагуглит этот вопрос, и у него будет и желание, и способности к ознакомлению.

[grizzly]

B@R5uk в сообщении #1286958 писал(а):

Ну, хотя бы для полноты раскрытия темы же можно.

Ну тогда вот:
Robert A. Proctor, Solution of two difficult combinatorial problems with linear algebra, American Mathematical Monthly 89, 721-734.

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

[B@R5uk]

grizzly в сообщении #1286961 писал(а):

Где найти можно посмотреть оригинал все знают, надеюсь.

На торрентах? AMM вроде довольно популярное издание. Или арксив?

[DeBill]

grizzly в сообщении #1286957 писал(а):

Если всё действительно можно так просто сделать,

Ну, от "я уверен" до "доказано" еще далеко... Но если кто сумеет довести эти прикидки до ума - я буду только рад

[grizzly]

B@R5uk
Гуглом в первой ссылке находится DOI, а потом нужно смотреть здесь.