# How to count the number of n-tuples $(x_1,x_2,…,x_n)$ that give a distinct sum?

Say we have the following $$n-$$tuple $$(x_1,x_2,...,x_n)$$ such that $$1\leq x_i\leq 2n,\text{ for all }i=1,2,...,n.$$ I want to know how many tuples exist which give the same sum. So for instance if $$n=3$$: $$(1,2,1)\equiv (2,1,1)\equiv (1,1,2)$$ because they yield the same sum.

I read some answers to similar questions and found people using the stars and bars technique or Polya Enumeration Theorem (which I don't clearly understand). Furthermore, if I understand the stars bar approach, then we need to know the sum $$\sum_{i=1}^{n} x_i$$ which will be equal to the number of stars and then you could throw in the $$n-1$$ bars. Here the number of stars range from $$n$$ to $$2n^2.$$ So maybe I have to do the following sum: $$S = \sum_{m=n}^{2n^2} \binom{m-1}{n-1}.$$ Does this make sense?

• here you can use the stars/bars approach in another sense. Notice that you are looking for the number of non-decreasing sequences of numbers between $1$ and $2n$ – Exodd Oct 1 '18 at 16:10
• – Exodd Oct 1 '18 at 16:13
• In the title you talk about the sum, in the body you do not mention the sum but just talk about the number of tuples. Which is it? Please clarify. – Ross Millikan Oct 1 '18 at 16:18
• I made the edit! Thanks for pointing this out. – model_checker Oct 1 '18 at 16:29
• It sounds like your original tuple consists of $n$ distinct numbers in the range $[1,2n]$. It is not hard to determine the number of orders of tuples that have the same entries in different order. For example there are ${n \choose 3}$ ways to choose three distinct numbers out of the original set, then $3!=6$ ways to order each of these choices. Finding $(2,3,4)\equiv (3,3,3)$ is harder because we are not guaranteed that $2$ and $4$ are both there. I think you are in for a brute force count of them. – Ross Millikan Oct 1 '18 at 16:46