login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A318618
a(n) is the number of rooted forests on n nodes that avoid the patterns 321, 2143, and 3142.
2
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
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).
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
KEYWORD
nonn
AUTHOR
Kassie Archer, Aug 30 2018
STATUS
approved