A113226 Number of permutations 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,3

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

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]

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[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}]

Crossrefs

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

Sequence in context: A200405 A336071 A200403 * A071075 A007555 A101053

Adjacent sequences: A113223 A113224 A113225 * A113227 A113228 A113229

Keyword

nonn

Author

David Callan, Oct 19 2005

Status

approved