A complete guide to solving questions of the form “how many integer solutions does this sum have”?

In combinatorics, there are several different of the form "How many integer solutions does the equation $\Sigma_{1\le i\le k}X_i=n$ have?"

Some variations include:

• $X_i\in\{0, 1\}$
• $0\le X_i$
• $1\le X_i$
• $0\le X_i\le m$
• $m_1\le X_i \le m_2$
• ...

Is there a complete guide to solving these kinds of questions?

-
Generating functions can sometimes do the trick. –  Eric Naslund Feb 12 '11 at 17:24
The solution here can be mimicked for the different variations. –  user17762 Feb 12 '11 at 20:03

All of the problems you describe can be quickly solved using generating functions. The standard free reference for this is Wilf's generatingfunctionology. You can even add coefficients in front of the $X_i$.

-

Because the $X_i$ are ordered, these are integer compositions with restrictions. But by suitable conversion (bijection) one can usually count these using combinations (and binomial coefficients). For your particular examples,

• $X_i \in \{0,1\}$, these are the number of combinations of size $n$ from $k$ items or ${k \choose n}$.
• $X_i \ge 0$, this is the 'stars and bars' problem, where you're counting the number of configurations of $n$ stars and $k-1$ bars in sequence (that is $n$ items separated into $k$ ordered parts by the $k-1$ bars). E.g. for $n = 2$ and $k = 3$, the ways of doing it are: "##||" ,"#|#|","#||#","|##|","|#|#","||##". This is counted by ${n+k-1 \choose n}$ (the positions of $n$ stars in a string of length $n+k-1$ or equivalently ${n+k-1 \choose k-1}$ the position of the $k-1$ bars).
• $X_i \ge 1$, just subtract $k$ from $n$ to get the same problem (that is, if you -have- to have at least one item in each bin, just count the ways to do it as if you have 1 less item in each bin). This is ${n-1 \choose k-1}$.
• for more general restrictions on the number of items in each bin, you may need to do some inclusion-exclusion. For lower bounds $m_1$, just subtract off like in the previous problem. For upper bounds, count the number of ways when the lower bound is $m_2+1$ (again using the previous problem) and subtract from the solution when it is unbounded.

So these are strategies geared towards the specific problem given. You might see much more complex restrictions than you've given, and there you'll probably want to use a more general method like generating functions as mentioned in other answers.

-

The general answers come in Partition theory. For the first you just have $\binom{k}{n}$. For the rest there are various ways.

-
Partitions in the link you gave are unordered and they are harder to count. Since OP has $X_i$ the partitions are ordered (so $1+2+1$ is different from $2+1+1$) and are usually easier to count, even though both use generating functions. –  Aryabhata Feb 12 '11 at 18:01
@Moron: right you are. I missed that they were ordered. –  Ross Millikan Feb 12 '11 at 21:13

Answers to integer composition problems or integer partition problems can also be found in the methods and theory of Diophantine equation systems.

-