Necklaces and Catalans.

[Antti Karttunen]

Antti Karttunen wrote:
> 
> Something related, or not:
> 
> At the summer-cottage I found a (quite easy) combinatorial proof that
> the next-to-central columns of A047996:
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A047996
> are indeed equal to Catalan numbers, A000108.
> Is this is anything new? Also, cursorily reading Stanley's Catalan excercises
> http://www-math.mit.edu/~rstan/ec/catalan.pdf
> and the addendun http://www-math.mit.edu/~rstan/ec/catadd.pdf
> (I might not have the most recent copy printed)
> I didn't find there any interpretation like
> "necklaces of n white beads and n+1 black beads", but maybe
> it occurs there in disguise.

Ummh, it's actually simpler than I thought... Sorry to bother everybody
with these trivialities, but here it comes, an proof why the next-to-centre
columns of A047996 (the necklaces of n white beads and n+1 black beads and
vice versa) are counted by Catalan numbers A000108, and why for the
corresponding bracelets A007123 (where the necklaces obtained from each another
by turning over are also counted to belonging to the same equivalence
class), has the formula (A000108(n)+A001405(n))/2
 = (Cat(n)+binomial(n,floor(n/2)))/2.

The first proof is almost a direct copy from Graham, Knuth, Patashnik:
"Concrete Mathematics", pages 345 & 346 (from the Chapter 7, "Generating
Function"), utilizing Raney's lemma (by George Raney, 1959):

  If <x1,x2,...,xm> is any sequence of integers whose sum is +1,
then exactly one of the cyclic shifts
 <x1,x2,...,xm>, <x2,...,xm,x1>, ..., <xm,x1,...,x_m-1>
has all of its partial sums positive.

In our case, we have (2n+1 choose n) binary strings of
n 1's and n+1 0's (from now on I call such binary strings
(n,n+1)-binary strings), and 1/(2n + 1) of these map to
a plane binary trees for example using the depth-first
encoding as Wouter used in his SeqFan-message
with the subject: "je-ne-sais-quoi, again..." posted Tue, 2 May 2000
(which you can blame for me getting hooked into these
things, and sharing my enthusiasm also with you...)

say

 0   0
  \ /
 0 1 0   0
  \/  \ /
   1   1
    \ /
     1

is mapped depth-first-wise, left branch before the right
one (1's are the branching nodes, 0's the leaves) to:

  110100100

and this time we take also the last zero explicitly to the binary
string so as to get n 1's and n+1 0's.
(This last zero is not included in the sequences A014486/A063171
of totally balanced binary sequences.)

Now change 1's to +1's and 0's to -1's, and start summing
from +1 because at first we have one "sprouting point" open for
growing a binary tree, and when any branching node (= 1 in code)
is added to it, it takes one sprouting point and adds two,
while any leaf (= 0) takes one sprouting point, and in the end
we know we have finished our binary tree construction process
when there are 0 "sprouting points" open, so the sum (of -1's
and +1's) should in the end be 0 without having gone zero
or negative meanwhile.

So, Raney's lemma says that _exactly one_ rotation of
_any_ (n,n+1)-binary string is such a valid binary tree
encoding. Now, because all these (n,n+1)-necklaces
are aperiodic (*) (because gcd(n,n+1)=1, I would say),
each necklace equivalence class contains
2n+1 members (all 2n+1 rotations of any (n,n+1) binary string
are distinct), so the number of separate equivalence classes
is
(2n+1 choose n)/(2n + 1) = (2n choose n)/(n+1) = Cat(n).

(See page 346 of "Concrete Mathematics").

(* This means also that Catalans occur also
as next-to-centre columns of the triangle A051168:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=051168
)

Now, to count the bracelets of n black beads and n+1 white
beads, one must pair any two necklace equivalence
classes where a binary string in the other can be obtained
by reversing a binary string in the other (as a single
equivalence class of bracelets), except those equivalence
classes which contain a palindrome (n,n+1)-binary string,
which thus form a bracelet class of their own.

If the length of (n,n+1) binary palindrome is 4n+1,
then the central element must be zero, e.g. 100101001
and if the length is 4n+3, then the central element
must be 1, e.g. 1001001.

The number of such (n,n+1) binary palindromes
(in either case) is A001405(n) = (n choose [n/2]) where
[ ] denotes the floor function.

Now, the crucial point is that each equivalence
class of (n,n+1)-necklaces can contain at most one such
palindrome, i.e. it is not possible to obtain
another, different palindrome just by rotating
(n,n+1)-palindrome. (This doesn't hold for
(n,n)-palindromes, as 00111100 rotated 4 steps
to either direction is 11000011).

The bad point is that I cannot prove this now
rigorously, but it's just my intuition that
says it strongly. I though first that it revolved
around the fact that phi(2n+1) > n
for all n: draw a (n,n+1)-necklace as a
circle, mark e.g. the topmost node as "the
central bead" and then try rotating by various steps
to see what kind of equivalencies it forces
on beads if one assumes that the original
arrangement was a palindrome, and the resulting
one must be also. The divisors of 2n+1
seems to be the most "promising" quantities for rotation,
and even then all the nodes belonging to the reduced
residue set of 2n+1 seem to be forced to be
of the same colour. Unfortunately that
doesn't hold, the first counter-example occurs
at n=52: phi((2*52)+1) = phi(105) = phi(3*5*7) = 48, 
Probably the proof is much simpler.
(or then I'm a fool again...)

Anyways, if that "max-one-palindrome-per-(n,n+1)-necklace-class-lemma"
holds, then we know we have precisely

    A000108(n)+A001405(n)
    ---------------------
              2

i.e. (Cat(n)+binomial(n,floor(n/2)))/2
equivalence classes of (n,n+1)-bracelets,
and we can add to A007123 the following rows:

%F A007123 a(n) = (A000108(n)+A001405(n))/2.
%Y A007123 Occurs as the row 164 in the table A073201.


Hmm, Neil seems to have just added something on
these lines, while I wrote this document.

Well, if somebody can give a nice proof for that
"max-one-palindrome-per-(n,n+1)-necklace-class-lemma"
we could take that "It appears that" phrase off,
(and somebody else gets his/her name also there... 8-)


Yours,

Antti Karttunen