|
|
A335349
|
|
a(n) counts anti-chains of size three in "0,1,2" Motzkin trees on n edges.
|
|
1
|
|
|
2, 16, 98, 500, 2308, 9920, 40522, 159212, 606790, 2256544, 8224202, 29473012, 104124044, 363374560, 1254711038, 4292365876, 14564351510, 49059814576, 164186524940, 546276316120, 1807990549352, 5955265349696, 19530431537488, 63795464433440, 207623760855106, 673440401953856
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
4,1
|
|
COMMENTS
|
"0,1,2" trees are rooted trees where each vertex has outdegree zero, one, or two. They are counted by the Motzkin numbers A001006.
A005717(n+1) is the total number of vertices (= anti-chains of size 1) in all "0,1,2" trees with n edges, while A178834(n) is the total number of anti-chains of size 2 in all "0,1,2" trees on n edges.
|
|
LINKS
|
|
|
FORMULA
|
G.f. is A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1) * M(z)^r = 2 * z^4 * T(z)^5 * M(z)^3 (with r = 3), where M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2)) / (2*z^2) is the g.f. of the Motzkin numbers A001006 and T(z) = 1 / sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426.
|
|
EXAMPLE
|
Out of the A001006(4) = 9 Motzkin rooted trees, there are only two that have anti-chains of size 3 (i.e., 3-sets of pairwise incomparable nodes), and each one has only one such an anti-chain. Thus, a(4) = 1 + 1 = 2.
In the first Motzkin tree below with 4 edges, {E, C, D} is an anti-chain of size 3. In the second one, {G, I, K} is an anti-chain of size 3.
A F
/ \ / \
/ \ / \
B E G H
/ \ / \
/ \ / \
C D I K
|
|
PROG
|
(PARI) M(z) = (1 - z - sqrt(1 - 2*z - 3*z^2))/(2*z^2);
T(z) = 1/sqrt(1 - 2*z - 3*z^2);
my(z='z+O('z^30)); Vec(2*z^4*T(z)^5*M(z)^3)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|