Cycle counts and Pairings
Wouter Meeussen
eu000949 at pophost.eunet.be
Thu Apr 27 21:08:55 CEST 2000
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
More information about the SeqFan
mailing list