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

Author

Kassie Archer, Aug 30 2018

Keywords

• nonn

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.

Crossrefs

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

Programs

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

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

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.