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.

I have not done combinatorics since high school, so this is an embarrassingly simple question.

We can solve the diophantine equation $x+y+z=100$ in nonnegative integers using the "bars and boxes" combinatorial method. We have $100$ dots, and we want place 2 partition markers among them, so the answer is ${ 102 \choose 2}$. Is there a way to generalize this (by a change of variable, perhaps) to equations like $x+2y+5z=100$? I know we can handle the case where we need to solve in positive integers by making the substitutions $x\rightarrow x+1$ and so forth, but I can't think of a way to apply a similar technique when the coefficients aren't $1$.

If not, is there a slick way to handle these more general equations?

share|improve this question
1  
Generating functions are reasonably slick. –  André Nicolas Mar 30 '13 at 1:16
    
@AndréNicolas: I don't know, as much as I love generating functions, I've never found a slick way of actually calculating the answer in closed form (the step after saying "the answer is the coefficent of $x^n$ in [some expression]"). Sometimes it even feels as though we're back to the original problem. Anyway most alleged answers I see on the net given using generating functions seem to leave out how to calculate the coefficient, so it seems like cheating to me. –  ShreevatsaR Mar 30 '13 at 1:49
    
They are pretty good for getting asymptotic estimates. –  André Nicolas Mar 30 '13 at 1:53
add comment

2 Answers

up vote 7 down vote accepted

You can solve this problem by using the idea of generating functions; specifically, for the example above, let $c_n$ be the number of positive integer solutions to the equation

$$x+2y+5z=n$$

Then the generating function $f(a)$ for the sequence $a_i$ is

$$f(a)=c_0+c_1a+c_2a^2+c_3a^3+...+c_na^n+...$$

We have

$$f(a)=(1+a+a^2+...+a^i+...)(1+a^2+a^4+...+a^{2j}+...)(1+a^5+a^{10}+...+a^{5k}+...)$$

The exponents $i, j, k$ correspond the values of $x, y, z$ respectively in your equation above.

However, expanding that polynomial is still quite inconvenient. As such, we can re-write the formula as follows

$$f(a)=\frac{1}{1-a}\frac{1}{1-a^2}\frac{1}{1-a^5}$$

Using partial fractions, we re-write $f(a)$ as follows

$$f(a)=\frac{-a^4-a^3+a^2+1}{5(1-a^5)}+\frac{13}{40(1-a)}+\frac{1}{8(1+a)}+\frac{1}{4(1-a)^2}+\frac{1}{10(1-a)^3}$$

$$f(a)=\frac{1}{5}(-a^4-a^3+a^2+1)(1+a^5+a^{10}+a^{15}+...)+\frac{13}{40}(1+a+a^2+a^3+...)+\frac{1}{8}(1-a+a^2-a^3+a^4-...)+\frac{1}{4}(1+2a+3a^2+4a^3+...)+\frac{1}{10}(1+3a+6a^2+10a^3+15a^4+...)$$

Therefore, $$c_{100}=\frac{1}{5}+\frac{13}{40}+\frac{1}{8}+\frac{1}{4}\times 101+\frac{1}{10}\times \binom{102}{2}=541$$

share|improve this answer
1  
By the way, as the first three coefficients are so small, the answer can be rewritten as the ceiling of $(n+1)/4+((n+2)(n+1))/20=((n+7)(n+1))/20$. –  Vincent Tjeng Mar 30 '13 at 1:55
    
+1. Very nice.${}$ –  user17762 Mar 30 '13 at 1:56
    
(+1) Nice answer. –  Mhenni Benghorbal Mar 30 '13 at 2:39
    
+1 for getting the actual coefficients at the end; this one is slick! So for general $n$, we have $c_n = \frac{1}{10}\binom{n+2}{2} + \frac{1}{4}(n+1) + \frac{13}{40} + \frac{1}{8}[1, -1]_{n\bmod 2} + \frac{1}{5}[1, 0, 1, -1, -1]_{n\bmod 5}$ where $a\bmod b$ denotes the unique $0 \le r < b$ such that $a \equiv r \pmod b$, and I made up the notation $[a_0, \dots, a_n]_{i}$ to mean $a_i$. –  ShreevatsaR Mar 30 '13 at 4:03
add comment

We can also solve it without generating functions as follows.

First, as a lemma, what is the number of nonnegative solutions to $x + 2y = n$? For any choice of $y$ such that $0 \le 2y \le n$, we have a unique solution (take $x = n - 2y$), so the number of solutions is the number of such choices, i.e. $\lfloor \frac{n}{2} \rfloor + 1$ (or, if you like, $\lceil \frac{n+1}{2} \rceil$).

Now the number of solutions to $x + 2y + 5z = n$: for each choice of $z$ such that $0 \le 5z \le n$, the number of solutions is that of $x + 2y = n - 5z$. The total number of solutions is got by adding them up.

For $n = 100$, the number $n - 5z$ takes values (enumerating the odd and even ones separately) $0, 10, \dots, 100$ and $5, 15, \dots, 95$, so the total number of solutions is $$\begin{align} &\phantom{=} \left(\left\lceil \frac{0+1}{2} \right\rceil + \left\lceil \frac{10+1}{2} \right\rceil + \dots + \left\lceil \frac{100+1}{2} \right\rceil\right) + \left(\left\lceil \frac{5+1}{2} \right\rceil + \left\lceil \frac{15+1}{2} \right\rceil + \dots + \left\lceil \frac{95+1}{2} \right\rceil \right)\\ &= \left(1 + 6 + \dots + 51\right) + \left(3 + 8 + \dots + 48\right) \\ &= 286 + 255 = 541. \end{align}$$

share|improve this answer
    
+1 nice! but why do you enumerate the answers separately? –  Vincent Tjeng Mar 30 '13 at 2:48
    
@VincentTjeng: Just because $1 + 3 + 6 + 8 + \dots + 41 + 46 + 48 + 51$ is more easily recognizable/summable when written as the sum of two disjoint arithmetic progressions. :-) (This break-up happens because $\lceil k/2 \rceil$ is either $k/2$ or $(k+1)/2$ depending on whether $k$ is even or odd.) –  ShreevatsaR Mar 30 '13 at 2:58
    
okay, I understand now! –  Vincent Tjeng Mar 30 '13 at 3:06
add comment

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.