A005753 -id:A005753 - cp's OEIS frontend

A255517 Number A(n,k) of rooted identity trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 3, 5, 2, 0, 0, 1, 4, 12, 18, 3, 0, 0, 1, 5, 22, 64, 66, 6, 0, 0, 1, 6, 35, 156, 363, 266, 12, 0, 0, 1, 7, 51, 310, 1193, 2214, 1111, 25, 0, 0, 1, 8, 70, 542, 2980, 9748, 14043, 4792, 52, 0, 0, 1, 9, 92, 868, 6273, 30526, 82916, 91857, 21124, 113, 0

Offset: 0

Alois P. Heinz, Feb 24 2015

From Vaclav Kotesovec, Feb 24 2015: (Start)
k    Limit n->infinity A(n,k)^(1/n)
  2.517540352632003890795354598463447277335981266803... = A246169
  5.249032491228170579164952216184309265343086337648... = A246312
  7.969494030514425004826375511986491746399264355846...
 10.688492754969652458452048798468242930479212456958...
 13.407087472537747579787047072702638639945914705837...
 16.125529360448558670505097146631763969697822205298...
 18.843901825822305757579605844910623225182677164912...
 21.562238702430237066018783115405680041128676137631...
 24.280555694806692616578932533497629224907619468796...
26.998860838916733933849490675388336975888308433826...
271.64425688361559470587959030374804709717287744789...
Conjecture: For big k the limit asymptotically approaches k*exp(1).
(End)

			A(3,2) = 5:
  o    o    o    o      o
  |    |    |    |     / \
  1    1    2    2    1   2
  |    |    |    |
  1    2    1    2
Square array A(n,k) begins:
  0,  0,   0,    0,    0,     0,     0, ...
  1,  1,   1,    1,    1,     1,     1, ...
  0,  1,   2,    3,    4,     5,     6, ...
  0,  1,   5,   12,   22,    35,    51, ...
  0,  2,  18,   64,  156,   310,   542, ...
  0,  3,  66,  363, 1193,  2980,  6273, ...
  0,  6, 266, 2214, 9748, 30526, 77262, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns k=1-10 give: A004111, A005753, A052757, A052772, A052797, A255518, A255519, A255520, A255521, A255522.
Rows n=0-4 give: A000004, A000012, A001477, A000326, 2*A051662(k-1) for k>0.
Lower diagonal gives A255523.
Cf. A242249, A256068.

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, add(A(n-j, k)*add(
      k*A(d, k)*d*(-1)^(j/d+1), d=divisors(j)), j=1..n-1)/(n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

A[n_, k_] := A[n, k] = If[n<2, n, Sum[A[n-j, k]*Sum[k*A[d, k]*d*(-1)^(j/d + 1), {d, Divisors[j]}], {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

A005754 Number of planted identity matched trees with n nodes.

Original entry on oeis.org

1, 1, 2, 7, 24, 95, 388, 1650, 7183, 31965, 144502, 662241, 3068942, 14358678, 67729973, 321759461, 1538076291, 7392775328, 35707198905, 173221206284, 843634142771, 4123376617009, 20218897206392, 99436453714990, 490355165178472, 2424146632435852

Offset: 1

N. J. A. Sloane

Number of rooted identity trees with n nodes and edges not attached to root are 2-colored or oriented. - Christian G. Bower, Dec 15 1999

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..400
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 430
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A005753, A102755, A246312.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(2*b((i-1)$2), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(b((i-1)$2), j)*g(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=1..30);  # Alois P. Heinz, Aug 01 2013

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[2*b[i-1, i-1], j]*b[n-i*j, i-1], {j, 0, n/i}]]]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[b[i-1, i-1], j]*g[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := g[n-1, n-1]; Table[a[n], {n, 1, 30}] // FullSimplify (* Jean-François Alcover, Dec 02 2013, translated from Alois P. Heinz's Maple program *)

a(n+1) is Weigh transform of A005753. - Christian G. Bower, Dec 15 1999
a(n) ~ c * d^n / n^(3/2), where d = A246312 = 5.2490324912281705791649522..., c = 0.05927840588836202377824646... . - Vaclav Kotesovec, Aug 25 2014
G.f. A(x) satisfies: A(x) = x * exp( A(x)^2/x - A(x^2)^2/(2*x^2) + A(x^3)^2/(3*x^3) - A(x^4)^2/(4*x^4) + ... ). - Ilya Gutkovskiy, May 26 2023

More terms from Christian G. Bower, Dec 15 1999

A246312 Decimal expansion of a constant related to identity matched trees.

Original entry on oeis.org

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

Offset: 1

Vaclav Kotesovec, Aug 25 2014

			5.249032491228170579164952216184309265343086337648736503202233186059585565...

Cf. A005753, A005754, A005755, A102755, A038078, A038077.

Equals lim n -> infinity A005753(n)^(1/n).
Equals lim n -> infinity A005754(n)^(1/n).
Equals lim n -> infinity A005755(n)^(1/n).
Equals lim n -> infinity A102755(n)^(1/n).
Equals lim n -> infinity A038078(n)^(1/n).

More terms from Vaclav Kotesovec, Sep 06 2014, Feb 24 2015 and Dec 26 2020

A038077 Number of rooted identity trees with 2-colored nodes.

Original entry on oeis.org

2, 4, 10, 36, 132, 532, 2222, 9584, 42248, 189776, 864830, 3989656, 18593424, 87413444, 414060796, 1974260912, 9467922870, 45638482068, 221001289714, 1074591477112, 5244497440468, 25681907242416, 126149132242490, 621386729646752, 3068748094479108

Offset: 1

Christian G. Bower, Jan 04 1999

Shifts left and halves under Weigh transform.

Alois P. Heinz, Table of n, a(n) for n = 1..500
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A004111, A038078, A038079, A038080, A246312.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n=1, 2, 2*b((n-1)$2)):
seq(a(n), n=1..40); # Alois P. Heinz, May 20 2013

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i], j]*b[n - i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n==1, 2, 2*b[n-1, n-1]];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

