cp's OEIS Frontend

A258041 Number of 312-avoiding derangements of {1,2,...,n}.

%I A258041 #11 May 18 2015 14:37:17
%S A258041 1,0,1,1,4,10,31,94,303,986,3284,11099,38024,131694,460607,1624451,
%T A258041 5771532,20640334,74246701,268478962,975436348,3559204700,13037907692,
%U A258041 47931423574,176792821643,654078238224,2426705590840,9026907769955
%N A258041 Number of 312-avoiding derangements of {1,2,...,n}.
%C A258041 In the Mathematica recurrence below, a(n,k) is the number of 312-avoiding permutations of {1,2,...,n} with no entry moved k places to the right of its "natural" position; thus a(n,0) = a(n). The recurrence for a(n,k) counts these permutations by the position j of 1 in the permutation.
%C A258041 Numerical evidence suggests lim_{n->inf} a(n)/a(n-1) = 4 and lim_{n->inf} A000108(n)/(n*a(n)) ~ .105.
%H A258041 Vaclav Kotesovec, <a href="/A258041/b258041.txt">Table of n, a(n) for n = 0..1000</a>
%H A258041 Aaron Robertson, Dan Saracino, and Doron Zeilberger, <a href="http://arxiv.org/abs/math/0203033">Refined Restricted Permutations</a>, arXiv:math/0203033 [math.CO], 2002.
%H A258041 Aaron Robertson, Dan Saracino, and Doron Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/DWilf.pdf">Refined Restricted Permutations</a>, Annals of Combinatorics 6 (2002) 427-444.
%F A258041 G.f.: 1/(1 + C(0)x -
%F A258041          x/(1 + C(1)x^2 -
%F A258041              x/(1 + C(2)x^3 -
%F A258041                 x/(1 + C(3)x^4 -
%F A258041                    x/(1 + C(4)x^5 -
%F A258041                       x/(1 + C(5)x^6 - ...)))))))) [continued fraction] where C(n) = A000108(n) is the n-th Catalan number.
%e A258041 a(4) = 4 counts 2143, 2341, 3421, 4321.
%t A258041 a[n_, k_] /; k >= n := CatalanNumber[n]
%t A258041 a[n_, k_] /; 0 <= k < n :=
%t A258041 a[n, k] = Sum[a[j - 1, k + 1] a[n - j, k]  , {j, k}] + Sum[a[j - 1, k + 1] a[n - j, k],{j, k + 2, n}]
%t A258041 a[n_] := a[n, 0]
%t A258041 Table[a[n], {n, 0, 30}]
%Y A258041 Cf. A000108, A000166, A061547.
%K A258041 nonn
%O A258041 0,5
%A A258041 _David Callan_, May 17 2015