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

Links

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.

Formula

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.

Mathematica

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

Prog

(PARI) 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

Crossrefs

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

Sequence in context: A367751 A367749 A367748 * A059294 A124468 A352302

Adjacent sequences: A318614 A318615 A318616 * A318618 A318619 A318620

Keyword

nonn

Author

Kassie Archer, Aug 30 2018

Status

approved