Cycle counts and Pairings

[Wouter Meeussen]

In Richard P. Stanley's "Problems on Catalan and Related Numbers"
(Enumerative Combinatorics, vol. 2) , example (cc), it is mentioned that the
permutations w of [2n] with n cycles of length 2, such that the product
((1,2,..,2n)) . w has n+1 cycles, are counted by the Catalans (.. and have a
bijection with the plane binary trees on n vertices..)

in plain, the product of (1,2,..,2n)_cyc with the (2n-1)!! pairings of 2n
gives exactly (n+1) cycles for Catalan[n] of the (2n-1)!! cases. These are
the cases where the number of cycles is maximal. R. Stanley's "max cycle
count pairings" turn out to be the non-crossing ones. Other Cycle counts are
(n-1, n-3,.. 1 or 2 : dependend on n even or odd).
The complete classification by cycle count over *all* pairings is given
(reversed) in A035309 :

      {1}
      {1, 2}
      {10, 5}
      {21, 70, 14}
      {483, 420, 42}
      {1485, 6468, 2310, 132}

of course, the row-sums are (2n-1)!! = 1*3*5*7* ...
-----------------------------------
ID Number: A035309
Sequence:  1,1,2,1,5,10,14,70,21,42,420,483,132,2310,6468,1485,429,
           12012,66066,56628,1430,60060,570570,1169740,225225,4862,
           291720,4390386,17454580,12317877
Name:      Triangle giving number of ways to glue sides of a 2n-gon so as to
produce a
           surface of genus g.
Formula:   Let c be number of cycles that appear in product of a (2n)-cycle
and a
           product of n disjoint transpositions; genus is g = (n-c+1)/2
Example:   1; 1; 2,1; 5,10; 14,70,21; 42,420,483; ...
See also:  First 3 cols are A000108, A002802, A006298.
Keywords:  nonn,tabf,nice
Offset:    1
Author(s): Dylan Thurston (Dylan.Thurston at math.unige.ch)
---------------------------------
A funny thing, that might be checked out, is that the GCD of each row is:
{1, 1, 1, 5, 7, 21, 33, 429, 715, 2431}
where the 1st, 2nd, 4th, 8th seem to be cat[n] themselves. Does this go on
to the (2^n)-th  for all those odd catalans?



If we now look into more detail, and not only *count* cycles, but *classify*
them according to partitions of 2n, we surprisingly find that the
permutations with cycle lengths 
{3,1,1,1}               n=3     occurs 2 times
{3,3,1,1,1,1}           n=5     occurs 5 times
{3,3,3,1,1,1,1,1}       n=7     occurs 14 times
...
{(n-1)/2 threes , (n+3)/2  ones}   occur cat[(n+1)/2] times.
This is an example of Catalans within Catalans.


So, I hear you wonder, what about the Tableaux of form {2,2,2,...}?
They're different from the non-crossers (except for the common pairing with
rank 1), what about their classification by cycle counts after
left-multiplying with (1,2,..,2n)_cyc ?

count of Tableaux-pairings      count of cycles

{1}                             2
{1, 1}                          3,1
{1, 4}                          4,2
{1, 8, 5}                       5,3,1
{1, 12, 29}                     6,4,2        
{1, 16, 78, 37}                 7,5,3,1
{1, 20, 146, 262}               8,6,4,2
{1, 24, 230, 844, 331}          9,7,5,3,1
{1, 28, 330, 1832, 2671}        10,8,6,4,2

of course, the row-sums must be cat[n]={1,2,5,14,42,..}

Not earth-shaking, but any partitioning scheme for the catalans holds some
"je-ne-sais-quoi",
if you'll pardon my French.
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be