Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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}

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

Your Answer


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.