|
|
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+1-k, 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 so-called 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
|
|
|
|