2
$\begingroup$

How to determine the coefficient of z3q100 in

enter image description here

I stumbled upon this problem while trying to solve this type of partition problem: Find the number of integer solutions to x + y + z = 100 such that 3 ≤ x ≤ y ≤ z ≤ 60.

Thanks in advance.

  • 1
    You might want to consider shifting x,y,z by -2 so that your problem becomes finding solutions to $x+y+z = 94$, $1 \le x \le y \le z \le 58$.2011-05-15
  • 0
    @J.J.: It's better to shift by $-3$, to get $x+y+z=91$ where $0\leq x\leq y \leq z \leq 57$ :)2011-05-15
  • 0
    Do you have to solve it with generating functions? Maybe it's easier to solve this problem without them.2011-05-15
  • 0
    @Dennis Gulko: It's a matter of taste. When I'm doing unordered partitions (i.e. number of solutions to the equation $x_1 + x_2 + \dots + x_n = m$ with no further restraints) I like to have $x_j \ge 0$. However with regular (ordered) partitions I've mostly worked with the case where the smallest possible number is 1.2011-05-15

1 Answers 1

3

A possible solution to your problem:
First, count all partitions $x+y+z=91$ where $0\leq x,y,z\leq 57$. That would be the same as the number of distributions of 91 balls to 3 cells, and each cell can hold at most $57$ balls:
Number of distributions without top limitation: $\binom{91+3-1}{3-1}=\binom{93}{2}=4278$.
Number of distributions with one of the cells holding more than $57$ balls: $3\cdot \binom{91-58+3-1}{3-1}=3\cdot\binom{35}{2}=1785$.
So, number of good distributions will be $4278-1785=2493$ (since it's impossible to have two cells with more than $57$ balls).
Each such solution where all $x,y,z$ are distinct gives you a unique partition in your problem and is counted $3!=6$ times, and a solution where two are equal is counted 3 times. (There is no solustion where all 3 are equal since 91 is not divisible by 3).
It's left to find the number of solutions to $x+y+z=91$ where $x,y,z\geq 0$ and two are equal. This is exactly 3 times (choice of which two are equal out of 3) the number of solutions to $x+2y=91$, where $x,y\geq 0$ (i.e. when $y=z$). Here $x$ could be only $1,3,5,...,57$, which is $29$ options (since $90/2=45<57$, we already take into account $x,y,z\leq 57$).
Hence there are $29\cdot 3=87$ solutions where two are equal.
So, we have a total of $(2493-87)/6+29=430$ partitions.

  • 0
    Don't you have for example the triplet $(0,40,51)$ which is counted in 6 ways?2011-05-15
  • 0
    @J.J.: Thanks, I forgot about them. I edited my answer.2011-05-15
  • 1
    @Dennis Gulko: Ok, looks great so far. :) But did you forget about the upper limit of 57?2011-05-15
  • 0
    @Dennis: I think there is something more to be deducted from 736. Matlab simulation shows the answer to be 430.2011-05-15
  • 0
    @J.J.: Argh... I forgot all about it... I edited my answer :)2011-05-15
  • 0
    @Dennis: Thanks, you deserve more votes!2011-05-15