A000055 -id:A000055 - cp's OEIS frontend

A157904 INVERT transform of A000055.

1, 2, 4, 8, 17, 36, 78, 170, 375, 833, 1870, 4229, 9654, 22223, 51622, 120961, 286029, 682398, 1642821, 3990231, 9777678, 24166327, 60233185, 151350709, 383287499, 977918150, 2512805727, 6500178867, 16921248231, 44310852884, 116678914575

Offset: 0

Gary W. Adamson, Mar 08 2009

nonn

Note that the correct INVERT transform of A000055 (recognizing the offsets) would be 1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1386,... - R. J. Mathar, Sep 20 2020

			a(3) = 8 = (1, 1, 1) dot (1, 2, 4) + 1 = 7 + 1 = 8; where the operation uses ascending terms of A000055: (1, 1, 1, 1, 2, 3, 6, 11,...) and an equal number of ongoing descending terms of A157904. Take the dot product and add to the next term of A000055. a(4) = 17 = (1, 1, 1, 1) dot (1, 2, 4, 8) + 2 = 15 + 2.

Alois P. Heinz, Table of n, a(n) for n = 0..700

Cf. A000055, A157905.

with(numtheory): b:= proc(n) option remember; local d, j; if n<=1 then n else (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1) fi end: t:= proc(n) option remember; local k; `if`(n=0, 1, b(n)- (add(b(k) *b(n-k), k=1..n-1) -`if`(type(n, odd), 0, b(n/2)))/2) end: a:= proc(n) option remember; local i; if n<=0 then 1 else add(t(i)*a(n-i-1),i=0..n) fi end: seq(a(n), n=0..35);  # Alois P. Heinz, Mar 31 2009

b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d b[d], {d, Divisors[j]}] b[n - j], {j, 1, n - 1}]/(n - 1)];
t[n_] := t[n] = If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 1, n - 1}] - If[OddQ[n], 0, b[n/2]])/2];
a[n_] := a[n] = If[n <= 0, 1, Sum[t[i] a[n - i - 1], {i, 0, n}]];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 22 2020, after Alois P. Heinz *)

INVERT transform of A000055: (1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106,...).

More terms from Alois P. Heinz, Mar 31 2009

A052471 Number of noncaterpillar trees on n nodes (A000055-A005418).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 3, 11, 34, 99, 279, 773, 2103, 5661, 15160, 40373, 107355, 285059, 757273, 2013177, 5361100, 14303274, 38250297, 102538714, 275597098, 742674804, 2006661720, 5436008057, 14763754746, 40196603110, 109703958381, 300091975184, 822705857129

Offset: 1

Eric W. Weisstein

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Caterpillar Graph

Cf. A000055, A005418.

with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= n-> b(n) -(add(b(k) *b(n-k), k=0..n)-`if`(irem(n, 2)=0,
        b(n/2), 0))/2 -ceil(2^(n-4) + 2^(iquo(n-2, 2)-1)):
seq(a(n), n=1..40); # Alois P. Heinz, May 18 2013

b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n-1}])/(n-1)]; a[n_] := b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[ Mod[n, 2] == 0, b[n/2], 0])/2 - Ceiling[2^(n-4) + 2^(Quotient[n-2, 2] - 1)]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Feb 19 2016, after Alois P. Heinz *)

a(14) and up from Eric W. Weisstein, Jul 17 2004.

A157905 Triangle read by rows, T(n,k) = A000055(n-k) * (A157904 * 0^(n-k)).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 4, 2, 1, 2, 4, 8, 3, 2, 2, 4, 8, 17, 6, 3, 4, 4, 8, 17, 36, 11, 6, 6, 8, 8, 17, 36, 78, 23, 11, 12, 12, 16, 17, 36, 78, 170, 47, 23, 22, 24, 24, 34, 36, 78, 170, 375, 106, 47, 46, 44, 48, 51, 72, 78, 170, 375, 833

Offset: 0

Gary W. Adamson, Mar 08 2009

As a property of eigentriangles, sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle =
    1;
    1,   1;
    1,   1,  2;
    1,   1,  2,  4;
    2,   1,  2,  4,  8;
    3,   2,  2,  4,  8,  17;
    6,   3,  4,  4,  8,  17,  36;
   11,   6,  6,  8,  8,  17,  36,  78;
   23,  11, 12, 12, 16,  17,  36,  78, 170;
   47,  23, 22, 24, 24,  34,  36,  78, 170, 375;
  106,  47, 46, 44, 48,  51,  72,  78, 170, 375, 833;
  235, 106, 94, 92, 88, 102, 108, 156, 170, 375, 833, 1870;
  ...
