4
$\begingroup$

I'm interested in a general formula to calculate the maximum number of unique subsets from a set of distinct integers that sum to the same value.

For 2-tuples, given s > 1 distinct integers, there are maximally Floor(s / 2) subsets that can be formed whose sum are equal.

For 3-tuples, I observe the following: \begin{array}{|c|c|c|} \hline \text{s}& \text{No. of subsets} & \text{Tuple representation} \\ \hline 3 & 1 & (x_1, x_2, x_3)\\ \hline 4 & 1 & (x_1, x_2, x_3)\\ \hline 5 & 2 & (x_1, x_2, x_3), (x_3, x_4, x_5)\\ \hline 6 & 3 & (x_1, x_2, x_4), (x_2, x_3, x_5), (x_3, x_4, x_6)\\ \hline 7 & 5 & (x_1, x_2, x_3), (x_4, x_5, x_6), (x_1, x_4, x_7), (x_2, x_5, x_7), (x_3, x_6, x_7)\\ \hline 8 & 6? & (x_1, x_2, x_3), (x_4, x_5, x_6), (x_1, x_4, x_7), (x_2, x_5, x_7), (x_3, x_6, x_7), (x_1, x_6, x_8), ??\\ \hline \end{array} Then I'm already finding it difficult to calculate for s=8 or beyond. I could try to validate with some algebra, but I'm more interested in generalizing for the case of any s and any n.

Appreciate any help.

$\endgroup$
2
  • 1
    $\begingroup$ The entry for $s=6$ isn't correct: $\{1,2,3,4,5,6\}$ has the three subsets $\{1, 2, 6\}, \{1, 3, 5\}, \{2, 3, 4\}$ all summing to $9$. $\endgroup$ Commented Aug 3, 2023 at 17:14
  • $\begingroup$ Thanks for pointing that out. I have edited my post accordingly. $\endgroup$
    – ziggy41
    Commented Aug 3, 2023 at 18:34

1 Answer 1

6
$\begingroup$

This problem was answered in

Stanley, Richard, Algebraic Combinatorics: Walks, Trees, Tableaux, and More, Springer New York, NY, 2013, https://doi.org/10.1007/978-1-4614-6998-8

Given a set of positive real numbers, $S$, and a positive real number $\alpha$, define $f_k(S,\alpha)$ to be the number of $k$-element subsets of $S$ whose sum is $\alpha$.

Theorem: ($6.11$ in Stanley) Let $n,k\in \mathbb N$, such that $n\ge k$. Let $S$ be a subset of $n$ positive real numbers, and let $\alpha\in \mathbb R^+$. Then $$ f_k(S,\alpha)\le f_k(\{1,\dots,n\}, \lfloor k(n+1)/2\rfloor ) $$

That is, the greatest number of $k$-subsets with the same sum occurs when $S$ is an arithmetic progression, and when the target weight $k$ times the median of $S$ (rounded to the nearest integer).

All that remains is to determine $f_k(\{1,\dots,n\}, \lfloor k(n+1)/2\rfloor)$. In general, to compute $f_k(\{1,\dots,n\},\alpha)$, you need to enumerate sequences $1\le i_1<i_2<\dots<i_k \le n$ such that $i_1+\dots+i_k=\alpha$. Equivalently, letting $j_r=i_r-r$, we enumerate weakling increasing sequences $0\le j_1\le j_2\le \dots \le j_k\le n-k$ whose sum is $\alpha-\binom{k+1}2$. These correspond exactly to partitions of $\alpha-\binom{k+1}2$ with $k$ parts, whose parts are all at most $n-k$. It is well known that these occur as the coefficients of the $q$-binomial coeffiicents. Using this, Stanley states the following result, which completely answers your question.

Corollary: The largest possible number of $k$-subsets of an $n$-element set with the same sum is the coefficient of $q^{\lfloor k(n-k)/2\rfloor}$ in $\binom{n}{k}_q$.

For example, to fill out the last row of your table, we have $s=8$ and $k=3$, so we compute $$ \binom{8}{3}_q=\frac{(q^8-1)(q^7-1)(q^6-1)}{(q^3-1)(q^2-1)(q-1)}=\\ q^{15} + q^{14} + 2 q^{13} + 3 q^{12} + 4 q^{11} \\ + 5 q^{10} + 6 q^9 + 6 q^8 + \color{blue}6 q^7 + 6 q^6 \\ + 5 q^5 + 4 q^4 + 3 q^3 + 2 q^2 + q + 1 $$

Since the middle, largest coefficient of this polynomial is $\color{blue}6$, we conclude that the largest possible number of $3$-element sets in an $8$-element set with the same sum is $\color{blue}6$, confirming what you thought. This is attained by the set $\{1,2,3,4,5,6,7,8\}$ (or any arithmetic progression of length $8$), and the target total of $\lfloor k\cdot \frac{s+1}2\rfloor =\lfloor 3\cdot \frac{8+1}2\rfloor =13$. These subsets are $$ \{1,4,8\}, \{1,5,7\}, \{2,3,8\}, \{2,4,7\}, \{2,5,6\}, \{3,4,6\} $$

$\endgroup$
2
  • 1
    $\begingroup$ This is incredibly helpful and informative. Thank you! $\endgroup$
    – ziggy41
    Commented Aug 4, 2023 at 5:58
  • 1
    $\begingroup$ (+1) "weakling increasing" is presumably a typo for "weakly increasing" - I wondered if it's a technical term I hadn't heard of and a quick google suggests it's a surprisingly widespread typo! $\endgroup$
    – Silverfish
    Commented Aug 4, 2023 at 13:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .