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

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

Offset: 0

Author

Kassie Archer, Aug 30 2018

Keywords

• nonn

Comments

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.

Links

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

Crossrefs

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

Programs

Mathematica

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 *)

PARI

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

Formula

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)