cp's OEIS Frontend

A318618 a(n) is the number of rooted forests on n nodes that avoid the patterns 321, 2143, and 3142.

%I A318618 #34 Jul 07 2025 22:36:04
%S A318618 1,1,3,15,102,870,8910,106470,1454040,22339800,381364200,7161323400,
%T A318618 146701724400,3255661609200,77808668137200,1992415575150000,
%U A318618 54420258228336000,1579320261543024000,48529229906613456000,1574046971727454224000,53741325186841612320000
%N A318618 a(n) is the number of rooted forests on n nodes that avoid the patterns 321, 2143, and 3142.
%C A318618 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.
%H A318618 Andrew Howroyd, <a href="/A318618/b318618.txt">Table of n, a(n) for n = 0..200</a>
%H A318618 Peter J. Taylor, <a href="/A318618/a318618.pdf">Improved formulae for A318618</a>
%F A318618 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).
%F A318618 From _Peter J. Taylor_, Jul 03 2025: (Start)
%F A318618 E.g.f.: -2*(x-1)/(x^2-4*x+2).
%F A318618 a(n) = n! * Sum_{j=0..n/2} binomial(n, 2*j)/2^j
%F A318618 a(n) = 2*n*a(n-1) - n*(n-1)/2*a(n-2).
%F A318618 a(n) ~ (1+sqrt(1/2))^n*n!/2. (End)
%t A318618 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]}];
%t A318618 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Sep 13 2018 *)
%o A318618 (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
%Y A318618 Cf. A000272, A318617, A007840, A000671, A000262.
%K A318618 nonn
%O A318618 0,3
%A A318618 _Kassie Archer_, Aug 30 2018