0

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.

Ayman Hourieh
  • 39,603
caso
  • 103
  • 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 08 '13 at 19:46

1 Answers1

0

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}

M.H
  • 11,498
  • 3
  • 30
  • 66