Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
Math Forum
»
Discussions
»
Math Topics
»
discretemath
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Re: Circular arrangements of n objects taken r at a time allowing (fwd)
Replies:
0
|
 |
|
|
Re: Circular arrangements of n objects taken r at a time allowing (fwd)
Posted:
Nov 2, 1999 11:36 AM
|
|
>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
|
|
|
|