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

[B@R5uk]

Пусть у нас имеется некоторое множество чисел, количество которых $n$. Для примера я возьму такое: $\{2, 2, 3, 3, 4, 6\}$. В этом множестве чисел мы рассматриваем все возможные суммы (включая сумму из одного слагаемого) и группируем их, если они совпадают. Всего таких сумм не более $2^n-1$. Пустая сумма не рассматривается, а суммы из двух одинаковых элементов считаются одной суммой вне зависимости от их порядка (для множества $\{2, 2, 2\}$ сумму $4$ можно получить только одним способом). Для каждого результата $s$ можно посчитать количество $m_s$ различных сумм, которыми этот результат получается. Пример для множества, приведённого выше:

$2=2$, $m_2=1$
$3=3$, $m_3=1$
$4=2+2=4$, $m_4=2$
$5=2+3$, $m_5=1$
$6=2+4=3+3=6$, $m_6=3$
$7=2+2+3=3+4$, $m_7=2$
$8=2+2+4=2+3+3=2+6$, $m_8=3$
$9=3+6$, $m_9=1$
$10=2+2+3+3=2+2+6=3+3+4=4+6$, $m_{10}=4$
$11=2+2+3+4=2+3+6$, $m_{11}=2$
$12=2+3+3+4=2+4+6=3+3+6$, $m_{12}=3$
$13=2+2+3+6$, $m_{13}=1$
$14=2+2+3+3+4=2+3+3+6=2+2+4+6$, $m_{14}=3$
$15=2+3+4+6$, $m_{15}=1$
$16=2+2+3+3+6=3+3+4+6$, $m_{16}=3$
$17=2+2+3+4+6$, $m_{17}=1$
$18=2+3+3+4+6$, $m_{18}=1$

Не уверен, что для каждой суммы $s$ перебрал все возможные комбинации слагаемых, но идея должна быть ясна. В общем, такая процедура порождает набор чисел $m_s$, среди которых, разумеется, есть максимальное. В примере выше таким числом является $m_{10}=4$.

Вот и вопрос задачи: при фиксированном размере $n$ множества исходных чисел, на сколько большим может быть максимальное из возможных $m_s$? Для какого множества оно будет получаться? В примере выше я приводил только целые числа, но брать можно любые, какие захочется. Единственно, они должны быть строго больше нуля.

Идей как решать задачу у меня нет. Можно, конечно, рассмотреть элементарные случаи.

Случай $n=1$. Тут всё просто: возможна только одна сумма из одного слагаемого, так что ответ: 1.

Случай $n=2$. В этом случае возможно две или три суммы, в зависимости от того, равны элементы множества или нет. Однако, вне зависимости ни от чего сумма двух чисел отличается от каждого из слагаемых, так что ответ в этом случае тоже 1.

Случай $n=3$. Здесь может случиться так, что сумма первых двух элементов множества равна третьему. Поэтому ответ равен 2.

Случай $n=4$. Вроде бы аналогичен предыдущему случаю, потому что добавление четвёртого числа не позволяет получить ещё одну такую же сумму, как и сумма первых двух элементов. Но моя уверенность в ответе 2 слегка колеблется.

Случай $n=5$. Ответ будет не меньше 3-х. Потому что может быть так, что $a_1+a_2=a_3+a_4=a_5$, причём $a_3\ne a_1\ne a_4$. Или же так: $a_1+a_2=a_3$, причём $a_3+a_4=a_5$, тогда $a_1+a_2+a_4=a_3+a_4=a_5$. Может кто-нибудь придумает вариант с четырьмя совпадающими суммами?

В общем, буду очень благодарен за любую помощь.

[atlakatl]

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

буду очень благодарен за любую помощь.

И Вам спасибо за интересную задачу.
Похоже, это https://oeis.org/A000009

[arseniiv]

atlakatl
Не дочитали условие. Рассматриваются не все разбиения, а только те, слагаемые которых — подмультимножество данного мультимножества.

[atlakatl]

arseniiv
Тем лучше. В OEIS не найдётся, знатоки с dxdy эту последовательность внесут.
И похоже, её действительно нет. Что удивительно. Идея довольно заметная, многим такая задача в голову бы пришла.

[arseniiv]

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

знатоки с dxdy эту последовательность внесут

Так это не одна последовательность, а семейство.

[atlakatl]

arseniiv в сообщении #1286559 писал(а):

Так это не одна последовательность, а семейство.

ТС же привёл первые 5 членов. Сами наборы предъявлять не надо. Как и число, набираемое наибольшими вариантами.
Абсолютно однозначная последовательность.

[arseniiv]

