# Number of integer solutions of an equation

How many integer solutions exist for the following equation with the given constraint:

Equation: $X_1 + X_2 + X_3 + X_4 = N$

Constraint: $1 \le X_1 \lt X_2 \lt X_3 \lt X_4 \le N$

I went as far as the number of integer solutions without the constraint which is $C( 4+N-1 , N-1 )$. I thought about applying the inclusion-exclusion theorem but I couldn't go any further with that.

-
Note that the constraint $\leq N$ isn't necessary as it is implied by $1 \geq$. You should use Burnside's Lemma (which will be how you want your PIE to work), or generating functions. –  Calvin Lin Feb 8 '13 at 19:46

## 1 Answer

hint: let $$x_1=y_1$$$$x_2=y_1+y_2$$$$x_3=y_1+y_2+y_3$$$$x_4=y_1+y_2+y_3+y_4$$ then $x_1 + x_2+ x_3 + x_44 = N$ equal to $4y_1+3y_2+2y_3+y_4=N$after that$$y'_1=4y_1$$$$y'_2=3y_2$$$$y'_3=2y_3$$$$y'_4=y_4$$ then compute generate function $f(x)=(\sum_{i=1}^{N}x^i)+(\sum_{i=1}^{2i\leq N}x^{2i})+((\sum_{i=1}^{3i\leq N}x^{3i})+((\sum_{i=1}^{4i\leq N}x^{4i})$ coefficient $x^N$ is answer of question (its necessary to know :$y'_4\in${1,2,...,N} ,$y'_3\in${2k ,$k\in${1,2,...,N} ,$y'_2\in${3k,$k\in${1,2,...,N} $y'_1\in${4k ,$k\in${1,2,...,N}

-
so now the equation is 4*Y1+3*Y2+2*Y3+1*Y4=N, but how do I generate function f(x) from it? –  caso Feb 8 '13 at 20:08
got it, thanks. –  caso Feb 8 '13 at 20:11
@caso: your welcome –  Maisam Hedyelloo Feb 8 '13 at 20:16