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.

  • 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
    @Dennis: Thanks, you deserve more votes!2011-05-15