Ой, мы оба не вчитывались до конца. (И тогда вообще непонятно, как ваша последовательность должна была подойти.)

[grizzly]

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

при фиксированном размере $n$ множества исходных чисел, на сколько большим может быть максимальное из возможных $m_s$?

Лучше рассматривать обычные множества, без повторений элементов. Результаты не должны быть хуже. Например, для $n=6$ получим $m_{10}\ge 5$.

[B@R5uk]

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

Похоже, это https://oeis.org/A000009

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

Кстати, для числа разбиений целого числа на положительные слагаемые без ограничений $p(n)$ и с ограничениями $q(n)$ есть ли какая-нибудь простая рекуррентная формула или формула $n$-го члена? Лучшее, что я пока нашёл, — это через производящие функции, что мало применимо на практике.

arseniiv в сообщении #1286550 писал(а):

подмультимножество данного мультимножества

Выучил новый термин.

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

Идея довольно заметная, многим такая задача в голову бы пришла.

Лично я пришёл к этой задаче пытаясь проанализировать ресурсозатратность алгоритма в худшем случае.

arseniiv в сообщении #1286559 писал(а):

Так это не одна последовательность, а семейство.

Почему же не последовательность? Одно цело число является функцией другого целого числа.

-- 22.01.2018, 21:53 --

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

Лучше рассматривать обычные множества, без повторений элементов.

Задача имеет вполне конкретную предысторию. Если ваша новая задача позволяет оценить исходную сверху, то тогда она сгодится для начала. Вернее даже, если исключение возможности повторение элементов в мультимножестве приведёт к росту функции в частном случае, то этот результат и будет ответом на исходную задачу в общем случае.

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

Например, для $n=6$ получим $m_{10}\ge 5$.

А можно поподробнее? Как ваше упрощение позволяет сходу выписать ответ?

[arseniiv]

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

Почему же не последовательность? Одно цело число является функцией другого целого числа.

Да, я глупость сказал. В начале-то их много для каждого (мульти)множества, а потом берётся максимум, и всё собралось в одну.

[grizzly]

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

Вернее даже, если исключение возможности повторение элементов в мультимножестве приведёт к росту функции в частном случае

Думаю, да. Я очень удивлюсь, если окажется иначе.

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

Как ваше упрощение позволяет сходу выписать ответ?

Да ведь очень просто считать для множества $\{1,2,3,4,5,6\}$. Ну и в общем случае тоже думаю, что начало натурального ряда будет давать максимум. Для $n=7$ получается 8, кажется. Если действительно так, то вот эту последовательность можно попытаться проверить: A025591.

-- 22.01.2018, 21:33 --

Ха, про неё так и написано:

Цитата:

$a(n)$ is the maximal number of subsets of $\{1,2,...,n\}$ that share the same sum.

-- 22.01.2018, 21:37 --

arseniiv в сообщении #1286567 писал(а):

И тогда вообще непонятно, как ваша последовательность должна была подойти.

Как ни странно, та последовательность тесно связана с этой.

[B@R5uk]

grizzly, спасибо.

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

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

Даже если это не так, то факт экспоненциального роста накладывает определённые ограничения, которые я и хотел выяснить. Вот уж не думал, что рост будет таким быстрым.

[DeBill]

Удалено: не въехал поначалу в условие

[atlakatl]

Не могу найти сами идеальные кортежи - полюбоваться ими. Уже для $n=10$ число вариантов равно 40.

[Yadryara]

atlakatl, что за идеальные кортежи? Максимум достигается в точке $s=[\dfrac{n(n+1)}4]$. Значит, для $n=10$ это суммы $27$ и $28$.

(И вот эти $40$ вариантов суммы равной $27$:)

8 9 10
1 7 9 10
2 6 9 10
2 7 8 10
3 5 9 10
3 6 8 10
3 7 8 9
4 5 8 10
4 6 7 10
4 6 8 9
5 6 7 9
1 2 5 9 10
1 2 6 8 10
1 2 7 8 9
1 3 4 9 10
1 3 5 8 10
1 3 6 7 10
1 3 6 8 9
1 4 5 7 10
1 4 5 8 9
1 4 6 7 9
1 5 6 7 8
2 3 4 8 10
2 3 5 7 10
2 3 5 8 9
2 3 6 7 9
2 4 5 6 10
2 4 5 7 9
2 4 6 7 8
3 4 5 6 9
3 4 5 7 8
1 2 3 4 7 10
1 2 3 4 8 9
1 2 3 5 6 10
1 2 3 5 7 9
1 2 3 6 7 8
1 2 4 5 6 9
1 2 4 5 7 8
1 3 4 5 6 8
2 3 4 5 6 7