Row 5 = (3, 2, 2, 4, 8, 17) = termwise products of (3, 2, 1, 1, 1, 1) and (1, 1, 2, 4, 8, 17).

Cf. A000055 (first column), A157904 (row sums).

b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d b[d], {d, Divisors[j]}] b[n - j], {j, 1, n - 1}]/(n - 1)];
t[n_] := t[n] = If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 1, n - 1}] - If[OddQ[n], 0, b[n/2]])/2];
u[n_] := u[n] = If[n <= 0, 1, Sum[t[i] u[n - i - 1], {i, 0, n}]];
c[0] = 0; c[1] = 1; c[n_] := c[n] = Sum[d c[d] c[n - j], {j, 1, n - 1}, {d, Divisors[j]}]/(n - 1);
v[0] = 1; v[n_] := c[n] - (Sum[c[k] c[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, c[n/2], 0])/2;
T[n_, k_] := v[n - k] u[k - 1];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 21 2020, after Alois P. Heinz in A000055 and A157904 *)

Triangle read by rows, T(n,k) = A000055(n-k) * (A157904 * 0^(n-k)). A000055(n-k) = an infinite lower triangular matrix with A000055 in every column: (1, 1, 1, 1, 2, 3, 6, 11, 23, ...). (A157904 * 0^(n-k)) = a matrix with A157904 as the diagonal and the rest zeros.

A336042 Numbers k such that A000055(k) is divisible by k.

Original entry on oeis.org

1, 6, 90, 1031, 1099

Offset: 1

Vaclav Kotesovec, Jul 08 2020

No other terms below 40000.

			90 is in the sequence because A000055(90) = 90*179212383627255715871103677440244414

Cf. A000055, A051420, A119642, A336039.

A006790 Exponentiation of e.g.f. for trees A000055(n-1).

Original entry on oeis.org

1, 2, 5, 15, 53, 211, 938, 4582, 24349, 139671, 858745, 5628789, 39145021, 287667582, 2226033629, 18082308403, 153770703339, 1365631349757, 12638233544989, 121640399661294, 1215438543434225, 12587691428792115

Offset: 0

N. J. A. Sloane

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500
Index entries for sequences related to trees

Cf. A000055.

with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n, add(add(d*
      b(d), d=divisors(j))*b(n-j), j=1..n-1)/(n-1))
    end:
t:= proc(n) option remember; `if`(n=0, 1, b(n)-(add(b(k)
      *b(n-k), k=0..n)-`if`(irem(n, 2)=0, b(n/2), 0))/2)
    end:
g:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1) *t(j-1) *g(n-j), j=1..n))
    end:
a:= n-> g(n+1):
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 16 2015

b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]; t[n_] := t[n] = If[n==0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[ Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_] := g[n] = If[n==0, 1, Sum[Binomial[n-1, j-1] *t[j-1]*g[n-j], {j, 1, n}]]; a[n_] := g[n+1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

A083202 a(n) = gcd(A000055(n), A000055(n+1)).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 3, 15, 15, 1, 2, 1, 1, 10, 10, 92, 1, 1, 2, 1, 1, 1, 1, 6, 6, 2, 2, 57, 1, 1, 15, 3, 2, 2, 2, 5, 3, 6, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 12, 69, 69, 6, 186, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1

Offset: 0

Jon Perry, Jun 01 2003

nonn

			A000055(6)=6, A000055(7)=11, so a(6) = gcd(6,11) = 1.

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

Cf. A000055.

{v=[1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 4 8629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 2 79793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410]; for (i=1,length(v)-1,print1(gcd(v[i],v[i+1])","))}

More terms from Alois P. Heinz, Sep 26 2011

A119528 Determinant of n X n matrix of first n^2 number of trees with n unlabeled nodes (A000055).

Original entry on oeis.org

1, 0, 7, -7288, 210319661226, -28724163065553504725184, -17273218743083166095017987886925095168489136, -3262865955763797132157936566332771517266609360571691111615623236765760

Offset: 1

Jonathan Vos Post, May 27 2006

			a(3) = 7 =
|.1..1..1|
|.1..2..3|
|.6.11.23|.

Alois P. Heinz, Table of n, a(n) for n = 1..17

Cf. A000055, A119493.

More terms from Alois P. Heinz, Sep 26 2011

A144520 a(n) = A000055(n) - 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 5, 10, 22, 46, 105, 234, 550, 1300, 3158, 7740, 19319, 48628, 123866, 317954, 823064, 2144504, 5623755, 14828073, 39299896, 104636889, 279793449, 751065459, 2023443031, 5469566584, 14830871801, 40330829029, 109972410220, 300628862479

Offset: 0

N. J. A. Sloane, Dec 20 2008

nonn

Number of free trees with n nodes, each node with degree <= n-2. - Robert A. Russell, Jan 25 2023

Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Cf. A000055, A144528.

b[n_,i_,t_,k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,k,k]
  + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
  b[0,i_,t_,k_] = 1;
Join[{0,0,0,0,1}, Table[m = n - 3;
  gf[x_] := 1 + Sum[b[j - 1, j - 1, m, m] x^j, {j, 1, n}];
  ci[x_] := SymmetricGroupIndex[m + 1, x] /. x[i_] -> gf[x^i];
  SeriesCoefficient[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}], n], {n,5,35}]] (* Robert A. Russell, Jan 25 2023 *)

