|
|
Bob wrote:
> Supposed you are given 4 red balls, 4 blue balls and 4 green balls. You
> want to arrange them in a row such that no 2 adjacent balls are of the
> same colour.
>
> (i)How many ways of doing so?
>
> (ii) Is there a generalisation for n balls of each colour?
> (iii) What if the balls are arranged in a circle? What is the relation
> to (i)?
>
> Thanks all
The answer to (iii) depends on whether you want to count rotations and
reflections as different arrangements. For example, is RGBRGB (written
in a circle) different from GBRGBR, and is it different from BGRBGR?
Assuming that rotations and reflections ARE counted separately (where
not identical, obviously), I get this rather messy answer:
sum over 0 <= p <= n, p even integer {A*B + D*E}
where
A = 2 * C(n-1, p/2)^2
B = C(2*n+1-p, n-p) - C(2*n-1-p, n-2-p)
for p = 0,
D = 0
for p > 0,
D = 2 * C(n-1, p/2-1)^2 * (2*n-p)/p
E = 2 * C(2*n-p, n-p)
C() is a binomial coefficient. If y < 0 then C(x,y) is taken to be
zero.
The first few values that I get are:
n No. arrangements
-- ----------------
1 6
2 24
3 132
4 804
5 5196
6 34872
7 240288
8 1688244
9 12040188
10 86892384
11 633162360
12 4650680640
13 34390540320
14 255773538240
15 1911730760832
16 14350853162676
17 108139250403804
18 817629606524112
Similar idea to before:
A is the number of ways of arranging n red balls and n green balls in a
circle such that there are exactly p instances of adjacent balls of the
same colour AND the start and end balls are different colours. (For
example, RRGG is an instance of n = 2, p = 2.)
B is the number of ways of interspersing n blue balls amongst each of
the A red/green arrangements such that no two adjacent balls have the
same colour.
D is the number of ways of arranging n red balls and n green balls in a
circle such that there are exactly p instances of adjacent balls of the
same colour AND the start and end balls are the same colour. (For
example, RGGR is an instance of n = 2, p = 2.)
E is the number of ways of interspersing n blue balls amongst each of
the D red/green arrangements such that no two adjacent balls have the
same colour.
|
|