A007853 -id:A007853 - cp's OEIS frontend

A317852 Number of plane trees with n nodes where the sequence of branches directly under any given node is aperiodic, meaning its cyclic permutations are all different.

1, 1, 1, 3, 8, 26, 76, 247, 783, 2565, 8447, 28256, 95168, 323720, 1108415, 3821144, 13246307, 46158480, 161574043, 567925140, 2003653016, 7092953340, 25186731980, 89690452750, 320221033370, 1146028762599, 4110596336036, 14774346783745, 53203889807764, 191934931634880

Offset: 1

Gus Wiseman, Sep 05 2018

nonn

Also the number of plane trees with n nodes where the sequence of branches directly under any given node has relatively prime run-lengths.

			The a(5) = 8 locally aperiodic plane trees:
  ((((o)))),
  (((o)o)), ((o(o))), (((o))o), (o((o))),
  ((o)oo), (o(o)o), (oo(o)).
The a(6) = 26 locally aperiodic plane trees:
  (((((o)))))  ((((o)o)))  (((o)oo))  ((o)ooo)
               (((o(o))))  ((o(o)o))  (o(o)oo)
               ((((o))o))  ((oo(o)))  (oo(o)o)
               ((o((o))))  (((o)o)o)  (ooo(o))
               ((((o)))o)  ((o(o))o)
               (o(((o))))  (o((o)o))
               (((o))(o))  (o(o(o)))
               ((o)((o)))  (((o))oo)
                           (o((o))o)
                           (oo((o)))
                           ((o)(o)o)
                           ((o)o(o))
                           (o(o)(o))

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

Cf. A000108, A000837, A007853, A032171, A032200, A254040, A301700, A303386, A303431, A304173, A304175, A317708, A317852.

aperQ[q_]:=Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
aperplane[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[aperplane/@c],aperQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[aperplane[n]],{n,10}]

Tfm(p, n)={sum(d=1, n, moebius(d)*(subst(1/(1+O(x*x^(n\d))-p), x, x^d)-1))}
seq(n)={my(p=O(1)); for(i=1, n, p=1+Tfm(x*p, i)); Vec(p)} \\ Andrew Howroyd, Feb 08 2020

a(16)-a(17) from Robert Price, Sep 15 2018

Terms a(18) and beyond from Andrew Howroyd, Feb 08 2020

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 5, 4, 5, 3, 4, 3, 7, 2, 4, 5, 3, 4, 5, 5, 6, 3, 10, 4, 9, 3, 5, 7, 6, 2, 9, 4, 7, 5, 4, 3, 7, 4, 5, 5, 4, 5, 13, 6, 8, 3, 5, 10, 7, 4, 3, 9, 13, 3, 5, 5, 5, 7, 6, 6, 9, 2, 10, 9, 4, 4, 11, 7, 5, 5, 6, 4, 19, 3, 9, 7, 6, 4, 17, 5, 7, 5

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

We require that an initial subtree contain either all or none of the branchings under any given node.

			70 is the Matula-Goebel number of the tree (o((o))(oo)), which has 7 distinct initial subtrees: {o, (ooo), (oo(oo)), (o(o)o), (o(o)(oo)), (o((o))o), (o((o))(oo))}. So a(70) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476, A317713.

si[n_]:=If[n==1,1,1+Product[si[PrimePi[b[[1]]]]^b[[2]],{b,FactorInteger[n]}]];
Array[si,100]

a(1) = 1 and if n > 1 has prime factorization n = prime(x_1)^y_1 * ... * prime(x_k)^y_k then a(n) = 1 + a(x_1)^y_1 * ... * a(x_k)^y_k.

A318153 Number of antichain covers of the free pure symmetric multifunction (with empty expressions allowed) with e-number n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Aug 19 2018

nonn

If n = 1 let e(n) be the leaf symbol "o". Given a positive integer n > 1 we construct a unique free pure symmetric multifunction (with empty expressions allowed) e(n) (as can be represented in functional programming languages such as Mathematica) with one atom by expressing n as a power of a number that is not a perfect power to a product of prime numbers: n = rad(x)^(prime(y_1) * ... * prime(y_k)) where rad = A007916. Then e(n) = e(x)[e(y_1), ..., e(y_k)]. For example, e(21025) = o[o[o]][o] because 21025 = rad(rad(1)^prime(rad(1)^prime(1)))^prime(1). The a(n) is the number of ways to partition e(n) into disjoint subexpressions such that all leaves are covered by exactly one of them.

			441 is the e-number of o[o,o][o] which has antichain covers {o[o,o][o]}, {o[o,o], o}, {o, o, o, o}}, corresponding to the leaf-colorings 1[1,1][1], 1[1,1][2], 1[2,3][4], so a(441) = 3.

Cf. A000081, A007853, A007916, A052409, A052410, A277576, A277996.

Cf. A317658, A316112, A317056, A317765, A317994, A318149, A318150, A318152.

