|
| |
|
|
A113229
|
|
Number of permutations avoiding the consecutive pattern 3412.
|
|
7
| |
|
|
1, 1, 2, 6, 23, 110, 631, 4223, 32301, 277962, 2657797, 27954521, 320752991, 3987045780, 53372351265, 765499019221, 11711207065229, 190365226548070, 3276401870322033, 59523410471007913, 1138295039078030599
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).
|
|
|
REFERENCES
| V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, Arxiv preprint arXiv:1109.2690, 2011
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math., 36 (2006), no. 2, 138-155.
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
|
|
|
LINKS
| Ray Chandler, Table of n, a(n) for n = 0..60
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns.
|
|
|
FORMULA
| The Dotsenko et al. reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.
In the recurrence coded in Mathematica below, w[n, a] = #3412-avoiding permutations on [n] with first entry a; u[n, a, b] is the number that start with an ascent a<b and v[n, a] is the number that start with a descent from a (n>=2). The main sum for u[n, a, b] counts by length k of the longest initial increasing subsequence. The cases k=2, k=3, k>=4 are considered separately.
|
|
|
EXAMPLE
| The 5!-a[5] = 10 permutations on [5] not counted by a[5] are
14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
|
|
|
CROSSREFS
| Cf. A113228, A117156, A117158, A117226, A201692, A201693.
Sequence in context: A117226 A117156 A201692 * A113228 A201693 A063255
Adjacent sequences: A113226 A113227 A113228 * A113230 A113231 A113232
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| David Callan (callan(AT)stat.wisc.edu), Oct 19 2005
|
| |
|
|
