A063895 -id:A063895 - cp's OEIS frontend

A339193 Matula-Goebel numbers of unlabeled binary rooted semi-identity trees.

1, 4, 14, 86, 301, 886, 3101, 3986, 13766, 13951, 19049, 48181, 57026, 75266, 85699, 199591, 263431, 295969, 298154, 302426, 426058, 882899

Offset: 1

Gus Wiseman, Mar 14 2021

nonn

Definition: A positive integer belongs to the sequence iff it is 1, 4, or a squarefree semiprime whose prime indices both already belong to the sequence. A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
In a semi-identity tree, only the non-leaf branches of any given vertex are distinct. Alternatively, a rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.
The Matula-Goebel number of an unlabeled rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of terms together with the corresponding unlabeled rooted trees begins:
      1: o
      4: (oo)
     14: (o(oo))
     86: (o(o(oo)))
    301: ((oo)(o(oo)))
    886: (o(o(o(oo))))
   3101: ((oo)(o(o(oo))))
   3986: (o((oo)(o(oo))))
  13766: (o(o(o(o(oo)))))
  13951: ((oo)((oo)(o(oo))))
  19049: ((o(oo))(o(o(oo))))
  48181: ((oo)(o(o(o(oo)))))
  57026: (o((oo)(o(o(oo)))))
  75266: (o(o((oo)(o(oo)))))
  85699: ((o(oo))((oo)(o(oo))))

Gus Wiseman, The sequence of all unlabeled binary rooted semi-identity trees by Matula-Goebel number.

Counting these trees by number of nodes gives A063895.
A000081 counts unlabeled rooted trees with n nodes.
A111299 ranks binary trees, counted by A001190.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A007097, A061775, A196050, A291636, A331963, A331964.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
mgbiQ[n_]:=Or[n==1,n==4,SquareFreeQ[n]&&PrimeOmega[n]==2&&And@@mgbiQ/@primeMS[n]];
Select[Range[1000],mgbiQ]

A116379 Number of ternary rooted identity (distinct subtrees) trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 245, 542, 1205, 2707, 6113, 13907, 31780, 73010, 168399, 389991, 906231, 2112742, 4939689, 11580640, 27216387, 64110091, 151334814, 357938832, 848153045, 2013190671, 4786210412, 11396004660, 27172368314, 64875527649

Offset: 1

Karen A. Yeats, Feb 06 2006

nonn

It is not known if these trees have the asymptotic form C rho^{-n} n^{-3/2}, whereas the identity binary trees, A063895, do, see the Jason P. Bell et al. reference.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Jason P. Bell, Stanley N. Burris and Karen A. Yeats, Counting Rooted Trees: The Universal Law t(n) ~ C rho^{-n} n^{-3/2}, arXiv:math/0512432 [math.CO], 2005-2006.

Cf. A004111, A063895, A116380.

#include  using namespace GiNaC; int main(){ int i, order = 40; symbol x("x"); ex T = x; for (i=0; i

A:= proc(n) option remember; local T; if n<=1 then x else T:= unapply(A(n-1), x); convert(series(x* (1+T(x)+ T(x)^2/2- T(x^2)/2+ T(x)^3/6- T(x)*T(x^2)/2+ T(x^3)/3), x, n+1), polynom) fi end: a:= n-> coeff(A(n), x, n): seq(a(n), n=1..40);  # Alois P. Heinz, Aug 22 2008

A[n_] := A[n] = If[n <= 1, x, T[y_] = A[n-1] /. x -> y; Normal[Series[y*(1+T[y]+T[y]^2/2-T[y^2]/2+T[y]^3/6-T[y]*T[y^2]/2+T[y^3]/3), {y, 0, n+1}]] /. y -> x] ; a[n_] := Coefficient[A[n], x, n]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 13 2014, after Maple *)

G.f. satisfies: A(x) = x(1+A(x)+A(x)^2/2-A(x^2)/2+A(x)^3/6-A(x)A(x^2)/2+A(x^3)/3), that is A(x) = x(1+Set_{<=3}(A)(x)).

