1

Consider that I am given a set of $n$ integers $a_1, a_2, \ldots a_n$, which can take any value in the interval $1\leq a_i\leq t$, where $t$ is a positive integer, how can I find the number of combinations so that the sum of these $n$ integers is equal to $S$.

As an example, for 4 integers bounded as $1\leq a_i\leq 4$, the number of unordered (i.e. sequence does not matter) combinations so that $S=13$ is 3, given as (4,4,4,1), (4,4,3,2), (4,3,3,3).

It can be assumed that $t$ is choosen such that there exist an assignment of $a_i$, such that $\sum_{i=1}^n a_i= S$ is always true.

mdewey
  • 16,541
  • 22
  • 30
  • 57
jcod0
  • 11
  • 1

1 Answers1

2

This is a very classical combinatorics problem beautifully treated by William Feller (1970, Theory of Probability) and since this sounds like an homework or assignment, I can only point you to the Wikipedia page on the topic to help you solve the question by yourself.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
  • Many thanks Prof Xi'an. Well, using the stars and bars approach, the number of possible solution to the problem will be $n-1\choose k-1$. But this solution assumes that permutations are allowed, so for the example I had shown in my first post, (4,4,4,1), (4,4,1,4), (4,1,4,4) and (1,4,4,4) are allowed {my question excludes this possibiltity}. Also this approach assumes that $a_i$ can take any positive integer value, whereas in my problem $a_i$ is bounded as $a_i\leq t$. – jcod0 Feb 18 '16 at 10:36