%I A111004
%S A111004 1,1,2,5,16,63,296,1623,10176,71793,562848,4853949,45664896,465403791,
%T A111004 5108121216,60069714207,753492215808,10042248398625,141712039383552,
%U A111004 2110880441637045,33097631526180864,544903371859138335
%N A111004 Number of permutations avoiding a consecutive 132 pattern.
%C A111004 a(n) is the number of permutations on [n] that avoid the consecutive 
               pattern 132 (pattern entries must occur consecutively in the permutation).
%C A111004 Asymptotically, a(n)/n! ~ c/r^n where r = 1.2755477364172... is the unique 
               positive root of Integrate[exp(-t^2/2),{t,0,r}] = 1 and c = exp(r^2/
               2)/r = 1.7685063678958....
%D A111004 Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Advances 
               in Applied Mathematics 30 (2003) 110-125.
%H A111004 Sergi Elizalde, <a href="http://arXiv.org/abs/math.CO/0505254">Asymptotic 
               enumeration of permutations avoiding generalized patterns</a>.
%F A111004 In the Mathematica code below, a[n, k] is the number of such permutations 
               with first entry k and they are counted recursively by the length, 
               say ell, of the longest increasing left factor L. (For ell >=2 the 
               first entry following L must be < the penultimate entry of L or else 
               a consecutive 132 would occur.) The first sum counts ell=1, the second 
               ell=2, the third ell>=3; m is the penultimate entry of L and j is 
               the first entry in the (reduced) subpermutation following L. Note 
               that j is indexed from 0 to cover the case when L is the entire permutation.
%F A111004 E.g.f. Sum_{n>=0}a(n)x^n/n! = 1/( 1-(Pi/2)^(1/2)*Erf[z/2^(1/2)] )
%e A111004 The first 3 entries of 2431 form a consecutive 132 pattern.
%e A111004 The 4!-a(4) = 8 permutations on [4] that DO contain a consecutive 132 
               pattern are 1243, 1324, 1423, 1432, 2143, 2431, 3142, 4132. Also, 
               for example, 1342 contains a scattered 1-3-2 pattern but not a consecutive 
               132.
%t A111004 Clear[a]; a[0, 0] = a[0] = 1; a[n_, 0]/;n>=1 := 0; a[n_, k_]/;k>n := 
               0; a[n_, k_]/;1<=k<=n<=2 := 1; a[n_, k_]/;n>=3 := a[n, k] = Sum[a[n-1, 
               j], {j, k-1}] + (n-k)Sum[a[n-2, j], {j, k-1}] + Sum[(n-m) Binomial[m-k-1, 
               ell-3]a[n-ell, j], {ell, 3, n-k+1}, {m, k+ell-2, n-1}, {j, 0, m-ell+1}]; 
               a[n_]/;n>=1 := a[n] = Sum[a[n, k], {k, n}]; Table[a[n], {n, 0, 15}]
%t A111004 (* or, faster *) ExpGfToList[f_, n_, x_] := CoefficientList[Normal[Series[f, 
               {x, 0, n}]] /. x^(pwr_) -> e!*x^pwr, x]; ExpgfToList[1/( 1-(Pi/2)^(1/
               2)*Erf[z/2^(1/2)] ), 25, z]
%Y A111004 Cf. A049774.
%Y A111004 Sequence in context: A105072 A022494 A136127 this_sequence A079566 A059685 
               A000112
%Y A111004 Adjacent sequences: A111001 A111002 A111003 this_sequence A111005 A111006 
               A111007
%K A111004 nonn
%O A111004 0,3
%A A111004 David Callan (callan(AT)stat.wisc.edu), Oct 01 2005