1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Exodd Oct 1 '18 at 16:10
  • $\begingroup$ see here: math.stackexchange.com/questions/2491677/… $\endgroup$ – Exodd Oct 1 '18 at 16:13
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 1 '18 at 16:18
  • $\begingroup$ I made the edit! Thanks for pointing this out. $\endgroup$ – model_checker Oct 1 '18 at 16:29
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 1 '18 at 16:46

Your Answer

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

Browse other questions tagged or ask your own question.