

A256672


Number of idempotents in the Motzkin monoid of degree n.


1



1, 2, 7, 31, 153, 834, 4839, 29612, 188695, 1243746, 8428597, 58476481, 413893789, 2980489256, 21787216989, 161374041945, 1209258743839, 9155914963702, 69969663242487, 539189056700627
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) is the number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle, such that when gluing the second half of one copy to the first half of the other so that each point k along the intersection is glued to n+1k, the result is homotopic to the original.
a(n+1) > a(n) for every n.
The structure of the Motzkin monoid (and particularly its idempotents and some associated orderings) is governed intimately by the combinatorics of socalled Motzkin paths and Motzkin words, which are related to Dyck paths and words respectively by insertion of punctuation into the words, or marking/coloring subpaths.
Bounded above by A026945, strictly for n > 1. Bounded below by the square of A001006, strictly for n > 1.


LINKS



EXAMPLE

There is one empty graph, which is idempotent under the composition, hence a(0)=1.
There are two on 1 pair of points, the clique and the discrete graph; both are idempotents under the composition, hence a(1)=2.


CROSSREFS



KEYWORD

nonn,hard,more


AUTHOR



EXTENSIONS

a(9)a(13) corrected and a(14)a(16) computed using the Semigroups package for GAP added by James Mitchell, Apr 12 2016


STATUS

approved



