Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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

4 Answers 4

up vote 8 down vote accepted

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$.

share|improve this answer

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

share|improve this answer
1  
And where would one go to learn more about this? –  Nate Eldredge Oct 7 '12 at 17:18

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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