nn=20000;
radQ[n_]:=If[n==1,False,GCD@@FactorInteger[n][[All,2]]==1];
rad[n_]:=rad[n]=If[n==0,1,NestWhile[#+1&,rad[n-1]+1,Not[radQ[#]]&]];
Clear[radPi];Set@@@Array[radPi[rad[#]]==#&,nn];
a[n_]:=If[n==1,1,With[{g=GCD@@FactorInteger[n][[All,2]]},1+a[radPi[n^(1/g)]]*Product[a[PrimePi[pr[[1]]]]^pr[[2]],{pr,If[g==1,{},FactorInteger[g]]}]]];
Array[a,100]

If n = rad(x)^(Product_i prime(y_i)^z_i) where rad = A007916 then a(n) = 1 + a(x) * Product_i a(y_i)^z_i.

A213705 a(n)=n if n <= 3, otherwise a(n) = A007477(n-1) + A007477(n).

Original entry on oeis.org

1, 2, 3, 5, 9, 17, 33, 66, 134, 277, 579, 1224, 2610, 5609, 12135, 26408, 57770, 126962, 280192, 620674, 1379586, 3075943, 6877611, 15417934, 34646156, 78027146, 176087292, 398143230, 901827322, 2046112299, 4649558191, 10581041518, 24112473412, 55019560650, 125696393844, 287494670302

Offset: 1

Antti Karttunen, Sep 14 2012

a(n) gives the number of "plausible parsings" of the sentence "Etsivät^(n+1)" in Finnish (with the most common word order, SV & SVO), that is, sentences which consist only of n+1 copies of the word "etsivät". See the OEIS Wiki page.
See A007477 for the number of plausible parsings of "Buffalo^n" sentences in English.
In my view the value of a(0) should be 0 in this context (single word "Etsivät." is not a valid Finnish sentence, except as an answer to a question), although this is arguable. However, it is probably that this sequence occurs in other (combinatorial) contexts as well, and there a(0) might be something else than 0, so I left it off, and made the sequence start from offset 1.

			G.f. = x + 2*x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 17*x^6 + 33*x^7 + ... - _Michael Somos_, Nov 07 2019

Antti Karttunen, Table of n, a(n) for n = 1..1000
Antti Karttunen, Etsivät etsivät etsivät..., OEIS Wiki.

Cf. A007477, A007853.

b:= n-> coeff(series(RootOf(A=(A*x)^2+x+1, A), x, n+1), x, n):
a:= n-> `if`(n<2, n, b(n-1) +b(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Sep 14 2012

(* b = A007477 *) b[n_] := Sum[Binomial[2*k+2, n-k-2]*Binomial[n-k-2, k]/(k + 1), {k, 0, n-2}]; a[n_] := b[n-1] + b[n]; a[1] = 1; a[2] = 2; Array[a, 40] (* Jean-François Alcover, Mar 04 2016 *)

b(n) = sum(k=0, n - 2, binomial(2*k + 2, n - k - 2)*binomial(n - k - 2, k)/(k + 1));
a(n) = if(n<3, n, b(n - 1) + b(n)); \\ Indranil Ghosh, Apr 11 2017

{a(n) = polcoeff( (1 + x) * (1 - 2*x^2 - sqrt(1 - 4*x^2 - 4*x^3 + x^3 * O(x^n))) / (2*x^2), n)}; /* Michael Somos, Nov 07 2019 */

from sympy import binomial
def b(n): return sum([binomial(2*k + 2, n - k - 2)*binomial(n - k - 2, k)//(k + 1) for k in range(n - 1)])
def a(n): return n if n<3 else b(n - 1) + b(n)
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Apr 11 2017

: (define (A213705 n) (if (< n 2) n (+ (A007477 (- n 1)) (A007477 n))))

Given the g.f. A(x) and the g.f. of A007853 B(x), then -x = A(-B(x)). - Michael Somos, Nov 07 2019

A319123 Number of series-reduced plane trees with n leaves such that each branch directly under any given node has a different number of leaves.

Original entry on oeis.org

1, 1, 3, 7, 21, 75, 277, 1083, 4419, 18493, 77729, 332557, 1444477, 6307225, 27912147, 123878207, 554733045, 2492087531, 11280537097, 51120499279, 233319480419, 1065835004917, 4895443823281, 22505853359485, 103958158302085, 480365303903637, 2229412587062123

Offset: 1

Gus Wiseman, Sep 11 2018

nonn

			The a(4) = 7 plane trees:
  (oooo)
  (o(ooo))
  ((ooo)o)
  (o(o(oo)))
  (o((oo)o))
  ((o(oo))o)
  (((oo)o)o)

Cf. A000108, A001003, A007853, A074206, A118376, A273873, A277130, A281113, A304173, A304175, A319122.

b[n_]:=b[n]=1+Sum[Times@@b/@f,{f,Join@@Permutations/@Select[IntegerPartitions[n],And[Length[#]>1,UnsameQ@@#]&]}];
Array[b,30]

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}]

cp's OEIS Frontend

A317852 Number of plane trees with n nodes where the sequence of branches directly under any given node is aperiodic, meaning its cyclic permutations are all different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A318153 Number of antichain covers of the free pure symmetric multifunction (with empty expressions allowed) with e-number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A213705 a(n)=n if n <= 3, otherwise a(n) = A007477(n-1) + A007477(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

A319123 Number of series-reduced plane trees with n leaves such that each branch directly under any given node has a different number of leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica