A108521 -id:A108521 - cp's OEIS frontend

A108529 Number of asymmetric mobiles (cycle rooted trees) with n generators.

1, 1, 2, 5, 16, 51, 177, 621, 2246, 8245, 30783, 116257, 443945, 1710255, 6640939, 25961690, 102105115, 403701135, 1603721999, 6397931901, 25621989760, 102965680728, 415091909292, 1678226164646, 6803121058354, 27645628327636

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

Here CHK(A(x)) = 1 - Sum_{n>=1} (mu(n)/n)*log(1-A(x^n)), i.e., the constant 1 is included in the definition of the CHK transform. For other sequences that involve the CHK transform, the 1 is sometimes dropped; e.g., see sequence A032171. We have CHK(A(x)) = x + x^2 + 3*x^3 + 8*x^4 + 27*x^5 + 86*x^6 + 303*x^7 + 1065*x^8 + 3871*x^9 + ... - Petros Hadjicostas, Dec 05 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)
Index entries for sequences related to mobiles

Cf. A108521, A108522, A108523, A108524, A108525, A108527, A108528, A032171.

CHK(p,n)={sum(d=1, n, moebius(d)/d*log(subst(1/(1+O(x*x^(n\d))-p), x, x^d)))}
seq(n)={my(p=x); for(n=2, n, p += x^n*polcoef(x*p + CHK(p, n), n)); Vecrev(p/x)} \\ Andrew Howroyd, Aug 31 2018

