# Distributing two distinct objects to identical boxes

Hiii,
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.
Thnx!

-

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.

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

-
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