# Maximum number of n-tuples of equal sum

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.

• 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$. Commented Aug 3, 2023 at 17:14
• Thanks for pointing that out. I have edited my post accordingly. Commented Aug 3, 2023 at 18:34

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

• This is incredibly helpful and informative. Thank you! Commented Aug 4, 2023 at 5:58
• (+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! Commented Aug 4, 2023 at 13:04