A246312 -id:A246312 - 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 *)

A005753 Number of rooted identity matched trees with n nodes.

Original entry on oeis.org

1, 2, 5, 18, 66, 266, 1111, 4792, 21124, 94888, 432415, 1994828, 9296712, 43706722, 207030398, 987130456, 4733961435, 22819241034, 110500644857, 537295738556, 2622248720234, 12840953621208, 63074566121245, 310693364823376, 1534374047239554, 7595642577152762

Offset: 1

N. J. A. Sloane

Also number of rooted identity trees with n nodes and 2-colored non-root nodes. - Christian G. Bower, Apr 15 1998

			G.f.: A(x) = x + 2*x^2 + 5*x^3 + 18*x^4 + 66*x^5 + 266*x^6 + ...
where A(x) = x*(1+x)^2*(1+x^2)^4*(1+x^3)^10*(1+x^4)^36*(1+x^5)^132*... (the exponents are A038077(n), n>=1).

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..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 429
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A038077, A246312.

Column k=2 of A255517.

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

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

{a(n)=polcoeff(x*prod(k=1, n-1, (1+x^k+x*O(x^n))^(2*a(k))), n)} /* Paul D. Hanna */

G.f.: x*Product_{n>=1} (1 + x^n)^(2*a(n)) = Sum_{n>=1} a(n)*x^n. - Paul D. Hanna, Dec 31 2011
a(n) ~ c * d^n / n^(3/2), where d = A246312 = 5.249032491228170579164952216..., c = 0.192066288645200371237879149260484794708740197522264442948290580404909605849... - Vaclav Kotesovec, Aug 25 2014, updated Dec 26 2020
G.f. A(x) satisfies: A(x) = x*exp(2*Sum_{k>=1} (-1)^(k+1)*A(x^k)/k). - Ilya Gutkovskiy, Apr 13 2019

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

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

A038078 Number of identity trees with 2-colored nodes.

Original entry on oeis.org

1, 2, 1, 2, 6, 20, 69, 270, 1026, 4120, 16794, 70230, 298306, 1288912, 5642559, 25007756, 111998920, 506348902, 2308338456, 10602357346, 49026021552, 228085486580, 1067020210339, 5016982766202, 23698640081356, 112422573858292, 535414026652828, 2559204304109868

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

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

Cf. A000220. A038077-A038080.

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-> `if`(n=0, 1, 2*b(n-1$2) -2*add(b(j-1$2)*b(n-j-1$2)
        , j=1..n-1) -`if`(irem(n, 2, 'r')=0, b(r-1$2), 0)):
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 02 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}]]];
a[n_] := If[n==0, 1, 2*b[n-1, n-1] - 2*Sum[b[j-1, j-1]*b[n-j-1, n-j-1], {j, 1, n-1}] - If[Mod[n, 2]==0, r=n/2; b[r-1, r-1], 0]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

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

a(n) ~ c * d^n / n^(5/2), where d = A246312 = 5.2490324912281705791649522161843092..., c = 0.356142078281568492877259973613... . - Vaclav Kotesovec, Sep 06 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

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

A005753 Number of rooted identity matched trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A005754 Number of planted identity matched trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

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

A038078 Number of identity trees with 2-colored 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