1
$\begingroup$

Possible Duplicate:
An efficient method for computing the number of submultisets of size n, of a given multiset

Consider the equation

$ x_1 + x_2 + \ldots + x_m = t $

for some positive integer $t$.

We want to determine the total number of solutions $(x_1, \ldots , x_m) \in \mathbb N^m$ of this equation which satisfy the constraint $0 \leq x_1 , x_2 , \ldots , x_m \leq n$ (here $n$ is some fixed positive integer).

(If it would help you may assume that $t$ is a multiple of $n$, i.e. $t = r \cdot n$ for some positive integer $r$.)

I tried using generating functions. I think that $ \left( \sum_{i=0}^n z^i \right)^m $ is its generating function. But from this I cannot deduce a formula. If we write this formal series as $ \sum_{i} a_i z^i $ then I want to calculate the term $a_t$, in which I do not succeed.

  • 0
    See also the questions in the Linked list at 4643.2012-10-01

0 Answers 0