Two People, Three Objects

Date: 07/14/2001 at 03:02:14
From: Nupur Srivastava
Subject: Combination 

Find the number of ways in which 2n objects of type A, 2n objects of 
type B, and 2n objects of type C can be divided between two persons, 
giving 3n objects to each.

I started solving this problem thinking that we can select some or all 
objects in 2n+1 ways, but I got stuck at the point that each selection 
from type again yields a variable case for selection from type B - so 
how to calculate the cases where selection for the second case depends 
on the selection in the first case?

Thanking you,
Nupur Srivastava

Date: 07/14/2001 at 07:49:38
From: Doctor Anthony
Subject: Re: Combination 

If we select 3n objects for one person we automatically select the 
other 3n objects for the second person.

We can find the number of ways of selecting 3n objects from 6n objects 
of the given colours by finding the coefficient of x^(3n) in the 
expansion of the the generating function

  [1 + x + x^2 + x^3 + .... + x^(2n)]^3

  [1 - x^(2n+1)]^3     1 - 3.x^(2n+1) + 3.x^(4n+2) + x^(6n+3)
  ----------------  = ---------------------------------------
     (1-x)^3                     (1-x)^3

Since we are only interested in powers of x up to 3n we can ignore the 
last two terms of the numerator.

(1 - 3.x^(2n+1)).[1 + C(3,1)x + C(4,2)x^2 + ...+ C(n+1,n-1)x^(n-1)
                    + C(3n+2,3n)x^(3n) + ...]

and picking out the terms in x^(3n) we have

     C(3n+2,2) - 3.C(n+1,2)

     (3n+2)(3n+1) - 3(n+1)(n)     9n^2 + 9n + 2 - 3n^2 - 3n
   = ------------------------  =  -------------------------
               2                             2

        6n^2 + 6n + 2
    =   --------------  =  3n^2 + 3n + 1
              2

So the number of ways of dividing the 6n objects into two groups of 3n 
is

      3n^2 + 3n + 1.

We can do a simple check with n = 1.  Suppose we have 2 red, 2 blue, 
2 green objects. The formula gives 7 ways of dividing the objects into 
two groups of 3.

We could choose 3 objects from 6 in the following ways

   RRB,  RRG,  BBR,  BBG,  GGR,  GGB,  RBG  = 7 ways

So the answer is correct for n = 1 and is a check that there are no 
arithmetic mistakes.

We conclude that the number of arrangements is 3n^2 + 3n + 1.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/