Necklaces vs Bracelets
Antti Karttunen
karttu at megabaud.fi
Fri Aug 9 03:10:30 CEST 2002
Frank Ruskey wrote:
>
> 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.
I reckon that Frank meant above with "r" the same as with "k",
and T(n,k) is A047996(n,k).
Anyways, combined with the proof based on Raney's lemma
that A047966(2n+1,n) = A000108(n) this is enough to prove
that A007123(n) = (A000108(n)+A001405(n))/2.
(And you can forget my previous long-winding mail...)
-- Antti
More information about the SeqFan
mailing list