login
Number of permutations containing exactly one occurrence of the pattern #, with # one of {1-23, 3-21, 12-3, 32-1}.
2

%I #17 Aug 19 2018 10:42:34

%S 1,7,39,211,1168,6728,40561,256297,1696707,11752973,85047284,

%T 641782220,5041634549,41160207335,348664792199,3059885806071,

%U 27781291314396,260599397789924,2522492941426381,25166308238897929,258507111338795491,2731176458973448817

%N Number of permutations containing exactly one occurrence of the pattern #, with # one of {1-23, 3-21, 12-3, 32-1}.

%H Alois P. Heinz, <a href="/A092923/b092923.txt">Table of n, a(n) for n = 3..500</a>

%H A. Claesson and T. Mansour, <a href="https://arxiv.org/abs/math/0110036">Counting patterns of type (1,2) or (2,1)</a>, arXiv:math/0110036 [math.CO], 2001.

%F G.f.: Sum_{n>=1} (x/(1-n*x)) * Sum_{k>=0} k*x^(k+n)/Product_{l=1..k+n} (1-l*x).

%F Recurrence: a(n) = 2a(n-1) + Sum_{k=0..n-3} C(n-2, k)*(a(k+1) + B(k+1)), with B(n) the Bell numbers A000110(n).

%t a[n_ /; n<3] = 0; a[n_] := a[n] = 2 a[n-1] + Sum[Binomial[n-2, k] (a[k+1] + BellB[k+1]), {k, 0, n-3}];

%t Table[a[n], {n, 3, 24}] (* _Jean-François Alcover_, Aug 19 2018 *)

%o (PARI) a(n)=if(n<1,0,2*a(n-1)+sum(k=0,n-3,binomial(n-2,k)*(a(k+1)+polcoeff(serlaplace(exp(exp(x)-1)),k+1))))

%Y Column k=1 of A260665.

%K nonn

%O 3,2

%A _Ralf Stephan_, Apr 18 2004