cp's OEIS Frontend

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

%I A113226 #48 Feb 21 2025 16:46:14
%S A113226 1,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 of [n] avoiding the pattern 12-34.
%C A113226 a(n) is the number of permutations on [n] that avoid the vincular pattern 12-34 (also the number that avoid 43-21).
%C A113226 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
%C A113226 a(n) is also the number of {3,2+2}-free naturally labeled posets. - _David Bevan_, Nov 15 2023
%H A113226 David Bevan, <a href="/A113226/b113226.txt">Table of n, a(n) for n = 0..471</a>
%H A113226 A. M. Baxter, <a href="https://pdfs.semanticscholar.org/2c5d/79e361d3aecb25c380402144177ad7cd9dc8.pdfindex.html">Algorithms for Permutation Statistics</a>, Ph. D. Dissertation, Rutgers University, May 2011.
%H A113226 Andrew M. Baxter and Lara K. Pudwell, <a href="http://arxiv.org/abs/1108.2642">Enumeration schemes for dashed patterns</a>, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
%H A113226 David Bevan, Gi-Sang Cheon and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.08023">On naturally labelled posets and permutations avoiding 12-34</a>, arXiv:2311.08023 [math.CO], 2023.
%H A113226 Sergi Elizalde, <a href="https://arxiv.org/abs/math/0505254">Asymptotic enumeration of permutations avoiding generalized patterns</a>, arXiv:math/0505254 [math.CO], 2005.
%H A113226 Sergi Elizalde, <a href="https://doi.org/10.1016/j.aam.2005.05.006">Asymptotic enumeration of permutations avoiding generalized patterns</a>, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
%H A113226 Steven Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Broken link?]
%H A113226 Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%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 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];
%t A113226 v[n_] /; n >= 2 := v[n] = Sum[v[n, a], {a, 2, n}]; v[1, 1] = 1;
%t A113226 v[n_, a_] /; 2 <= a <= n :=
%t A113226 v[n, a] = Sum[u[n - 1, b], {b, a - 1}] + Sum[v[n - 1, b], {b, 2, a - 1}];
%t A113226 u[1] = 1; u[n_] /; n >= 2 := u[n] = Sum[u[n, a], {a, n - 1}]; u[1, 1] = 1;
%t A113226 u[n_, a_] /; a == n := 0; u[n_, a_] /; 1 <= a < n := u[n, a, n];
%t A113226 u[1, 1, k_] := 1; u[2, 1, k_] := 1; u[n_, a_, k_] /; a >= n := 0;
%t A113226 u[n_, a_, k_] /; 1 <= a < n && n >= 3 :=
%t A113226 u[n, a, k] = Sum[u[n, a, k, b], {b, a + 1, n}];
%t A113226 u[n_, a_, k_, b_] /; 1 <= a < b <= n && k >= b + 2 := u[n, a, b + 1, b];
%t A113226 u[n_, a_, k_, b_] /; 1 <= a < n && b == n && k == n + 1 := u[n, a, n, n];
%t A113226 u[n_, a_, k_, b_] /; 1 == a < b == n && k == 2 := 1;
%t A113226 u[n_, a_, k_, b_] /; 1 <= a < b <= n && k <= b :=
%t A113226 u[n, a, k, b] =
%t A113226   Sum[Binomial[b - k - If[k <= a, 1, 0], j1] Binomial[
%t A113226      k - 1 - If[a < k, 1, 0] - c, j2]*
%t A113226     u[n - 2 - j1 - j2, c, k - If[a < k, 1, 0] - j2], {c,
%t A113226     k - 1 - If[a < k, 1, 0]}, {j1, 0, b - k - If[k <= a, 1, 0]}, {j2, 0,
%t A113226     k - 1 - If[a < k, 1, 0] - c}];
%t A113226 u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} == {1, 2} := 1;
%t A113226 u[n_, a_, k_, b_] /; 1 <= a < b < n && k == b + 1 && {a, b} != {1, 2} :=
%t A113226 u[n, a, k, b] =
%t A113226   Sum[Binomial[n - b, i] Binomial[b - 2 - c, j] u[n - 2 - i - j, c,
%t A113226      b - 1 - j], {c, b - 2}, {i, 0, n - b}, {j, 0, b - 2 - c}]; Table[
%t A113226 w[n], {n, 0, 15}]
%Y A113226 Cf. A135922 (3-free naturally labeled posets).
%K A113226 nonn
%O A113226 0,3
%A A113226 _David Callan_, Oct 19 2005