a(n) = 2 * A005753(n).

A102755 Number of asymmetric (or identity) oriented trees with n nodes.

Original entry on oeis.org

1, 1, 1, 4, 10, 37, 135, 522, 2060, 8430, 35115, 149286, 644456, 2821835, 12503878, 56001856, 253174451, 1154179790, 5301178673, 24513058220, 114042743290, 533510321377, 2508491383101, 11849321038092, 56211286929146, 267707017974770, 1279602152054934

Offset: 1

Vladeta Jovovic, Feb 10 2005

nonn

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

Cf. A005753 = number of asymmetric (or identity) rooted oriented trees with n nodes.

Cf. A246312.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(2*b(i-1$2), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> b(n-1$2)-add(b(j-1$2)*b(n-j-1$2), j=1..n-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Aug 01 2013

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[2*b[i-1, i-1], j]*b[n - i*j, i-1], {j, 0, n/i}]]] // FullSimplify; a[n_] := b[n-1, n-1] - Sum[b[j-1, j-1]*b[n-j-1, n-j-1], {j, 1, n-1}]; Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

G.f.: B(x)-B(x)^2, where B(x) is g.f. for A005753.

a(n) ~ c * d^n / n^(5/2), where d = A246312 = 5.249032491228170579164952216..., c = 0.17807103914078424643862998... . - Vaclav Kotesovec, Aug 25 2014

A005755 Number of identity matched trees with n nodes.

Original entry on oeis.org

0, 0, 0, 1, 4, 16, 64, 252, 1018, 4182, 17510, 74510, 322034, 1410362, 6251114, 27998532, 126583634, 577079333, 2650573354, 12256481666, 57021299394, 266754944481, 1254245360430, 5924659521632, 28105641930102, 133853504339029, 639801068848128

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450
Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A005753, A005754, A102755, A246312.

with(numtheory): b2:= proc(n) option remember; local m; `if`(n=1, 1, 2/(n-1) *add(b2(m) *add((-1)^((n-m)/d+1) *d*b2(d), d=divisors(n-m)), m=1..n-1)) end: c2:= proc(n) option remember; local m; `if`(n=1, 1, 1/(n-1) *add(c2(m) *add((-1)^((n-m)/d+1) *d*b2(d), d=divisors(n-m)), m=1..n-1)) end: a2:= n-> (b2(n) -add(b2(m) *b2(n-m), m=1..n-1) -`if`(irem(n, 2)=0, b2(n/2), c2((n+1)/2)))/2: seq(a2(n), n=1..30); # Alois P. Heinz, Aug 04 2009

