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.

I've been struck with a problem which deals with the distribution of two distinct objects such that p of one type and q of other type into three identical boxes.
As if it were only one object with q copies i'd have used integer partitioning, and if all objects were distinct then could use Stirling Number of second kind.
But what about this mixed case...?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Using Burnside's lemma I get $\frac16{p+2\choose2}{q+2\choose2}+\frac12\lfloor\frac{p+2}2\rfloor\lfloor\frac{q+2}2\rfloor+\frac13N$, where $N=1$ if $p$ and $q$ are both divisible by $3$, and $N=0$ otherwise.

share|improve this answer
tried on one case it's valid for that... Consider number 36 then number of ways to write it as multiple of three factors, (a,b,c).. 36 = 2*2*3*3 it will give answer 8 which is correct –  greendragons Jun 14 '13 at 22:58
What is your group action here? –  Austin Mohr Jun 14 '13 at 23:21
I wrote program to calculate the answer, tried for 1000 = 2,2,2,5,5,5 , answer is 19...1 1 1000 (1 2 500), (1 4 250), (1 5 200) (1 8 125), (1 10 100), (1 20 50), (1 25 40), (2 2 250),, (2 4 125), (2 5 100), (2 10 50), (2 20 25), (4 5 50), (4 10 25), (5 5 40), (5 8 25), (5 10 20), (10 10 10).... matches with your formula... –  greendragons Jun 14 '13 at 23:30
@user14111 Is there any more intuitive way to tackle the problem other than this Lemma.. –  greendragons Jun 14 '13 at 23:34

For the sake of completeness I am posting an answer using the Polya Enumeration Theorem. As was pointed out, the group acting on the boxes is $S_3$ with cycle index $$Z(S_3) = \frac{1}{6} a_1^3 + \frac{1}{2} a_1 a_2 + \frac{1}{3} a_3.$$ The pattern repertoire is given by $$ \frac{1}{1-X}\frac{1}{1-Y}.$$ Substituting into the cycle index it now follows that the desired value is $$ [X^p Y^q] \left( \frac{1}{6} \frac{1}{(1-X)^3}\frac{1}{(1-Y)^3} + \frac{1}{2} \frac{1}{1-X}\frac{1}{1-Y} \frac{1}{1-X^2}\frac{1}{1-Y^2} + \frac{1}{3} \frac{1}{1-X^3}\frac{1}{1-Y^3} \right).$$

Now the first term (see the formula at the end) contributes $$ \frac{1}{6} {p+2 \choose 2} {q+2 \choose 2}.$$ The second term combines the initial segment of the series for $1/(1-X^2)$ of degree at most $p$ with a term from $1/(1-X)$ and the initial segment of the series for $1/(1-Y^2)$ of degree at most $q$ with a term from $1/(1-Y)$ and hence contributes $$ \frac{1}{2} \left(\sum_{m=0}^{\lfloor p/2\rfloor} 1 \right) \left(\sum_{m=0}^{\lfloor q/2\rfloor} 1 \right) = \frac{1}{2} \lfloor (p+2)/2\rfloor \lfloor (q+2)/2\rfloor$$ and the third term contributes $1/3$ if $p$ and $q$ are both divisible by three because $1/(1-X^3)$ only contains terms of degree divisible by three and $1/(1-Y^3)$ also only contains terms of degree divisible by three.

This confirms the first answer that was posted, namely $$\frac{1}{6} {p+2 \choose 2} {q+2 \choose 2} + \frac{1}{2} \lfloor (p+2)/2\rfloor \lfloor (q+2)/2\rfloor + \frac{1}{3} [[p\equiv 0 (3); q\equiv 0 (3)]].$$

Here we have made use several times of the fact that $$[z^k] \frac{1}{(1-z)^m} = {k+m-1\choose m-1}.$$

share|improve this answer
I appreciate your effort, but i am not familiar with group theory. –  greendragons Jun 15 '13 at 0:06
Thanks. I was a bit too slow and the excellent solution using Burnside showed up first. Whether you use Burnside or Polya, I don't think you can avoid cycle indices in this problem. –  Marko Riedel Jun 15 '13 at 0:09
At first problem seemed straight forward and thought could be solved using basic approach. –  greendragons Jun 15 '13 at 0:11

Your Answer


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.