Maximum number of n-tuples of equal sum

combinatoricsnumber theoryproblem solving

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.

Best Answer

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\} $$

Related Question