b2[n_] := b2[n] = If [n == 1, 1, 2/(n-1)*Sum[b2[m]*Sum[(-1)^((n-m)/d+1)*d*b2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; c2[n_] := c2[n] = If [n == 1, 1, 1/(n-1)*Sum[c2[m]*Sum[(-1)^((n-m)/d+1)*d*b2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; a2[n_] := (b2[n] - Sum[b2[m]*b2[n-m], {m, 1, n-1}] - If[Mod[n, 2] == 0, b2[n/2], c2[(n+1)/2]])/2; Table[a2[n], {n, 1, 30}] (* Jean-François Alcover, Mar 17 2014, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(5/2), where d = A246312 = 5.2490324912281705791649522..., c = 0.089035519570392123219315... . - Vaclav Kotesovec, Aug 25 2014

More terms from Alois P. Heinz, Aug 04 2009

A345243 G.f. A(x) satisfies: A(x) = x + x^2 * exp(2 * Sum_{k>=1} (-1)^(k+1) * A(x^k) / k).

Original entry on oeis.org

1, 1, 2, 3, 8, 17, 42, 107, 272, 719, 1914, 5163, 14088, 38733, 107370, 299511, 840372, 2370020, 6714316, 19100096, 54534696, 156230943, 448942998, 1293692305, 3737568960, 10823759093, 31413810702, 91358248179, 266193726712, 776989772307, 2271695757714, 6652074198889

Offset: 1

Ilya Gutkovskiy, Jun 11 2021

nonn

Cf. A005753, A007560, A345244, A345245.

nmax = 32; A[] = 0; Do[A[x] = x + x^2 Exp[2 Sum[(-1)^(k + 1) A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = a[2] = 1; a[n_] := a[n] = (2/(n - 2)) Sum[Sum[(-1)^(k/d + 1) d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 2}]; Table[a[n], {n, 1, 32}]

G.f.: x + x^2 * Product_{n>=1} (1 + x^n)^(2*a(n)).

a(n+2) = (2/n) * Sum_{k=1..n} ( Sum_{d|k} (-1)^(k/d+1) * d * a(d) ) * a(n-k+2).

A363474 G.f. satisfies A(x) = exp( 2 * Sum_{k>=1} (-1)^(k+1) * A(-x^k) * x^k/k ).

Original entry on oeis.org

1, 2, -3, -14, 22, 138, -213, -1536, 2474, 18928, -31451, -248992, 420804, 3416514, -5844716, -48349920, 83503128, 700674606, -1219159874, -10345673158, 18109290380, 155082913608, -272798814028, -2353889042848, 4157686512816, 36104006239798

Offset: 0

Seiichi Manyama, Jun 03 2023

sign

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A306768, A363475.

Cf. A005753, A363470.

seq(n) = my(A=1); for(i=1, n, A=exp(2*sum(k=1, i, (-1)^(k+1)*subst(A, x, -x^k)*x^k/k)+x*O(x^n))); Vec(A);

A(x) = Sum_{k>=0} a(k) * x^k = Product_{k>=0} (1+x^(k+1))^(2 * (-1)^k * a(k)).

a(0) = 1; a(n) = (2/n) * Sum_{k=1..n} ( Sum_{d|k} d * (-1)^(d+k/d) * a(d-1) ) * a(n-k).

A345878 G.f. A(x) satisfies: A(x) = x / exp(2 * Sum_{k>=1} A(x^k) / k).

Original entry on oeis.org

1, -2, 5, -18, 70, -282, 1179, -5104, 22634, -102128, 467637, -2168208, 10157664, -48005858, 228607728, -1095885048, 5284044080, -25609804110, 124693451466, -609641464746, 2991742731876, -14731354000792, 72761153346680, -360397156557696, 1789733084330806, -8909067981051118

Offset: 1

Ilya Gutkovskiy, Jun 28 2021

sign

Cf. A000151, A005753, A045648, A345883.

a:= proc(n) option remember; `if`(n=1, 1, -2*add(a(n-k)*add(
      d*a(d), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
    end:
seq(a(n), n=1..26); # Alois P. Heinz, Jun 28 2021

nmax = 26; A[] = 0; Do[A[x] = x/Exp[2 Sum[A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = 1; a[n_] := a[n] = -(2/(n - 1)) Sum[Sum[d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 1}]; Table[a[n], {n, 1, 26}]

G.f.: x * Product_{n>=1} (1 - x^n)^(2*a(n)).

a(n+1) = -(2/n) * Sum_{k=1..n} ( Sum_{d|k} d * a(d) ) * a(n-k+1).

A345884 G.f. A(x) satisfies: A(x) = x * exp(2 * Sum_{k>=1} (-1)^k * A(x^k) / k).

Original entry on oeis.org

1, -2, 7, -26, 103, -442, 1982, -9122, 42985, -206526, 1007322, -4974066, 24819268, -124949782, 633882799, -3237261340, 16629986395, -85873762466, 445491479309, -2320717519612, 12134813554225, -63667883444468, 335083404759136, -1768545061282712, 9358571746569760

Offset: 1

Ilya Gutkovskiy, Jun 28 2021

sign

Cf. A000151, A005753, A049075, A345885.

a:= proc(n) option remember; `if`(n=1, 1, 2*add(a(n-k)*add(d*a(d)
       *(-1)^(k/d), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
    end:
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 28 2021

nmax = 25; A[] = 0; Do[A[x] = x Exp[2 Sum[(-1)^k A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = 1; a[n_] := a[n] = (2/(n - 1)) Sum[Sum[(-1)^(k/d) d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 1}]; Table[a[n], {n, 1, 25}]

G.f.: x / Product_{n>=1} (1 + x^n)^(2*a(n)).

a(n+1) = (2/n) * Sum_{k=1..n} ( Sum_{d|k} (-1)^(k/d) * d * a(d) ) * a(n-k+1).

cp's OEIS Frontend

A255517 Number A(n,k) of rooted identity trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A005754 Number of planted identity matched trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A246312 Decimal expansion of a constant related to identity matched trees.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A038077 Number of rooted identity trees with 2-colored nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A102755 Number of asymmetric (or identity) oriented trees with n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005755 Number of identity matched trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A345243 G.f. A(x) satisfies: A(x) = x + x^2 * exp(2 * Sum_{k>=1} (-1)^(k+1) * A(x^k) / k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A363474 G.f. satisfies A(x) = exp( 2 * Sum_{k>=1} (-1)^(k+1) * A(-x^k) * x^k/k ).

Views

Author

Keywords

Links

Crossrefs