A064067 n-th step is to add a(n) to each previous number a(k) (excluding itself, i.e., k < n) to produce n more terms of the sequence, starting with a(0)=1, a(1)=2.

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Aug 31 2001

nonn

			Start with (1,2). So after initial step have (1, *2*, 1+2 = 3), then (1, 2, *3*, 1+3 = 4, 2+3 = 5), then (1, 2, 3, *4*, 5, 1+4 = 5, 2+4 = 6, 3+4 = 7), then (1, 2, 3, 4, *5*, 5, 6, 7, 1+5 = 6, 2+5 = 7, 3+5 = 8, 4+5 = 9), etc.

Each positive number appears A063895 number of times.

Cf. A064064, A064065, A064066.

A116380 Number of quaternary rooted identity (distinct subtrees) trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6298, 14419, 33183, 76760, 178327, 415960, 973693, 2286781, 5386573, 12723097, 30127465, 71506140, 170081575, 405359177, 967899981, 2315131955, 5546597838, 13308818691, 31979667219, 76947325788

Offset: 1

Karen A. Yeats, Feb 06 2006

nonn

It is not known if these trees have the asymptotic form C rho^{-n} n^{-3/2}, whereas the identity binary trees, A063895, do, see the Jason P. Bell et al. reference.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Jason P. Bell, Stanley N. Burris and Karen A. Yeats, Counting Rooted Trees: The Universal Law t(n) ~ C rho^{-n} n^{-3/2}, arXiv:math/0512432 [math.CO], 2005-2006.

Cf. A004111, A063895, A116379.

#include  using namespace GiNaC; int main(){ int i, order=40; symbol x("x"); ex T; for (i=0; i

A:= proc(n) option remember; local T; if n<=1 then x else T:= unapply(A(n-1), x); convert(series(x* (1+T(x)+ T(x)^2/2- T(x^2)/2+ T(x)^3/6- T(x)*T(x^2)/2+ T(x^3)/3+ T(x)^4/24- T(x)^2* T(x^2)/4+ T(x)* T(x^3)/3+ T(x^2)^2/8- T(x^4)/4), x,n+1), polynom) fi end: a:= n-> coeff(A(n),x,n): seq(a(n), n=1..40); # Alois P. Heinz, Aug 22 2008

A[n_] := A[n] = If[n <= 1, x, T[y_] = A[n-1] /. x -> y; Normal[Series[y*(1+T[y]+T[y]^2/2-T[y^2]/2+T[y]^3/6-T[y]*T[y^2]/2+T[y^3]/3+T[y]^4/24-T[y]^2*T[y^2]/4+T[y]*T[y^3]/3+T[y^2]^2/8-T[y^4]/4), {y, 0, n+1}]] /. y -> x]; a[n_] := Coefficient[A[n], x, n]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 13 2014, after Maple *)

G.f. satisfies: A(x) = x(1 + A(x) + A(x)^2/2-A(x^2)/2 + A(x)^3/6-A(x)A(x^2)/2+A(x^3)/3 + A(x)^4/24-A(x)^2A(x^2)/4+A(x)A(x^3)/3+A(x^2)^2/8-A(x^4)/4), that is A(x) = x(1+Set_{<=4}(A)(x)).

A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.

Original entry on oeis.org

1, 1, 2, 4, 12, 34, 108, 344, 1136, 3796, 12920, 44442, 154596, 542336, 1917648, 6825464, 24439008, 87962312, 318087216, 1155090092, 4210494616, 15400782912, 56508464736, 207935588586, 767162495940, 2837260332472, 10516827106016, 39063666532784, 145378611426512

Offset: 1

Gus Wiseman, May 05 2021

nonn

In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 12 trees:
  o  (oo)  ((oo)o)  (((oo)o)o)  ((((oo)o)o)o)
           (o(oo))  ((o(oo))o)  (((o(oo))o)o)
                    (o((oo)o))  (((oo)o)(oo))
                    (o(o(oo)))  ((o((oo)o))o)
                                ((o(o(oo)))o)
                                ((o(oo))(oo))
                                ((oo)((oo)o))
                                ((oo)(o(oo)))
                                (o(((oo)o)o))
                                (o((o(oo))o))
                                (o(o((oo)o)))
                                (o(o(o(oo))))

