[seqfan] Unlabeled super-Catalan - was unlabeled Motzkin

David Scambler dscambler at bmm.com
Tue Jan 4 05:30:45 CET 2011


Seqfans,

Following Max Alekseyev's post Oct 27 2010 regarding a chords on unlabeled points of a circle, 
i.e. Motzkin numbers up to rotation (added as A175954), NJAS commented that the same idea could 
be applied to the many interpretations of Catalan, Motzkin, Schroeder numbers etc.

So here is one such attempt...

Interpret the super-Catalan sequence (A001003) as follows:

"Ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced
but there is no restriction on the number of pairs of parentheses. The number of letters
inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are
ignored."  - Fan, Mansour and Pang "Elements of the sets enumerated by super-Catalan numbers".

So a(3) = 11: (xx)xx, x(xx)x, xx(xx), (xx)(xx), (xxx)x, x(xxx),((xx)x)x, (x(xx))x, x((xx)x), x(x(xx)), xxxx.

Now picture the x's and parentheses as equally spaced points on a circle with chords joining paired parentheses 
and x's having no chord. Circles thus produced may have n+1, n+3, ..., 3*n-1 points.

====================================
The count of circles decomposed by number of points on the circle yields the triangle (A033282):
(rows start at n=1 and sum to A001003(n))

1
1 2
1 5  5
1 9  21  14 
1 14 56  84  42
1 20 120 300 330 132
..

It is readily apparent that the right diagonal shows the Catalan numbers (A000106).

Now, circles have a natural interpretation of rotation and reflection, so...

====================================
Removing rotational symmetry I get these counts:

a(n) = 1,1,2,6,17,74,324,1558,7640,38245,... (not in OEIS)

The corresponding triangle is:

1
1 1
1 2 3
1 2 7  7
1 3 15 33 22
1 3 24 94 136 66
...

The right diagonal is apparently A007595 (confirmed up to 10 terms)

====================================
Removing rotational symmetry and reflections, I get these counts:

a(n) = 1,1,2,5,12,44,176,809,3883,19265,... (not in OEIS)

The corresponding triangle is:

1
1 1
1 2 2
1 2 5  4
1 3 10 18 12
1 3 16 51 71 34
...

The right diagonal is apparently A001895 (confirmed up to 10 terms)

I have no formula or g.f. for these sequences.

Regards
dave



More information about the SeqFan mailing list