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,3

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

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)

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

Prog

(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

Crossrefs

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

Sequence in context: A185753 A174493 A354122 * A123184 A390721 A079486

Adjacent sequences: A318615 A318616 A318617 * A318619 A318620 A318621

Keyword

nonn

Author

Kassie Archer, Aug 30 2018

Status

approved