Necklaces vs Bracelets

[Frank Ruskey]

Burnside's Lemma gives:

Length n binary bracelets with k black beads = (T(n,k)+s)/2 where

s = C( n/2,     r/2     )  if n = 0, r = 0 mod 2
    C( (n-2)/2, (r-1)/2 )  if n = 0, r = 1 mod 2
    C( (n-1)/2, r/2     )  if n = 1, r = 0 mod 2
    C( (n-1)/2, (r-2)/2 )  if n = 1, r = 1 mod 2

The expression for s can undoubtedly be simplified with some 
floors, but the above expression is closer to the derivation.

Here's the maple routine I wrote while checking:

> Brace := proc( n, r )
>   local sum;
>   if r mod 2 = 0 and n mod 2 = 0 
>      # then sum := (binomial( (n-2)/2, (r-2)/2 ) + binomial( (n-2)/2, r/2 )
>      #             + binomial( n/2, r/2 ))/2;  fi;
>      then sum := binomial( n/2, r/2 ); fi;
>   if r mod 2 = 1 and n mod 2 = 0
>      then sum := binomial( (n-2)/2, (r-1)/2 );  fi;
>   if r mod 2 = 0 and n mod 2 = 1
>      then sum := binomial( (n-1)/2, r/2 );  fi;
>   if r mod 2 = 1 and n mod 2 = 1
>      then sum := binomial( (n-1)/2, (r-1)/2 );  fi;   
>   return (sum+Neck(2,n,r))/2;
> end;

Cheers,

-Frank R.

"Meeussen Wouter (bkarnd)" wrote:
> 
> ID Number: A047996
> Sequence:  1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,3,4,3,1,1,1,1,
> Name:      Triangle of circular binomial coefficients T(n,k), 0<=k<=n.
> Comments:  T(n,k)=number of necklaces with k black beads, n-k white beads.
> Formula : (1/n) * Sum_{d | (n,k)} phi(d)*binomial(n/d,k/d).
> 
> ID Number: A052307
> Sequence:  1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,3,3,3,1,1,1,1,
>            3,4,4,3,1,1,1,1,4,5,8,5,4,1,1,1,1,4,7,10,10,7,4,1,1,1,1,5,8,
>            16,16,16,8,5,1,1,1,1,5,10,20,26,26,20,10,5,1,1,1,1,6,12,29,
>            38,50,38,29,12,6,1,1,1,1,6
> Name:      Triangle: T(n,k): bracelets (reversible necklaces) with n black
> 
>               beads and n-k white beads.
> Formula : nihil !
> xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> Author(s): Christian G. Bower (bowerc at usa.net), Nov 1999.
> 
> for even rows (=2n beads) and m=1..n this appears to be :
> (1/2)*(C(2*(n\2),m\2) +Sum (d|(2n,m) phi(d)C(2n/d,m/d) ) - (-1)^n
> if(even(n+m) ,0, C(n-1, floor(m/2-1/2) )
> 
> who can give the formula for the complete A052307 ?
> 
> greets,
> 
> W.
> 
> Wouter Meeussen
> email : wouter.meeussen at vandemoortele.com
> 
> ===============================
> This email is confidential and intended solely for the use of the individual to whom it is addressed.
> If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited.
> You are explicitly requested to notify the sender of this email that the intended recipient was not reached.

-- 
----------------------
Frank Ruskey                     e-mail: fruskey at cs.uvic.ca <- NEW!
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~fruskey