Math Forum Discussions

Brian Alspach

Posts: 3
Registered: 12/6/04

Re: Circular arrangements of n objects taken r at a time allowing (fwd)
Posted: Nov 2, 1999 11:36 AM

Plain Text

>From: Andrew Wayne Graff <andrewwgraff@freei.net> (by way of r!chard
> tchen)
>Subject: Circular arrangements of n objects taken r at a time allowing

This is a problem which is easiest done using Polya's enumeration
theorem. My favorite exposition on Polya's theorem is what de Bruijn
wrote as Chapter 5 in the book "Applied Combinatorics" edited by
Beckenbach and published by Wiley in the early sixties. The formula
appears after the problem statement below.

>I would like to see a formula for the total number of distinct
>circular combinations of n distinct objects taken r at a time
>allowing repetition. In other words, if you have r positions
>around in a circle, and n objects which may be placed in any
>position, then any element of the set of n objects may appear in
>any location, but when rotated, no one arrangement may be
>identical.
>
>ex.:
>n=1,r=1 CCR(1,1)=1 (CCR, meaning circular combinations with
>repetition)
>n=2,r=1 CCR(2,1)=2
>n=3,r=1 CCR(3,1)=3
>...
>n=1,r=2 CCR(1,2)=1
>n=2,r=2 CCR(2,2)=3
>n=3,r=2 CCR(3,2)=6
>...
>n=1,r=3 CCR(1,3)=1
>n=2,r=3 CCR(2,3)=4
>n=3,r=3 CCR(3,3)=11
>n=4,r=3 CCR(4,3)=24
>...
>n=1,r=4 CCR(1,4)=1
>n=2,r=4 CCR(2,4)=6
>n=3,r=4 CCR(3,4)=24
>n=4,r=4 CCR(4,4)=70
>...
>...
>
>I have a general formula for these calculations, however, I am
>not satisfied with how complicated it is. There is a particular
>formula for each value of r, none of which are the same.
>
>The one for r=1 is
>
>f(x)=n
>
>for r=2,
>
> 2
> n +n
>f(x)=----
> 2
>
>for r=3,
>
> 3
> n +2n
>f(x)=-----
> 3
>
>for r=4, however,
>
> 4 2
> n +n +2n
>f(x)=--------
> 4
>
>, ...
>
>As it turns out for all prime values of r, including r=1,
>
> r
> n +(r-1)n
>f(x)=---------
> r
>
>my general formula is something like the following,
>
> p
> ___ g(a )
> \ i
>f(x)= > ----
> /__ a
> i=1 i
>
>where
> q
> ___
> x \
>g(x)=n - > g(b )
> /__ j
> j=1
>
>g(1)=n
>
>{a ,a ,...,a }={positive factors of r}
> 1 2 p
>
>{b ,b ,...,b }={positive factors of x less than x}
> 1 2 j
>
>This is the best generalization I could come up with. Please
>post a simpler solution, if one exists.
>
>Andrew Wayne Graff

What one does is calculate the cycle index for the permutation
group generated by an $r$-cycle. To obtain the cycle index, one
forms a monomial for each permutation in the group; the monomial
is $x_1^{e_l} + x_2^{e_2} + \cdots + x_r^{e_r}$ for a permutation
whose disjoint cycle decomposition has $e_1$ fixed points, $e_2$
transpositions, $e_3$ 3-cycles, ..., $e_r$ r-cycles. Note that
$e_1 + 2e_2 + \cdots + re_r = r$ for a permutation acting on $r$
elements. To get the cycle index, sum all the monomials over the
elements of the group and divide by the order of the group.

In the present case, for the group generated by an $r$-cycle,
one obtains
\[\frac{1}{r}\sum_{d|r}\phi(d)x_d^{r/d},\]
where $\phi$ denotes the Euler totient function and the sum is taken
over all divisors of $r$.

The first few cycle indexes are given by $x_1$ for $r = 1$,
$1/2(x_1^2 + x_2)$ for $r = 2$, $1/3(x_1^3 + 2x_3)$ for $r = 3$,
and $1/4(x_1^4 + x_2^2 + 2x_4)$ for $r = 4$.

To obtain the answer to the enumeration problem posed above,
simply substitute $n$ for each variable in the cycle index.

One can do more. For example, suppose you allow yourself the
same symmetries as you allow an $n$-gon, that is, you allow the
dihedral flips. Then you do the same thing except you now use the
dihedral group rather than the cyclic group.

Also, suppose you would like to know how many patterns there are
using fixed amounts of each of the symbols. Then you assign a
different weight to each of the objects - say $n = 3$; give one
object weight $b$, one object weight $c$ and one object weight $d$ -
and substitute the sum of the weights to the i-th powers for $x_i$ in
the cycle index and look at the coeficients of various terms in the
evaluated expression. For example, in the preceding case of $n = 3$,
the coefficient of $b^2c^2d$ would be the number of arrangements using
two objects of weight $b$, two objects of weight $c$, and one object of
weight $d$ when $r = 5$.

Brian Alspach