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.

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|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
add comment

1 Answer 1

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