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
Keywords
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..200
- Peter J. Taylor, Improved formulae for A318618
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)
Comments