A113226 Number of permutations of [n] avoiding the pattern 12-34.

1, 1, 2, 6, 23, 107, 585, 3669, 25932, 203768, 1761109, 16595757, 169287873, 1857903529, 21823488238, 273130320026, 3627845694283, 50962676849199, 754814462534449, 11754778469338581, 191998054346198680

Offset: 0

Author

David Callan, Oct 19 2005

Keywords

• nonn

Comments

a(n) is the number of permutations on [n] that avoid the vincular pattern 12-34 (also the number that avoid 43-21).

a(n) is also the number of permutations on [n] that avoid the vincular pattern 12-43 (or 21-34 or 34-21 or 43-12) or 21-43 (or 34-12). - David Bevan, Nov 15 2023

a(n) is also the number of {3,2+2}-free naturally labeled posets. - David Bevan, Nov 15 2023

Examples

			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.
		

Links

• David Bevan, Table of n, a(n) for n = 0..471
• A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
• Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
• David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
• Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
• Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
• Steven Finch, Pattern-Avoiding Permutations [Broken link?]
• Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]

Crossrefs

Cf. A135922 (3-free naturally labeled posets).

Programs

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[Binomial[b - k - If[k <= a, 1, 0], j1] Binomial[
     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[Binomial[n - b, i] Binomial[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}]

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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