A000671 -id:A000671 - cp's OEIS frontend

A318617 a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 231, and 312.

1, 1, 3, 13, 73, 503, 4107, 38773, 415589, 4986715, 66238503, 965102769, 15306905817, 262567910999, 4844199561787, 95660129298709, 2013392566243565, 44997370759528091, 1064283567185090791, 26560710262784693097, 697529916604465424553

Offset: 0

Kassie Archer, Aug 30 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..200
K. Anders and K. Archer, Rooted forests that avoid sets of permutations, arXiv:1607.03046 [math.CO], 2017.

Cf. A000272, A318618, A007840, A000671, A000262.

a[0] = 1; a[n_] := a[n] = Sum[Binomial[n-1, k-1] (r-1)! a[n-k] a[k-r], {k, 1, n}, {r, 1, k}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 13 2018 *)

seq(n)={my(v=vector(n+1)); v[1]=1; for(n=1, n, v[n+1]=sum(k=1, n, sum(r=1, k, binomial(n-1,k-1)*(r-1)!*v[n-k+1]*v[k-r+1]))); v} \\ Andrew Howroyd, Aug 30 2018

a(n) = Sum_{k=1..n} Sum_{r=1..k} binomial(n-1,k-1)*(r-1)!*a(n-k)*a(k-r) for n>0, a(0)=1.

A318618 a(n) is the number of rooted forests on n nodes that avoid the patterns 321, 2143, and 3142.

Original entry on oeis.org

1, 1, 3, 15, 102, 870, 8910, 106470, 1454040, 22339800, 381364200, 7161323400, 146701724400, 3255661609200, 77808668137200, 1992415575150000, 54420258228336000, 1579320261543024000, 48529229906613456000, 1574046971727454224000, 53741325186841612320000

Offset: 0

Kassie Archer, Aug 30 2018

nonn

a(n) is the number of rooted labeled forests on n nodes so that along any path from the root to a vertex, there is at most one descent.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Peter J. Taylor, Improved formulae for A318618

Cf. A000272, A318617, A007840, A000671, A000262.

a[n_] := n! + Sum[n! 2^-j Binomial[n-k-1, j-1] Binomial[k, j], {k, 1, n}, {j, 1, Min[k, n-k]}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Sep 13 2018 *)

a(n) = {n! + sum(k=1, n, sum(j=1, min(k, n-k), n!/(2^j)*binomial(n-k-1,j-1)*binomial(k,j)))} \\ Andrew Howroyd, Aug 31 2018

a(n) = n! + Sum_{k=1..n} Sum_{j=1..min(k, n-k)} (n!/2^j)*binomial(n-k-1, j-1)*binomial(k, j).
From Peter J. Taylor, Jul 03 2025: (Start)
E.g.f.: -2*(x-1)/(x^2-4*x+2).
a(n) = n! * Sum_{j=0..n/2} binomial(n, 2*j)/2^j
a(n) = 2*n*a(n-1) - n*(n-1)/2*a(n-2).
a(n) ~ (1+sqrt(1/2))^n*n!/2. (End)

A363272 Irregular triangle read by rows: T(n,k) = number of unlabeled binary rooted trees with n leaves, where some child tree has k leaves, 1 <= k <= n/2.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 1, 6, 3, 2, 11, 6, 3, 3, 23, 11, 6, 6, 46, 23, 11, 12, 6, 98, 46, 23, 22, 18, 207, 98, 46, 46, 33, 21, 451, 207, 98, 92, 69, 66, 983, 451, 207, 196, 138, 138, 66, 2179, 983, 451, 414, 294, 276, 253, 4850, 2179, 983, 902, 621, 588, 506, 276

Offset: 2

Harry Richman, May 24 2023

			Table begins:
 1;
 1;
 1,  1;
 2,  1;
 3,  2,  1;
 6,  3,  2;
11,  6,  3,  3;
23, 11,  6,  6;
46, 23, 11, 12,  6;
98, 46, 23, 22, 18;
...

Andrew Howroyd, Table of n, a(n) for n = 2..2501 (rows 2..100)

Row sums are A001190.
First column k=1 is T(n,1) = A001190(n-1).
Cf. A000671, A363273.

T(n)={my(A=vector(n), R=vector(n)); A[1]=1; R[1]=[]; for(i=2, n, R[i] = vector(i\2, j, if(2*jAndrew Howroyd, Jan 01 2024

T(n,k) = A001190(k) * A001190(n-k) if k < n/2; otherwise
T(2k,k) = A001190(k) * (A001190(k) + 1) / 2 = A000217(A001190(n)).
Sum_{k >= 1} T(n,k) = A001190(n).
Sum_{i >= k} T(n,i) = A363273(n,k).
Sum_{i <= n-1, i+j >= n} T(i,j) = A000671(n-2).

Terms a(32) and beyond from Andrew Howroyd, Jan 01 2024

A363273 Irregular triangle read by rows: T(n,k) = number of unlabeled binary rooted trees with n leaves, where both children have at least k leaves, 1 <= k <= n/2.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 6, 3, 1, 11, 5, 2, 23, 12, 6, 3, 46, 23, 12, 6, 98, 52, 29, 18, 6, 207, 109, 63, 40, 18, 451, 244, 146, 100, 54, 21, 983, 532, 325, 227, 135, 66, 2179, 1196, 745, 538, 342, 204, 66, 4850, 2671, 1688, 1237, 823, 529, 253, 10905, 6055, 3876, 2893, 1991, 1370, 782, 276

Offset: 2

Harry Richman, May 24 2023

			Table begins:
  1;
  1;
  2,   1;
  3,   1;
  6,   3,  1;
 11,   5,  2;
 23,  12,  6,  3;
 46,  23, 12,  6;
 98,  52, 29, 18,  6;
207, 109, 63, 40, 18;
...

Andrew Howroyd, Table of n, a(n) for n = 2..2501 (rows 1..100)

First column k = 1 is A001190.
Sums along upwards diagonals are A000671.
Cf. A363272.

T(n)={my(A=vector(n), R=vector(n)); A[1]=1; R[1]=[]; for(i=2, n, my(t=vector(i\2, j, if(2*jAndrew Howroyd, Jan 01 2024

T(n,k) = Sum_{j >= k} A363272(n,j).

Sum_{k >= 1} T(n-k, k) = A000671(n-2).

Terms a(27) and beyond from Andrew Howroyd, Jan 01 2024

A036661 Number of n-node rooted labeled trees with deg <= 4 at root and outdegree <= 2 elsewhere.

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 32, 66, 142, 306, 672, 1483, 3316, 7446, 16859, 38353, 87735, 201510, 464801, 1075744, 2498053, 5817576, 13585231, 31801732, 74615404, 175433624, 413281276, 975355639, 2305763635, 5459480822, 12945857671

Offset: 0

N. J. A. Sloane

Cf. A000671, A001190.

G.f.: A(x) = x*cycle_index(S4, f), where f = A001190(x)/x.

cp's OEIS Frontend

A318617 a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 231, and 312.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A318618 a(n) is the number of rooted forests on n nodes that avoid the patterns 321, 2143, and 3142.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A363272 Irregular triangle read by rows: T(n,k) = number of unlabeled binary rooted trees with n leaves, where some child tree has k leaves, 1 <= k <= n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A363273 Irregular triangle read by rows: T(n,k) = number of unlabeled binary rooted trees with n leaves, where both children have at least k leaves, 1 <= k <= n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A036661 Number of n-node rooted labeled trees with deg <= 4 at root and outdegree <= 2 elsewhere.

Views

Author

Keywords

Links

Crossrefs

Formula