A113227 - OEIS

%I #92 Nov 23 2024 09:48:15

%S 1,1,2,6,23,105,549,3207,20577,143239,1071704,8555388,72442465,

%T 647479819,6083742438,59885558106,615718710929,6595077685263,

%U 73424063891526,847916751131054,10138485386085013,125310003360265231

%N Number of permutations avoiding the pattern 1-23-4.

%C a(n) is the number of permutations on [n] that avoid the mixed consecutive/scattered pattern 1-23-4 (also number that avoid 4-32-1).

%C From _David Callan_, Jul 25 2008: (Start)

%C a(n) appears to also count vertical-marked parallelogram polyominoes of perimeter 2n+2; vertical-marked means that for each vertical line that splits the polyomino into two nonempty polyominoes one of the unit segments on the common boundary is marked.

%C ....._

%C ..._|.|

%C ._|...|

%C |_._._|

%C For example, the polyomino above, with n=5, has two such vertical lines, the left line giving only one choice for marking and the right line giving two choices. (End)

%H Alois P. Heinz, <a href="/A113227/b113227.txt">Table of n, a(n) for n = 0..250</a>

%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/2003.11533">Wilf equivalences between vincular patterns in inversion sequences</a>, arXiv:2003.11533 [math.CO], 2020.

%H 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 Andrew M. Baxter and Lara K. Pudwell, <a href="http://arxiv.org/abs/1108.2642">Enumeration schemes for vincular patterns</a>, arXiv preprint arXiv:1108.2642 [math.CO], 2011.

%H Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini, and Simone Rinaldi, <a href="https://arxiv.org/abs/1808.04114">Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers</a>, arXiv:1808.04114 [math.CO], 2018.

%H David Callan, <a href="http://arxiv.org/abs/1008.2375">A bijection to count (1-23-4)-avoiding permutations</a>, arXiv:1008.2375 [math.CO], 2010.

%H Matteo Cervetti, <a href="https://arxiv.org/abs/2103.00246">A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4</a>, arXiv:2103.00246 [math.CO], 2021.

%H Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, <a href="http://arxiv.org/abs/1510.05434">Patterns in Inversion Sequences I</a>, arXiv:1510.05434 [math.CO], 2015.

%H Sergi Elizalde, <a href="http://arxiv.org/abs/math/0505254">Asymptotic enumeration of permutations avoiding generalized patterns</a>, arXiv:math/0505254 [math.CO], 2005.

%H Sergi Elizalde, <a href="http://dx.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 Steven Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Broken link?]

%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]

%H Andrea Frosini, Veronica Guerrini, and Simone Rinaldi, <a href="https://doi.org/10.20944/preprints202411.1611.v1">Constrained Underdiagonal Paths and pattern Avoiding Permutations</a>, Preprints:202411.1611 (2024). See pp. 9, 12.

%H Zhicong Lin and Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation (2020), Vol. 364, 124672.

%H Zhicong Lin and Shishuo Fu, <a href="https://arxiv.org/abs/2003.11813">On 120-avoiding inversion and ascent sequences</a>, arXiv:2003.11813 [math.CO], 2020.

%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.

%H Benjamin Testart, <a href="https://arxiv.org/abs/2407.07701">Completing the enumeration of inversion sequences avoiding one or two patterns of length 3</a>, arXiv:2407.07701 [math.CO], 2024. See p. 2.

%F In the recurrence coded in Mathematica below, v[n, a] is the number of permutations on [n] that avoid the 3-letter pattern 1-23 and start with a; u[n, a, m, k] is the number of 1-23-4-avoiding permutations on [n] that start with a, have n in position k and for which m is the minimum of the first k-1 entries. In the last sum, j is the number of entries lying strictly between a and n both in value and position.

%F From _Gary W. Adamson_, Jul 08 2011: (Start)

%F a(n) = the upper left term in M^n, M = the production matrix:

%F   1, 1

%F   1, 2, 1

%F   1, 2, 3, 1

%F   1, 2, 3, 4, 1

%F   1, 2, 3, 4, 5, 1

%F   ...

%F (End)

%F G.f.: 1+x/(U(0)-x) where U(k) = 1 - x*k - x/U(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 10 2012

%F Conjecture: a(n) = R(n-1, 0) for n > 0 with a(0) = 1 where R(n, q) = R(n-1, q+1) + Sum_{j=0..q} (j+1)*R(n-1, j) for n > 0, q >= 0 with R(0, q) = 1 for q >= 0. - _Mikhail Kurkov_, Jan 05 2024

%e 12534 contains a scattered 1-2-3-4 pattern (1234 itself) but not a 1-23-4 because the 2 and 3 are not adjacent in the permutation.

%t v[n_, a_] := v[n, a] = Sum[StirlingS2[a-1, i-1]i^(n-a), {i, a}];

%t u[0]=u[1]=1; u[n_]/; n>=2 := u[n] = Sum[u[n, a], {a, n}];

%t u[1, 1]=u[2, 1]=u[2, 2]=1;

%t u[n_, a_]/; n>=3 && a==n := u[n-1];

%t u[n_, a_]/; n>=3 && a<n := u[n, a] = u[n, a, a, 2] + Sum[u[n, a, m, k], {k, 3, n}, {m, Min[a, n-k+1]}];

%t u[n_, a_, m_, k_]/; n>=3 && k==2 && a<n && m==a := u[n-1, a];

%t u[n_, a_, m_, k_]/; n>=3 && k>=3 && a<n && m==a := bi[n-a-1, k-2]v[k-1, 1]u[n-k+1, a];

%t u[n_, a_, m_, k_]/; n>=3 && k>=3 && a<n && m<=Min[a-1, n-k+1] := Sum[bi[n-a-1, j]bi[a-m-1, k-3-j]v[k-1, k-1-j]u[n-k+1, m], {j, Max[0, k-2-(a-m)], Min[n-a-1, k-3]}];

%t Table[u[n], {n, 0, 15}]

%K nonn

%O 0,3

%A _David Callan_, Oct 19 2005