%I A113226
%S A113226 1,2,6,23,107,585,3669,25932,203768,1761109,16595757,169287873,
%T A113226 1857903529,21823488238,273130320026,3627845694283,50962676849199,
%U A113226 754814462534449,11754778469338581,191998054346198680
%N A113226 Number of permutations avoiding the pattern 12-34.
%C A113226 a(n) is the number of permutations on [n] that avoid the mixed consecutive/
               scattered pattern 12-34 (also number that avoid 43-21).
%D A113226 Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized 
               patterns, Adv. in Appl. Math., to appear.
%H A113226 Sergi Elizalde, <a href="http://front.math.ucdavis.edu/math.CO/0505254">
               Asymptotic enumeration of permutations avoiding generalized patterns</
               a>..
%F A113226 In the recurrence coded in Mathematica below, w[n] = # (12-34)-avoiding 
               permutations on [n]; v[n, a] is the number that start with a descent 
               and have first entry a; u[n, a, k, b] is the number that start with 
               an ascent and that have (i) first entry a, (ii) other than a, all 
               ascent initiators <k, (iii) second entry b. The summation index c 
               denotes the next ascent initiator after a. The indices j1, j2, i, 
               j all count entries lying strictly between a and c in position and 
               with value in the intervals: j1 in [k, b), j2 in (c, k), i in (b, 
               n], j in (c, b).
%e A113226 523146 contains 2346 as a 12-34 pattern because the 23 and 46 are
%e A113226 adjacent in the permutation and the reduced form of 2346 is 1234.
%t A113226 Clear[u, v, w]; w[0]=w[1]=1; w[n_]/;n>=2 := w[n] = u[n]+v[n]; v[n_]/;
               n>=2 := v[n] = Sum[v[n, a], {a, 2, n}]; v[1, 1] = 1; v[n_, a_]/;2<=a<=n 
               := v[n, a] = Sum[u[n-1, b], {b, a-1}] + Sum[v[n-1, b], {b, 2, a-1}]; 
               u[1] = 1; u[n_]/;n>=2 := u[n] = Sum[u[n, a], {a, n-1}]; u[1, 1] = 
               1; u[n_, a_]/;a==n := 0; u[n_, a_]/;1<=a<n := u[n, a, n]; u[1, 1, 
               k_] := 1; u[2, 1, k_] := 1; u[n_, a_, k_]/;a>=n := 0; u[n_, a_, k_]/
               ;1<=a<n && n>=3 := u[n, a, k] = Sum[u[n, a, k, b], {b, a+1, n}]; 
               u[n_, a_, k_, b_]/;1<=a<b<=n && k>=b+2 := u[n, a, b+1, b]; u[n_, 
               a_, k_, b_]/;1<=a<n && b==n && k==n+1 := u[n, a, n, n]; u[n_, a_, 
               k_, b_]/;1==a<b==n && k==2 := 1; u[n_, a_, k_, b_]/;1<=a<b<=n && 
               k<=b := u[n, a, k, b] = Sum[bi[b-k-If[k<=a, 1, 0], j1]bi[k-1-If[a<k, 
               1, 0]-c, j2]* u[n-2-j1-j2, c, k-If[a<k, 1, 0]-j2], {c, k-1-If[a<k, 
               1, 0]}, {j1, 0, b-k-If[k<=a, 1, 0]}, {j2, 0, k-1-If[a<k, 1, 0]-c}]; 
               u[n_, a_, k_, b_]/;1<=a<b<n && k==b+1 && {a, b}=={1, 2} := 1; u[n_, 
               a_, k_, b_]/;1<=a<b<n && k==b+1 && {a, b}!={1, 2} := u[n, a, k, b] 
               = Sum[bi[n-b, i]bi[b-2-c, j]u[n-2-i-j, c, b-1-j], {c, b-2}, {i, 0, 
               n-b}, {j, 0, b-2-c}]; Table[w[n], {n, 0, 15}]
%Y A113226 Sequence in context: A125273 A130908 A000772 this_sequence A071075 A007555 
               A101053
%Y A113226 Adjacent sequences: A113223 A113224 A113225 this_sequence A113227 A113228 
               A113229
%K A113226 nonn
%O A113226 0,2
%A A113226 David Callan (callan(AT)stat.wisc.edu), Oct 19 2005