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

share|improve this question
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$. –  J. J. May 15 '11 at 8:41
    
@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$ :) –  Dennis Gulko May 15 '11 at 9:13
    
Do you have to solve it with generating functions? Maybe it's easier to solve this problem without them. –  Dennis Gulko May 15 '11 at 9:14
    
@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. –  J. J. May 15 '11 at 9:23

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Don't you have for example the triplet $(0,40,51)$ which is counted in 6 ways? –  J. J. May 15 '11 at 10:00
    
@J.J.: Thanks, I forgot about them. I edited my answer. –  Dennis Gulko May 15 '11 at 10:06
1  
@Dennis Gulko: Ok, looks great so far. :) But did you forget about the upper limit of 57? –  J. J. May 15 '11 at 10:14
    
@Dennis: I think there is something more to be deducted from 736. Matlab simulation shows the answer to be 430. –  Bhaskar Dey May 15 '11 at 10:16
    
@J.J.: Argh... I forgot all about it... I edited my answer :) –  Dennis Gulko May 15 '11 at 10:32

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.