Andrew Howroyd, Table of n, a(n) for n = 1..500
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Samuele Giraudo, Mockingbird lattices, Séminaire Lotharingien de Combinatoire XX, Proceedings of the 34th Conf. on Formal Power, Series and Algebraic Combinatorics (Bangalore, India, 2022).

The not necessarily semi-identity version is A000108.
The non-plane version is A063895, ranked by A339193.
The Matula-Goebel numbers in the non-plane case are A339193.
The not-necessarily binary version is A343937.
A000081 counts unlabeled rooted trees with n nodes.
2*A001190 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
A004111 counts identity trees, ranked by A276625.
A306200 counts semi-identity trees, ranked by A306202.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A320230, A331934, A331963, A331964.

crsiq[n_]:=Join@@Table[Select[Union[Tuples[crsiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[crsiq[n]],{n,1,11,2}]
(* Second program: *)
m = 29; p[_] = 1;
Do[p[x_] = 1 + x + x (p[x]^2 - p[x^2]) + O[x]^m // Normal, {m}];
CoefficientList[p[x], x] (* Jean-François Alcover, May 09 2021, after Andrew Howroyd *)

seq(n)={my(p=O(1)); for(n=1, n, p=1 + x + x*(p^2-subst(p,x,x^2))); Vec(p)} \\ Andrew Howroyd, May 07 2021

G.f.: x*A(x) where A(x) satisfies A(x) = 1 + x + x*(A(x)^2 - A(x^2)). - Andrew Howroyd, May 07 2021

Terms a(13) and beyond from Andrew Howroyd, May 07 2021

A063894 Start with x, y; then concatenate each word in turn with all preceding words, getting x y xy xxy yxy xxxy yxxy xyxxy ...; sequence gives number of words of length n. Also binary trees by degree: x y (x,y) (x,(x,y)) (y,(x,y)) (x,(x,(x,y))) (y,(x,(x,y))) ((x,y),(x,(x,y)))...

Original entry on oeis.org

2, 1, 2, 4, 10, 25, 68, 187, 532, 1532, 4492, 13308, 39870, 120433, 366656, 1123504, 3463050, 10729234, 33396202, 104381385, 327477814, 1030903514, 3255394686, 10309154738, 32732315724, 104177891232, 332308237666, 1062192108053

Offset: 1

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

Cf. A063895.

a[1] = 2; a[n_] := a[n] = Sum[a[k]*a[n-k], {k, 1, Floor[(n-1)/2]}] + If[EvenQ[n], (a[n/2]-1)*a[n/2]/2, 0]; Table[a[n], {n, 1, 28}] (* Jean-François Alcover, Feb 20 2012, from formula *)

a(n)=local(A,m); if(n<0,0,m=1; A=O(x); while(m<=n,m*=2; A=1-sqrt(1-4*x+subst(A,x,x^2))); polcoeff(A,n))

G.f. A(x)=1-sqrt(1-4x+A(x^2)) satisfies A(x)^2-2A(x)+4x-A(x^2)=0, A(0)=0. - Michael Somos, Sep 06 2003

a(n)=(sum a(i)a(j), i+j=n, i1. a(1)=2.

A245747 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 2.

Original entry on oeis.org

1, 2, 5, 10, 21, 42, 87, 178, 371, 773, 1630, 3447, 7346, 15712, 33790, 72922, 158020, 343494, 749101, 1638102, 3591723, 7893801, 17387930, 38379199, 84875595, 188036829, 417284180, 927469844, 2064465340, 4601670624, 10270463564, 22950838754, 51346678940

Offset: 4

Joerg Arndt and Alois P. Heinz, Jul 31 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Column k=2 of A244523.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 2$2) -b(n-1$2, 1$2):
seq(a(n), n=4..60);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[ b[i-1, i-1, k, k], j]*b[n-i*j, i-1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] :=  b[n-1, n-1, 2, 2] - b[n-1, n-1, 1, 1];
Table[a[n], {n, 4, 60}] (* Jean-François Alcover, Aug 28 2021, after Maple code *)

a(n) = A063895(n+1)-1.

A245748 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 3.

Original entry on oeis.org

1, 3, 9, 25, 66, 170, 431, 1076, 2665, 6560, 16067, 39219, 95476, 231970, 562736, 1363640, 3301586, 7988916, 19322585, 46722160, 112955614, 273063236, 660116215, 1595906490, 3858740567, 9331539319, 22570697689, 54605064084, 132137719127, 319841444030

Offset: 7

Joerg Arndt and Alois P. Heinz, Jul 31 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..1000

Column k=3 of A244523.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b(i-1$2, k$2), j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> b(n-1$2, 3$2) -b(n-1$2, 2$2):
seq(a(n), n=7..60);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[ b[i-1, i-1, k, k], j]*b[n - i*j, i-1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := b[n-1, n-1, 3, 3] - b[n-1, n-1, 2, 2];
Table[a[n], {n, 7, 60}] (* Jean-François Alcover, Aug 28 2021, after Maple code *)

a(n) = A116379(n) - A063895(n+1).

A343937 Number of unlabeled semi-identity plane trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 38, 117, 375, 1224, 4095, 13925, 48006, 167259, 588189, 2084948, 7442125, 26725125, 96485782, 350002509, 1275061385, 4662936808, 17111964241, 62996437297, 232589316700, 861028450579, 3195272504259, 11884475937910, 44295733523881, 165420418500155

Offset: 1

Gus Wiseman, May 07 2021

nonn

In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 13 trees are the following. The number of nodes is the number of o's plus the number of brackets (...).
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))

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

The not necessarily semi-identity version is A000108.
The non-plane binary version is A063895, ranked by A339193.
The non-plane version is A306200, ranked by A306202.
The binary case is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A001190*2 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
A004111 counts identity trees, ranked by A276625.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A320230, A331934, A331963, A331964.

arsiq[n_]:=Join@@Table[Select[Union[Tuples[arsiq/@ptn]],#=={}||(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[arsiq[n]],{n,10}]

F(p)={my(n=serprec(p,x)-1, q=exp(x*y + O(x*x^n))*prod(k=2, n, (1 + y*x^k + O(x*x^n))^polcoef(p,k,x)) ); sum(k=0, n, k!*polcoef(q,k,y))}
seq(n)={my(p=O(x)); for(n=1, n, p=x*F(p)); Vec(p)} \\ Andrew Howroyd, May 08 2021

G.f.: A(x) satisfies A(x) = x*Sum_{j>=0} j!*[y^j] exp(x*y - Sum_{k>=1} (-y)^k*(A(x^k) - x^k)/k). - Andrew Howroyd, May 08 2021

Terms a(17) and beyond from Andrew Howroyd, May 08 2021

cp's OEIS Frontend

A339193 Matula-Goebel numbers of unlabeled binary rooted semi-identity trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A116379 Number of ternary rooted identity (distinct subtrees) trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Maple

Mathematica

Formula

A064067 n-th step is to add a(n) to each previous number a(k) (excluding itself, i.e., k < n) to produce n more terms of the sequence, starting with a(0)=1, a(1)=2.

Views

Author

Keywords

Examples

Crossrefs

A116380 Number of quaternary rooted identity (distinct subtrees) trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Maple

Mathematica

Formula

A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A063894 Start with x, y; then concatenate each word in turn with all preceding words, getting x y xy xxy yxy xxxy yxxy xyxxy ...; sequence gives number of words of length n. Also binary trees by degree: x y (x,y) (x,(x,y)) (y,(x,y)) (x,(x,(x,y))) (y,(x,(x,y))) ((x,y),(x,(x,y)))...

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A245747 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A245748 Number of identity trees with n nodes where the maximal outdegree (branching factor) equals 3.

Views

Author

Keywords

Links

Crossrefs

Programs