G.f. satisfies: (2-x)*A(x) = x - 1 + CHK(A(x)).
From Petros Hadjicostas, Dec 05 2017: (Start)
a(n) = (1/2)*(a(n-1) + (1/n)*Sum_{d|n} mu(d)*c(n/d)) for n>=2, where c(n) = n*a(n) + Sum_{s=1..n-1} c(s)*a(n-s) and a(1) = c(1) = 1.
The g.f. satisfies (2-x)*A(x) = x - Sum_{n>=1} (mu(n)/n)*log(1-A(x^n)). (This is just a rephrasing of C. Bower's equation above.)
The auxiliary sequence (c(n): n>=1} has g.f. C(x) = Sum_{n>=1} c(n)*x^n = x*(dA/dx)/(1-A(x)) = x + 3*x^2 + 10*x^3 + 35*x^4 + 136*x^5 + 528*x^6 + 2122*x^7 + ...
(End)

A108524 Number of ordered rooted trees with n generators.

Original entry on oeis.org

1, 2, 7, 32, 166, 926, 5419, 32816, 203902, 1292612, 8327254, 54358280, 358769152, 2390130038, 16051344307, 108548774240, 738563388214, 5052324028508, 34727816264050, 239733805643552, 1661351898336676, 11553558997057772, 80603609263563262, 563972937201926432

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.
The Hankel transform of this sequence is 3^C(n+1,2). The Hankel transform of this sequence with 1 prepended (1,1,2,7,...) is 3^C(n,2). - Paul Barry, Jan 26 2011
a(n) is the number of Schroder paths of semilength n-1 in which the (2,0)-steps that are not on the horizontal axis come in 2 colors. Example: a(3)=7 because we have HH, UDUD, UUDD, HUD, UDH, UBD, and URD, where U=(1,1), H=(2,0), D=(1,-1), while B and R are, respectively, blue and red (2,0)-steps. - Emeric Deutsch, May 02 2011
Also the compositional inverse of A327767. - Peter Luschny, Oct 08 2022

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
Shishuo Fu, Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Index entries for sequences related to rooted trees

Cf. A108521-A108529, A108525, A000108, A001003, A327767.

# Using function CompInv from A357588.
CompInv(24, n -> [1, -2][irem(n-1, 2) + 1]); # Peter Luschny, Oct 08 2022

Rest[CoefficientList[Series[(Sqrt[4*x^2-8*x+1]-1)/(2*x-4), {x, 0, 20}], x]] (* Vaclav Kotesovec, Oct 18 2012 *)

a(n):=sum((i*binomial(n+1,i)*sum((-1)^j*2^(n-j)*binomial(n,j)*binomial(2*n-j-i-1,n-1),j,0,n-i))/2^i,i,1,n+1)/(n*(n+1)); /* Vladimir Kruchinin, May 10 2011 */

G.f.: (sqrt(4*x^2-8*x+1) - 1)/(2*x-4).
G.f.: 1/(1-x-x/(1-2x-x/(1-2x-x/(1-2x-x/(1-2x-x/(1-... (continued fraction). - Paul Barry, Feb 10 2009
a(n) = sum(i=1..n+1, (i*C(n+1,i)*sum(j=0..n-i, (-1)^j*2^(n-j)*C(n,j)*C(2*n-j-i-1,n-1)))/2^i)/(n*(n+1)). - Vladimir Kruchinin, May 10 2011
From Gary W. Adamson, Jul 11 2011: (Start)
a(n) is upper left term in the following infinite square production matrix:
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  3, 3, 1, 1, 0, ...
  9, 9, 3, 1, 1, ...
  ...
where columns are (1, 1, 3, 9, 27, 81, ...) prefaced with (0,0,1,2,3,...) zeros. (End)
Conjecture: 2*n*a(n) +(24-17*n)*a(n-1) +4*(4*n-9)*a(n-2) +4*(3-n)*a(n-3)=0. - R. J. Mathar, Nov 14 2011
G.f.: A(x)=(sqrt(4*x^2-8*x+1) - 1)/x/(2*x-4) = 1/(G(0)-x); G(k) = 1 + 2*x - 3*x/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ 3^(1/4)*(3^(3/2)-5)*(4+2*sqrt(3))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 18 2012
From Peter Bala, Mar 13 2015: (Start)
The o.g.f. A(x) satisfies the differential equation (2 - 17*x + 16*x^2 - 4*x^3)A'(x) + (7 - 4*x)*A(x) = 2 - 2*x. Mathar's conjectural recurrence above follows from this.
The o.g.f. A(x) is the series reversion of the rational function x*(1 - 2*x)/(1 - x^2). (End)

A108522 Number of increasing rooted trees with n generators.

Original entry on oeis.org

1, 2, 9, 70, 771, 10948, 190205, 3907494, 92654059, 2490459468, 74827519077, 2485153213814, 90403692195179, 3574835773247140, 152675377606343901, 7003761877546096278, 343454890456254782203, 17929588055863943650988

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.

Vaclav Kotesovec, Table of n, a(n) for n = 1..250
Index entries for sequences related to rooted trees

Cf. A108521-A108529, A007151, A001147.

{a(n)=local(A=x);for(i=1,n,A=intformal((1+A)/(2-exp(A+x*O(x^n)))) );n!*polcoeff(A,n)}
for(n=1,20,print1(a(n),", ")) \\ Paul D. Hanna, Mar 29 2014

E.g.f. satisfies: 2*A(x) = x - 1 + exp(A(x)) + Integral A(x) dx. - corrected by Vaclav Kotesovec and Paul D. Hanna, Mar 29 2014
From Paul D. Hanna, Mar 29 2014: (Start)
E.g.f. satisfies: A(x) = A'(x)*(2 - exp(A(x))) - 1.
E.g.f. satisfies: A'(x) = (1 + A(x))/(2 - exp(A(x))).
(End)
a(n) ~ c * n^(n-1) / (exp(n) * r^n), where r = 0.3160173586544089316502903103262192204293322854083... and c = 0.51723490785798357350192800634304... - Vaclav Kotesovec, Mar 29 2014

A007151 Number of planted evolutionary trees of magnitude n.

Original entry on oeis.org

1, 3, 19, 198, 2906, 55018, 1275030, 34947664, 1105740320, 39661089864, 1590232358584, 70482038536880, 3421732373367504, 180574681050278960, 10292371442183694832, 630125771602386523392, 41239934114630205030656

Offset: 1

Robert W. Robinson

Also number of labeled rooted trees with n generators. (A generator is a leaf or a node with just one child.) - Christian G. Bower, Jun 07 2005

L. R. Foulds and R. W. Robinson, Counting certain classes of evolutionary trees with singleton labels, Congress. Num., 44 (1984), 65-88.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..360
L. R. Foulds and R. W. Robinson, Counting certain classes of evolutionary trees with singleton labels, Congress. Num., 44 (1984), 65-88. (Annotated scanned copy)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A007152, A108521, A108522, A000169, A000311.

A007151 := proc(n)
    local k,j,i,m ,a;
    if n =1 then
        1;
    else
        a := 0 ;
        for k from 1 to n-1 do
        for j from 1 to k do
        for i from 0 to n-1 do
        for m from 0 to j do
             a := a+(n+k-1)! /(k-j)! *binomial(j+i-1,j-1) *2^m *(-1)^(m+i) *combinat[stirling2](n-m+j-i-1,j-m) / m! /(n-m+j-i-1)! ;
        end do:
        end do:
        end do:
        end do:
        a ;
    end if;
end proc:
seq(A007151(n),n=1..10) ; # R. J. Mathar, Mar 19 2018

Rest[CoefficientList[InverseSeries[Series[(1 - E^x + 2*x)/(1 + x),{x,0,20}],x],x] * Range[0,20]!] (* Vaclav Kotesovec, Jan 08 2014 *)

a(n):=if n=1 then 1 else (sum((n+k-1)!*sum(1/((k-j)!)*sum(binomial(j+i-1,j-1)*sum((2^m*(-1)^(m+i)*stirling2(n-m+j-i-1,j-m))/(m!*(n-m+j-i-1)!),m,0,j),i,0,n-1),j,1,k),k,1,n-1)); /* Vladimir Kruchinin, Aug 07 2012 */

for(n=1,20, print1(if(n==1,1,sum(k=1,n-1, (n+k-1)!*sum(j=1,k, (1/(k-j)!)* sum(i=0,n-1, binomial(j+i-1,j-1)*sum(m=0,j, 2^m*(-1)^(m+i)* stirling(n-m+j-i-1,j-m,2)/(m!*(n-m+j-i-1)!)))))), ", ")) \\ G. C. Greubel, Nov 26 2017

E.g.f. satisfies (2-x)*A(x) = x - 1 + exp(A(x)). - Christian G. Bower, Jun 07 2005
a(n) = Sum_{k=1..(n-1)} (n+k-1)!*Sum_{j=1..k} (1/(k-j)!)*Sum_{i=0..(n-1)} binomial(j+i-1,j-1)*Sum_{m=0..j} 2^m*(-1)^(m+i)*Stirling2(n-m+j-i-1,j-m)/(m!*(n-m+j-i-1)!), n>1, a(1)=1. - Vladimir Kruchinin, Aug 07 2012
a(n) ~ sqrt(LambertW(1)+1) * n^(n-1) * (LambertW(1))^n / (exp(n) * (2*LambertW(1)-1)^(n-1/2)). - Vaclav Kotesovec, Jan 08 2014

A108525 Number of increasing ordered rooted trees with n generators.

Original entry on oeis.org

1, 3, 27, 429, 9609, 277107, 9772803, 407452221, 19604840481, 1069202914083, 65177482634667, 4391636680582029, 324102772814580729, 25999541378465556627, 2252597527900572815763, 209625760563134613131421

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.

Vaclav Kotesovec, Table of n, a(n) for n = 1..200
Index entries for sequences related to rooted trees

Cf. A108521-A108529, A001147.

Rest[CoefficientList[InverseSeries[Series[(Log[1-x]+7*Log[1+x]+2/(x-1))/4+1/2,{x,0,20}],x],x]*Range[0,20]!] (* Vaclav Kotesovec, Feb 20 2014 *)

{a(n)=local(A=x); for(i=1, n, A=intformal((A-1)^2 * (1+A) /(1 - 4*A + 2*A^2)+O(x^n))); n!*polcoeff(A, n)};
for(n=1, 20, print1(a(n), ", ")); /* Vaclav Kotesovec, Feb 20 2014 */

E.g.f. satisfies: A(x) = -1 + 2*A'(x) - A'(x)/(1-A(x))^2, corrected by Vaclav Kotesovec and Paul D. Hanna, Feb 20 2014
A(x) = Series_Reversion( (log(1-x) + 7*log(1+x) + 2/(x-1))/4 + 1/2). - Vaclav Kotesovec, Feb 20 2014
a(n) ~ sqrt(4-sqrt(2)) * 2^(3*n-13/4) * n^(n-1) / (exp(n) * (4-4*sqrt(2)-log(2)+14*log(2-1/sqrt(2)))^(n-1/2)). - Vaclav Kotesovec, Feb 20 2014

A108523 Number of rooted identity trees with n generators.

Original entry on oeis.org

1, 1, 2, 4, 10, 27, 77, 226, 685, 2112, 6618, 20996, 67337, 217884, 710571, 2332958, 7705429, 25584035, 85346018, 285908169, 961440343, 3244259406, 10981797187, 37280278698, 126890974820, 432950169885, 1480542159038, 5073504809660

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

Andrew Howroyd, Table of n, a(n) for n = 1..200
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A108521-A108529, A004111.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(n)={my(v=[1]); for(n=2, n, v=concat(v, v[#v] + WeighT(concat(v,[0]))[n])); v}  \\ Andrew Howroyd, Aug 31 2018

G.f. satisfies (2-x)*A(x) = x - 1 + WEIGH(A(x)).

A108527 Number of labeled mobiles (cycle rooted trees) with n generators.

Original entry on oeis.org

1, 3, 20, 229, 3764, 80383, 2107412, 65436033, 2347211812, 95492023811, 4344109422388, 218499395486909, 12039757564700644, 721239945304498215, 46669064731537444820, 3243864647191662324601, 241046155271316751794596

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

Vaclav Kotesovec, Table of n, a(n) for n = 1..250
Index entries for sequences related to mobiles

Cf. A108521-A108529, A038037, A032188.

nmax=20; c[0]=0; A[x_]:=Sum[c[k]*x^k/k!,{k,0,nmax}]; Array[c,nmax]/.Solve[Rest[CoefficientList[Series[x-1-Log[1-A[x]]-(2-x)*A[x],{x,0,nmax}],x]]==0][[1]] (* Vaclav Kotesovec, Mar 28 2014 *)

{a(n)=local(A=x+O(x^n)); for(i=0, n, A=intformal((1-A^2)/(1-x-2*A+x*A)+O(x^n))); n!*polcoeff(A, n)}
for(n=1, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Mar 28 2014

E.g.f. satisfies: (2-x)*A(x) = x - 1 - log(1-A(x)).

a(n) ~ c * n^(n-1) / (exp(n) * r^n), where r = 0.20846306198165450115960050053484328028... and c = 0.3060161306524907981116283162103879... - Vaclav Kotesovec, Mar 28 2014

A108526 Number of mobiles (cycle rooted trees) with n generators.

Original entry on oeis.org

1, 2, 5, 16, 54, 210, 841, 3555, 15402, 68336, 308206, 1410175, 6525500, 30492934, 143669529, 681781043, 3255653089, 15632422715, 75429279214, 365556955492, 1778608580060, 8684658137204, 42543288504844, 209022441144144

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

A generator is a leaf or a node with just one child.

Andrew Howroyd, Table of n, a(n) for n = 1..200
C. G. Bower, Transforms (2)
Index entries for sequences related to mobiles

Cf. A108521-A108529, A032200, A032203.

CIK(p,n)={sum(d=1, n, eulerphi(d)/d*log(subst(1/(1+O(x*x^(n\d))-p), x, x^d)))}
seq(n)={my(p=x); for(n=2, n, p += x^n*polcoef(x*p + CIK(p, n), n)); Vecrev(p/x)} \\ Andrew Howroyd, Aug 31 2018

G.f. satisfies (2-x)*A(x) = x - 1 + CIK(A(x)).

A108528 Number of increasing mobiles (cycle rooted trees) with n generators.

Original entry on oeis.org

1, 2, 10, 92, 1216, 20792, 435520, 10793792, 308874016, 10021509632, 363509706880, 14576530558592, 640275236943616, 30573223563625472, 1576805482203235840, 87353392124392020992, 5173324070004374358016, 326160898887563325581312, 21810458629345555407462400

Offset: 1

Christian G. Bower, Jun 07 2005

nonn

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Index entries for sequences related to mobiles

Cf. A108521, A108522, A108523, A108524, A108525, A108526, A108527, A108528, A108529, A029768.

Rest[CoefficientList[InverseSeries[Series[Log[(1+x)*Sqrt[1-x^2]], {x, 0, 20}], x],x] * Range[0, 20]!] (* Vaclav Kotesovec, Jan 08 2014 *)

{a(n)=n!*polcoeff(serreverse(log((1+x)*sqrt(1-x^2+O(x^(n+2))))),n)} \\ Paul D. Hanna, Sep 11 2010

E.g.f. satisfies 2*A(x) = x - 1 + A'(x) - log(1-A(x)).
From Paul D. Hanna, Sep 11 2010: (Start)
E.g.f. satisfies: (1+A(x))*sqrt(1-A(x)^2) = exp(x).
E.g.f.: A(x) = Series_Reversion[ log((1+x)*sqrt(1-x^2)) ]. (End)
a(n) ~ 2^(n-2) * sqrt(3) * n^(n-1) / (exp(n) * (log(27/16))^(n-1/2)). - Vaclav Kotesovec, Jan 08 2014

A335342 Number of free trees with exactly n nodes with fewer than three neighbors.

Original entry on oeis.org

1, 1, 2, 4, 9, 25, 70, 226, 753, 2675, 9785, 37087, 143487, 566952, 2274967, 9257906, 38113299, 158535204, 665364565, 2814924441, 11993967450, 51433198599, 221839745468, 961884808879, 4190783204515, 18339291329225

Offset: 1

Robert A. Russell, Jun 02 2020

Generates and uses values from A108521, rooted trees with exactly n generators, a generator being a leaf or node with just one child.

			For n=4, we have 1) a node with four neighbors, 2) two adjacent nodes with three neighbors each, 3) two adjacent nodes with two neighbors each, and 4) two adjacent nodes, one having two neighbors and the other three neighbors.

Robert A. Russell, Table of n, a(n) for n = 1..60
R. A. Russell, How many trees have n nodes with fewer than three neighbors?, MathOverflow, June 2020.

Cf. A108521 (rooted trees).

a[1] = 1; a[n_] := a[n] = 1+a[n-1] + Total[Product[Binomial[a[i]-1+Count[#,i], Count[#,i]], {i, DeleteCases[DeleteDuplicates[#], 1]}] & /@ IntegerPartitions[n,{2, n-1}]]; (* A108521 *)
b[1] = 1; b[n_] := b[n] = If[n > 2, 1, 0] + If[EvenQ[n], a[n/2] (a[n/2] + 1)/2, a[(n-1)/2] (a[(n-1)/2]+1)/2] + If[n > 3, Total[If[Max[#] <= If[EvenQ[n], n/2-1, (n-1)/2], Product[Binomial[a[i] - 1 + Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}], 0] & /@ IntegerPartitions[n, {3, n-1}]], 0];
Table[b[n], {n, 40}]
(* a[n] = A108521[n]; d[n] are coefficients of A^2(x) in g.f. *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n-1] + (DivisorSum[n, a[#] # &, #

\\ here S is A108521 as vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
S(n)={my(v=[1]); for(n=2, n, v=concat(v, v[#v] + EulerT(concat(v, [0]))[n])); v}
seq(n)={my(p=x*Ser(S(n))); Vec(p + (x/2-1)*p^2 + (x/2)*subst(p, x, x^2))} \\ Andrew Howroyd, Jun 06 2020

G.f.: A(x) + (x/2-1)*A^2(x) + (x/2)*A(x^2), where A(x) is the g.f. for A108521.

cp's OEIS Frontend

A108529 Number of asymmetric mobiles (cycle rooted trees) with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A108524 Number of ordered rooted trees with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A108522 Number of increasing rooted trees with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A007151 Number of planted evolutionary trees of magnitude n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

A108525 Number of increasing ordered rooted trees with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A108523 Number of rooted identity trees with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A108527 Number of labeled mobiles (cycle rooted trees) with n generators.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A108526 Number of mobiles (cycle rooted trees) with n generators.