5
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$ – Ross Millikan Mar 28 '13 at 20:27
  • $\begingroup$ 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 $\endgroup$ – Pedro Mar 28 '13 at 20:56
  • $\begingroup$ 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. $\endgroup$ – Pedro Mar 28 '13 at 21:03
  • $\begingroup$ I hate when such doubts assail me; too complex to find something made by internet, too irrelevant to appear in a book. $\endgroup$ – Pedro Mar 28 '13 at 21:16
  • $\begingroup$ 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? $\endgroup$ – Ross Millikan Mar 28 '13 at 21:34
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your right. I'm not able to find a general rule... it is not true what i first said. It depends of n and k. Unfortunately computer is down, so i have to work with pen and paper. I was playing a little with n=7 and k=5 and it depends of n/2 and k/2 the way it reises $\endgroup$ – Pedro Apr 2 '13 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.