a(n) = A144528(n,n-2). - Robert A. Russell, Jan 25 2023

A144527 a(n) = A000055(n) - 2.

Original entry on oeis.org

0, 1, 4, 9, 21, 45, 104, 233, 549, 1299, 3157, 7739, 19318, 48627, 123865, 317953, 823063, 2144503, 5623754, 14828072, 39299895, 104636888, 279793448, 751065458, 2023443030, 5469566583, 14830871800, 40330829028, 109972410219, 300628862478, 823779631719

Offset: 4

N. J. A. Sloane, Dec 20 2008

nonn

Number of free trees with n nodes, each node with degree <= n-3. - Robert A. Russell, Jan 25 2023

Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Cf. A000055, A144528.

b[n_,i_,t_,k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,k,k]
  + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
  b[0,i_,t_,k_] = 1;
Join[{0, 1}, Table[m = n - 4;
  gf[x_] := 1 + Sum[b[j - 1, j - 1, m, m] x^j, {j, 1, n}];
  ci[x_] := SymmetricGroupIndex[m + 1, x] /. x[i_] -> gf[x^i];
  SeriesCoefficient[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}], n], {n,6,35}]] (* Robert A. Russell, Jan 25 2023 *)

a(n) = A144528(n,n-3). - Robert A. Russell, Jan 25 2023

A212809 Decimal expansion of radius of convergence of g.f. for unlabeled trees (A000055).

Original entry on oeis.org

3, 3, 8, 3, 2, 1, 8, 5, 6, 8, 9, 9, 2, 0, 7, 6, 9, 5, 1, 9, 6, 1, 1, 2, 6, 2, 5, 7, 1, 7, 0, 1, 7, 0, 5, 3, 1, 8, 3, 7, 7, 4, 6, 0, 7, 5, 3, 2, 9, 6, 7, 7, 9, 5, 5, 7, 2, 3, 0, 3, 7, 7, 6, 2, 5, 7, 6, 6, 6, 0, 5, 0, 1, 8, 9, 6, 2, 0, 7, 6, 6, 5, 6, 3, 5, 2, 8, 7, 9, 8, 3, 6, 7, 3

Offset: 0

N. J. A. Sloane, May 29 2012

			0.338321856899208...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.6, p. 296.

Michael Drmota and Bernhard Gittenberger, The shape of unlabeled rooted random trees, Eur. J. Comb. 31 (2010) no 8, 2028-2063.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

Cf. A000055.

digits = 95; max = 200;
s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2*k, 0, s[n - k, k]];
a[1] = 1;
a[n_] := a[n] = Sum[a[k]*s[n - 1, k]*k, {k, 1, n - 1}]/(n - 1);
A[x_] := Sum[a[k]*x^k, {k, 0, max}];
eq = Log[c] == 1 + Sum[A[c^-k]/k, {k, 2, max}];
r = 1/c /. FindRoot[eq, {c, 3}, WorkingPrecision -> digits + 5];
RealDigits[r, 10, digits] // First (* Jean-François Alcover, Aug 10 2016 *)

Equals 1/A051491. - Vaclav Kotesovec, Jul 29 2013

More terms from Vaclav Kotesovec, Jul 29 2013

cp's OEIS Frontend

A157904 INVERT transform of A000055.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A052471 Number of noncaterpillar trees on n nodes (A000055-A005418).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A157905 Triangle read by rows, T(n,k) = A000055(n-k) * (A157904 * 0^(n-k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A336042 Numbers k such that A000055(k) is divisible by k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A006790 Exponentiation of e.g.f. for trees A000055(n-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A083202 a(n) = gcd(A000055(n), A000055(n+1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A119528 Determinant of n X n matrix of first n^2 number of trees with n unlabeled nodes (A000055).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A144520 a(n) = A000055(n) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A144527 a(n) = A000055(n) - 2.

Views