A113226 - OEIS

This site is supported by donations to The OEIS Foundation.

A113226

Number of permutations avoiding the pattern 12-34.

1, 2, 6, 23, 107, 585, 3669, 25932, 203768, 1761109, 16595757, 169287873, 1857903529, 21823488238, 273130320026, 3627845694283, 50962676849199, 754814462534449, 11754778469338581, 191998054346198680 (list; graph; refs; listen; history; internal format)

	OFFSET	`1,2`
	COMMENTS	`a(n) is the number of permutations on [n] that avoid the mixed consecutive/scattered pattern 12-34 (also number that avoid 43-21).`
	REFERENCES	`Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, Arxiv preprint arXiv:1108.2642, 2011` `Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math., to appear.`
	LINKS	`A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.` `Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns.`
	FORMULA	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).
	EXAMPLE	`523146 contains 2346 as a 12-34 pattern because the 23 and 46 are` `adjacent in the permutation and the reduced form of 2346 is 1234.`
	MATHEMATICA	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}]
	CROSSREFS	`Sequence in context: A000772 A200405 A200403 * A071075 A007555 A101053` `Adjacent sequences: A113223 A113224 A113225 * A113227 A113228 A113229`
	KEYWORD	`nonn`
	AUTHOR	`David Callan (callan(AT)stat.wisc.edu), Oct 19 2005`

Content is available under The OEIS End-User License Agreement .

Last modified February 15 16:28 EST 2012. Contains 205823 sequences.