Necklaces and Catalans.

[Meeussen Wouter (bkarnd)]

Nice article by Martin Gardner in Scientific American of 1976.
That's where I got my inspiration.

Wouter Meeussen
email : wouter.meeussen at pandora.be


-----Original Message-----
From: Richard Guy [mailto:rkg at cpsc.ucalgary.ca]
Sent: vrijdag 9 augustus 2002 15:12
To: Antti Karttunen
Cc: Frank Ruskey; Christian G.Bower; Wouter Meeussen;
njas at research.att.com; rstan at math.mit.edu; Seqfan (E-mail)
Subject: Re: Necklaces and Catalans.


See `Mountains and Catalan Numbers' on p.105 of
The Book of Numbers.  Note the introduction of
an additional upstroke to facilitate the
correspondence and the proof.  And while you're
there, look at `parentheses' on the opposite
page.  We were aware at the time that
`parentheses' could mean two different things:

   (a) just a pretty pattern formed by not
closing a parenthesis unless it's already been
opened.

   (b) as a means of indicating the order of
binary operations on a string of symbols.

They both lead to Catalan numbers, but a simple
bijection eluded us at the time.  This was since
supplied by Mark Krusemeyer and others.   R.

On Fri, 9 Aug 2002, Antti Karttunen wrote:

> 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?An
um=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?An
um=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


===============================
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.