# What is the maximum number of combinations with repetitions, that the sum could be the same?

Suppose I have $n$ integers (both negative and positive) and I get all combinations of $k$ elements with repetition $((n, k)) = (n + k-1, k)$

My question is: what is the maximum number of combinations, that the sum could be the same? That is, what is the maximum number of combinations with the same amount, I can get by carefully selecting the $n$ numbers. Assuming that two combinations whose elements were the same but in a different order, are the same combination.

I've been testing with 4 numbers selected such that an attempt to obtain the maximum number of combinations with the same sum. I noticed that either combining of 3 on 3 with repetition, 2 on 2 with repetition or 5 on 5, in all cases, the maximum number of combinations with the same sum, was always 3. I have never managed to fix the 4 numbers to obtain a larger number of combinations with the same amount.

If this were a general rule, then the maximum number of combinations with repetition that sum the same for $n$ elements, is always $n-1$, regardless of the value of $k$. Is it true?

Does anyone know where there is a general proof? Or a formula?

• When you say 4 numbers selected and combining 2 on 2, what are the possibilities? I would imagine the base set could be $\{1,2,3,4\}$ and you pick a pair with repetition? You have $1+3=2+2, 1+4=3+2, 2+4=3+3$ are those the three? – Ross Millikan Mar 28 '13 at 20:27
• Hello Ross. With these numbers The maximum number with the same sum is two, for example 1+3 = 2+2 or 1+4= 3+2 or 2+4 = 3+3 – Pedro Mar 28 '13 at 20:56
• I can't find now combinig 2 on 2, the 3 I have said, I always find only two as the maximum number..I was wrong...Oh god, now I'm lost. – Pedro Mar 28 '13 at 21:03
• I hate when such doubts assail me; too complex to find something made by internet, too irrelevant to appear in a book. – Pedro Mar 28 '13 at 21:16
• So for "3 on 3" you would have to find three lists of three numbers that all have the same sum, like $1+3+4=2+2+4=2+3+3$? Would $1+2+5$ (were $5$ in the set) make it 4 on 3 or 3 on 4? – Ross Millikan Mar 28 '13 at 21:34

Taking $\{0,1,2,3,4,5,6,7\}$ and $k=4$, we have $0077,0167,0257,0347,1157,1247,2237,0266,1166,1256,$ and there are many more. Clearly the number will rise faster than $n$
Added: you are looking for the multinomial coefficient. The maximum will come when the sum is $k(n+\frac 12)$. There doesn't seem to be a simple formula.