|
|
A007853
|
|
Number of maximal antichains in rooted plane trees on n nodes.
|
|
16
|
|
|
1, 2, 5, 15, 50, 178, 663, 2553, 10086, 40669, 166752, 693331, 2917088, 12398545, 53164201, 229729439, 999460624, 4374546305, 19250233408, 85120272755, 378021050306, 1685406494673, 7541226435054, 33852474532769, 152415463629568, 688099122024944
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Also the number of initial subtrees (emanating from the root) of rooted plane trees on n vertices, where we require that an initial subtree contains either all or none of the branchings under any given node. The leaves of such a subtree comprise the roots of a corresponding antichain cover. Also, in the (non-commutative) multicategory of free pure multifunctions with one atom, a(n) is the number of composable pairs whose composite has n positions. - Gus Wiseman, Aug 13 2018
The g.f. is denoted by y_2 in Bacher 2004 Proposition 7.5 on page 20. - Michael Somos, Nov 07 2019
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1/4) * (3 - 2*x - sqrt(1-4*x) - sqrt(2) * sqrt((1+2*x) * sqrt(1-4*x) + 1 - 8*x + 2*x^2)) [from Klazar]. - Sean A. Irvine, Feb 06 2018
a(n) = (1/(n+1))*C(2*n,n) + Sum_{k=0..n-1} ((k+2)/(n+1))*C(2*n-k-1,n-k-1)*Sum_{i=0..floor(k/2)} C(2*i,i)*C(k+i,3*i)/(i+1). - Vladimir Kruchinin, Apr 05 2019
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 5*x^3 + 15*x^4 + 50*x^5 + 178*x^6 + 663*x^7 + 2553*x^8 + ... - Michael Somos, Nov 07 2019
|
|
MATHEMATICA
|
ie[t_]:=If[Length[t]==0, 1, 1+Product[ie[b], {b, t}]];
allplane[n_]:=If[n==1, {{}}, Join@@Function[c, Tuples[allplane/@c]]/@Join@@Permutations/@IntegerPartitions[n-1]];
Table[Sum[ie[t], {t, allplane[n]}], {n, 9}] (* Gus Wiseman, Aug 13 2018 *)
|
|
PROG
|
(Maxima)
a(n):=1/(n+1)*binomial(2*n, n)+sum((k+2)/(n+1)*binomial(2*n-k-1, n-k-1)*(sum(((binomial(2*i, i))*(binomial(k+i, 3*i)))/(i+1), i, 0, floor(k/2))), k, 0, n-1); /* Vladimir Kruchinin, Apr 05 2019 */
(PARI) {a(n) = my(A); if( n<0, 0, A = sqrt(1 - 4*x + x * O(x^n)); polcoeff( (3 - 2*x - A - sqrt(2 - 16*x + 4*x^2 + (2 + 4*x) * A)) / 4, n))}; /* Michael Somos, Nov 07 2019 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|