1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I suggest you add the tag self-study to this question as there is no way to distinguish it from a class homework. $\endgroup$
    – Xi'an
    Feb 18, 2016 at 8:50
  • $\begingroup$ Use generating functions. $\endgroup$
    – whuber
    Aug 25, 2016 at 15:21

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – jcod0
    Feb 18, 2016 at 10:36

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