A318046 -id:A318046 - 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

A318049 Number of first/rest balanced rooted plane trees with n nodes.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 3, 2, 6, 8, 11, 26, 28, 67, 96, 162, 316, 448, 922, 1435, 2572, 4660, 7563, 14397, 23896, 43337, 77097, 133071, 244787, 423093, 767732, 1367412, 2426612, 4408497, 7802348, 14152342, 25365035, 45602031, 82631362, 148246136, 269103870, 485379304

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

A rooted plane tree is first/rest balanced if either (1) it is a single node, or (2a) the number of leaves in the first branch is equal to the number of branches minus one, and (2b) every branch is also first/rest balanced.

Also the number of composable free pure multifunctions (CPMs) with one atom and n positions. A CPM is either (case 1) the leaf symbol "o", or (case 2) an expression of the form h[g_1, ..., g_k] where h and each of the g_i for i = 1, ..., k > 0 are CPMs, and the number of leaves in h is equal to k. The number of positions in a CPM is the number of brackets [...] plus the number of o's.

			The a(12) = 11 first/rest balanced rooted plane trees:
  (o(o(o((oo)oo))))
  (o(o((oo)(oo)o)))
  (o(o((oo)o(oo))))
  (o((oo)(o(oo))o))
  (o((oo)o(o(oo))))
  (o((oo)(oo)(oo)))
  ((oo)(o(o(oo)))o)
  ((oo)o(o(o(oo))))
  ((o(o(oo)))oooo)
  ((oo)(o(oo))(oo))
  ((oo)(oo)(o(oo)))
The a(12) = 11 composable free pure multifunctions:
  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..100

Cf. A000081, A000108, A001003, A001006, A007853, A126120, A317713, A318046, A318048.

balplane[n_]:=balplane[n]=If[n===1,{{}},Join@@Function[c,Select[Tuples[balplane/@c],Length[Cases[#[[1]],{},{0,Infinity}]]==Length[#]-1&]]/@Join@@Permutations/@IntegerPartitions[n-1]];
Table[Length[balplane[n]],{n,10}]

seq(n)={my(p=x*y+O(x^2)); for(n=1, n\2, p = x*y + x*sum(k=1, n, y^k * polcoef(p,k,y) * (O(x^(2*n-k+1)) + p)^k )); Vec(subst(p + O(x*x^n), y, 1)) } \\ Andrew Howroyd, Jan 22 2021

G.f.: A(x,1) where A(x,y) satisfies A(x,y) = x*(y + Sum_{k>=1} y^k * ([y^k] A(x,y)) * A(x,y)^k). - Andrew Howroyd, Jan 22 2021

Terms a(21) and beyond from Andrew Howroyd, Jan 22 2021

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 4, 4, 2, 6, 6, 5, 4, 6, 3, 9, 2, 6, 6, 4, 6, 6, 8, 10, 4, 12, 6, 10, 4, 9, 9, 6, 2, 12, 6, 9, 6, 6, 4, 9, 6, 9, 7, 6, 8, 15, 10, 15, 4, 5, 12, 9, 7, 4, 10, 16, 4, 7, 9, 8, 9, 10, 10, 11, 2, 13, 12, 6, 7, 14, 10, 9, 6, 10, 7, 21, 3, 12, 10, 12, 6

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

The span of a tree is defined to be the set of possible terminal subtrees of initial subtrees, or, which is the same, the set of possible initial subtrees of terminal subtrees.

			42 is the Matula-Goebel number of (o(o)(oo)), which has span {o, (o), (oo), (ooo), (oo(oo)), (o(o)o), (o(o)(oo))}, so a(42) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A109082, A109129, A206491, A317713, A318046.

ext[c_,{}]:=c;ext[c_,s:{}]:=Extract[c,s];rpp[c_,v_,{}]:=v;rpp[c_,v_,s:{}]:=ReplacePart[c,v,s];
RLO[ear_,rue:{}]:=Union@@(Function[x,rpp[ear,x,#2]]/@ReplaceList[ext[ear,#2],#1]&@@@Select[Tuples[{rue,Position[ear,_]}],MatchQ[ext[ear,#[[2]]],#[[1,1]]]&]);
RL[ear_,rue:{}]:=FixedPoint[Function[keeps,Union[keeps,Join@@(RLO[#,rue]&/@keeps)]],{ear}];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
MGTree[n_]:=If[n==1,{},MGTree/@primeMS[n]];
Table[Length[Union[Cases[RL[MGTree[n],{List[__List]:>List[]}],_List,{1,Infinity}]]],{n,100}]

A333267 If n = Product (p_j^k_j) then a(n) = Product (a(pi(p_j)) * k_j), where pi = A000720.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 2, 1, 4, 2, 2, 3, 2, 2, 1, 2, 3, 2, 1, 3, 4, 1, 1, 1, 5, 1, 2, 2, 4, 2, 3, 1, 3, 1, 2, 2, 2, 2, 2, 1, 4, 4, 2, 2, 2, 4, 3, 1, 6, 3, 1, 2, 2, 2, 1, 4, 6, 1, 1, 3, 4, 2, 2, 2, 6, 2, 2, 2, 6, 2, 1, 1, 4, 4, 1, 2, 4, 2, 2, 1, 3, 3, 2, 2, 4, 1, 1, 3, 5, 2, 4, 2, 4

Offset: 1

Ilya Gutkovskiy, Mar 13 2020

			a(36) = a(2^2 * 3^2) = a(prime(1)^2 * prime(2)^2) = a(1) * 2 * a(2) * 2 = 4.

Cf. A000026, A000720, A002110, A003963, A005361, A054725, A109129, A276625 (positions of 1's), A282446, A304117, A318046, A328880.

a:= proc(n) option remember;
      mul(a(numtheory[pi](i[1]))*i[2], i=ifactors(n)[2])
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Mar 13 2020

a[1] = 1; a[n_] := a[n] = Times @@ (a[PrimePi[#[[1]]]] #[[2]] & /@ FactorInteger[n]); Table[a[n], {n, 1, 100}]

a(n) = A005361(n) * Product_{p|n, p prime} a(pi(p)).
a(n) = a(prime(n)).
a(p^k) = k * a(p), where p is prime.
a(A002110(n)) = Product_{k=1..n} a(k).

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

A318049 Number of first/rest balanced rooted plane trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333267 If n = Product (p_j^k_j) then a(n) = Product (a(pi(p_j)) * k_j), where pi = A000720.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula