A318617 - OEIS

A318617

a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 231, and 312.

%I #25 Jan 04 2024 18:09:57

%S 1,1,3,13,73,503,4107,38773,415589,4986715,66238503,965102769,

%T 15306905817,262567910999,4844199561787,95660129298709,

%U 2013392566243565,44997370759528091,1064283567185090791,26560710262784693097,697529916604465424553

%N a(n) is the number of rooted labeled forests on n nodes that avoid the patterns 213, 231, and 312.

%H Andrew Howroyd, <a href="/A318617/b318617.txt">Table of n, a(n) for n = 0..200</a>

%H K. Anders and K. Archer, <a href="https://arxiv.org/abs/1607.03046">Rooted forests that avoid sets of permutations</a>, arXiv:1607.03046 [math.CO], 2017.

%F 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.

%t 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}];

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Sep 13 2018 *)

%o (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

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

%K nonn

%O 0,3

%A _Kassie Archer_, Aug 30 2018