A318049 -id:A318049 - cp's OEIS frontend

A007853 Number of maximal antichains in rooted plane trees on n nodes.

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

Offset: 1

Martin Klazar

nonn

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

			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

R. Bacher, On generating series of complementary plane trees arXiv:math/0409050 [math.CO], 2004.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
Index entries for sequences related to rooted trees

Cf. A000081, A000108, A001003, A001006, A126120, A213705, A317713, A318046, A318048, A318049.

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 *)

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 */

{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 */

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
Given the g.f. A(x) and the g.f. of A213705 B(x), then -x = A(-B(x)). - Michael Somos, Nov 07 2019

More terms from Sean A. Irvine, Feb 06 2018

A102403 Number of Dyck paths of semilength n having no ascents of length 2.

Original entry on oeis.org

1, 1, 1, 2, 6, 17, 46, 128, 372, 1109, 3349, 10221, 31527, 98178, 308179, 973911, 3096044, 9894393, 31770247, 102444145, 331594081, 1077022622, 3509197080, 11466710630, 37567784437, 123380796192, 406120349756, 1339571374103

Offset: 0

Emeric Deutsch, Jan 06 2005

nonn

Number of Łukasiewicz paths of length n having no (1,1) steps. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: a(4)=6 because we have HHHH, HU(2)DD, U(2)DDH, U(2)DHD, U(2)HDD and U(3)DDD where H=(1,0), U(2)=(1,2), U(3)=(1,3) and D=(1,-1).

Also the number of series-reduced Mathematica expressions with one atom and n + 1 positions. Also the number of rooted plane trees with n + 1 nodes in which there are no binary branchings (nodes of out-degree 2). - Gus Wiseman, Aug 14 2018

			a(3)=2 because we have UDUDUD and UUUDDD, where U=(1,1) and D=(1,-1); the other three Dyck paths of semilength 3, namely UD(UU)DD, (UU)DDUD and (UU)DUDD, have ascents of length 2 (shown between parentheses).
From _Gus Wiseman_, Aug 14 2018: (Start)
The a(5) = 17 series-reduced Mathematica expressions:
  o[o[][],o]
  o[o,o[][]]
  o[o[],o[]]
  o[o[],o,o]
  o[o,o[],o]
  o[o,o,o[]]
  o[o,o,o,o]
  o[][o[],o]
  o[][o,o[]]
  o[][o,o,o]
  o[][][o,o]
  o[o[],o][]
  o[o,o[]][]
  o[o,o,o][]
  o[][o,o][]
  o[o,o][][]
  o[][][][][]
The a(5) = 17 rooted plane trees with no binary branchings:
  (((((o)))))
  (((ooo)))
  (((o)oo))
  ((o(o)o))
  ((oo(o)))
  ((oooo))
  (((o))oo)
  (o((o))o)
  (oo((o)))
  ((o)(o)o)
  ((o)o(o))
  (o(o)(o))
  ((o)ooo)
  (o(o)oo)
  (oo(o)o)
  (ooo(o))
  (ooooo)
(End)

Robert Israel, Table of n, a(n) for n = 0..1700
Eric S. Egge and Kailee Rubin, Snow Leopard Permutations and Their Even and Odd Threads, arXiv:1508.05310 [math.CO], 2015.
Index entries for sequences related to Łukasiewicz

Cf. A000108, A001003, A001006, A007853, A102402, A126120, A318049.

Order:=35: S:=solve(series(V*(1-V)/(1-V^2+V^3),V)=z,V): seq(coeff(S,z^n),n=1..33); # V=zG
P:= gfun:-rectoproc({(69*n^2+207*n+138)*a(n)+(97*n^2+609*n+830)*a(n+1)+(-38*n^2-342*n-694)*a(n+2)+(37*n^2+333*n+734)*a(n+3)+(2*n^2+18*n+34)*a(n+4)+(-7*n^2-87*n-266)*a(n+5)+(n^2+15*n+56)*a(n+6), a(0)=1,a(1)=1,a(2)=1,a(3)=2,a(4)=6,a(5)=17},a(n),remember):
seq(P(n),n=0..50); # Robert Israel, Aug 24 2015

a[n_] := 1/(n+1) Sum[Binomial[n+1, j] Binomial[3j-n-3, j-1] (-1)^(n+1-j), {j, n+1, (n+3)/3, -1}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 21 2018, after Vladimir Kruchinin *)

a102403(n):=1/n*sum(binomial(n,j)*binomial(3*j-n-2,j-1)*(-1)^(n-j),j,ceiling((n+2)/3),n); /* Vladimir Kruchinin, Mar 07 2011 */

Vec( serreverse( O(x^33) + x/(1+x/(1-x)-x^2) ) /x )  \\ Joerg Arndt, Apr 28 2016

G.f.: G=G(z) satisfies z^3*G^3 + z(1-z)G^2 - G + 1 = 0.
a(n) = (1/n)*Sum_{j=ceiling((n+2)/3)..n} binomial(n,j)*binomial(3*j-n-2,j-1)*(-1)^(n-j), n > 0. - Vladimir Kruchinin, Mar 07 2011
From Gary W. Adamson, Jan 30 2012: (Start)
a(n) is the upper left term in M^n, M = an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  0, 1, 1, 0, 0, 0, ...
  1, 0, 1, 1, 0, 0, ...
  1, 1, 0, 1, 1, 0, ...
  1, 1, 1, 0, 1, 1, ... (End)
(69*n^2+207*n+138)*a(n) + (97*n^2+609*n+830)*a(n+1) + (-38*n^2-342*n-694)*a(n+2) + (37*n^2+333*n+734)*a(n+3) + (2*n^2+18*n+34)*a(n+4) + (-7*n^2-87*n-266)*a(n+5) + (n^2+15*n+56)*a(n+6) = 0. - Robert Israel, Aug 24 2015
Recurrence (of order 4): (n+1)*(n+2)*(28*n^2 - 32*n - 39)*a(n) = 4*(n+1)*(14*n^3 - 9*n^2 - 62*n + 39)*a(n-1) + (140*n^4 - 160*n^3 - 401*n^2 + 469*n - 78)*a(n-2) - 12*(n-2)*(14*n^3 - 9*n^2 - 28*n - 8)*a(n-3) + 23*(n-3)*(n-2)*(28*n^2 + 24*n - 43)*a(n-4). - Vaclav Kotesovec, Mar 06 2016
a(n) ~ s * sqrt((1 - 2*r + 3*r^2*s)/(1 - r + 3*r^2*s)) /(2*sqrt(Pi)*n^(3/2)*r^n), where r = 0.2869905464691794898... and s = 1.850270202250705342... are roots of the system of equations 3*r^3*s^2 = 1 + 2*(-1 + r)*r*s, 1 + r^3*s^3 = s + (-1 + r)*r*s^2. - Vaclav Kotesovec, Mar 06 2016

A303022 Number of free pure symmetric multifunctions (with empty expressions allowed) with one atom, n positions, and no unitary parts (subexpressions of the form x[y]).

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 27, 63, 152, 376, 939, 2371, 6047, 15577, 40429, 105637, 277625, 733518, 1947126, 5190503, 13888811, 37291968, 100444019, 271316998, 734802247, 1994873116, 5427893149, 14799525982, 40429761365, 110645688034, 303316712450, 832799212777

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

Also the number of orderless Mathematica expressions with one atom, n positions, and no unitary parts.

			The a(6) = 12 Mathematica expressions:
  o[o,o[][]]
  o[o[],o[]]
  o[o,o,o[]]
  o[o,o,o,o]
  o[][o,o[]]
  o[][o,o,o]
  o[][][o,o]
  o[o,o[]][]
  o[o,o,o][]
  o[][o,o][]
  o[o,o][][]
  o[][][][][]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000108, A001003, A001006, A007853, A102403, A126120, A318049.

Cf. A303023, A303024, A303025, A303026, A303027.

allOLBF[n_]:=allOLBF[n]=If[n==1,{"o"},Join@@Cases[Table[PR[k,n-k-1],{k,n-1}],PR[h_,g_]:>Join@@Table[Apply@@@Tuples[{allOLBF[h],Select[Union[Sort/@Tuples[allOLBF/@p]],Length[#]!=1&]}],{p,IntegerPartitions[g]}]]];
Table[Length[allOLBF[n]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, my(t=EulerT(v)-v); v=concat(v, v[n-1] + sum(k=1, n-2, v[k]*t[n-k-1]))); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(21) and beyond from Andrew Howroyd, Aug 19 2018

A303027 Number of free pure symmetric multifunctions with one atom, n positions, and no empty or unitary parts (subexpressions of the form x[] or x[y]).

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 3, 5, 7, 15, 28, 47, 90, 175, 319, 607, 1181, 2251, 4325, 8449, 16425, 31992, 62823, 123521, 243047, 480316, 951290, 1886293, 3749341, 7467815, 14893500, 29752398, 59532947, 119274491, 239275400, 480638121, 966571853, 1945901716, 3921699524

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

Also the number of orderless Mathematica expressions with one atom, n positions, and no empty or unitary parts.

			The a(10) = 15 Mathematica expressions:
  o[o,o[o,o[o,o]]]
  o[o,o[o,o][o,o]]
  o[o[o,o],o[o,o]]
  o[o,o][o,o[o,o]]
  o[o,o[o,o]][o,o]
  o[o,o][o,o][o,o]
  o[o,o[o,o,o,o,o]]
  o[o,o,o[o,o,o,o]]
  o[o,o,o,o[o,o,o]]
  o[o,o,o,o,o[o,o]]
  o[o,o][o,o,o,o,o]
  o[o,o,o][o,o,o,o]
  o[o,o,o,o][o,o,o]
  o[o,o,o,o,o][o,o]
  o[o,o,o,o,o,o,o,o]

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000108, A001003, A001006, A007853, A102403, A126120, A318049.

Cf. A303022, A303023, A303024, A303025, A303026.

allOLZR[n_]:=allOLZR[n]=If[n==1,{"o"},Join@@Cases[Table[PR[k,n-k-1],{k,n-1}],PR[h_,g_]:>Join@@Table[Apply@@@Tuples[{allOLZR[h],Select[Union[Sort/@Tuples[allOLZR/@p]],Length[#]>1&]}],{p,IntegerPartitions[g]}]]];
Table[Length[allOLZR[n]],{n,25}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1]); for(n=2, n, my(t=EulerT(v)-v); v=concat(v, sum(k=1, n-2, v[k]*t[n-k-1]))); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(29) and beyond from Andrew Howroyd, Aug 19 2018

cp's OEIS Frontend

A007853 Number of maximal antichains in rooted plane trees on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A102403 Number of Dyck paths of semilength n having no ascents of length 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A303022 Number of free pure symmetric multifunctions (with empty expressions allowed) with one atom, n positions, and no unitary parts (subexpressions of the form x[y]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A303027 Number of free pure symmetric multifunctions with one atom, n positions, and no empty or unitary parts (subexpressions of the form x[] or x[y]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions