A113227 Number of permutations of [n] avoiding the pattern 1-23-4.
1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239, 1071704, 8555388, 72442465, 647479819, 6083742438, 59885558106, 615718710929, 6595077685263, 73424063891526, 847916751131054, 10138485386085013, 125310003360265231
Offset: 0
Keywords
Examples
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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..250
- Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
- A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
- Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for vincular patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
- Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini, and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
- David Callan, A bijection to count (1-23-4)-avoiding permutations, arXiv:1008.2375 [math.CO], 2010.
- Matteo Cervetti, A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4, arXiv:2103.00246 [math.CO], 2021.
- Sylvie Corteel, Megan A. Martinez, Carla D. Savage, and Michael Weselcouch, Patterns in Inversion Sequences I, arXiv:1510.05434 [math.CO], 2015.
- 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]
- Andrea Frosini, Veronica Guerrini, and Simone Rinaldi, Constrained Underdiagonal Paths and pattern Avoiding Permutations, Preprints:202411.1611 (2024). See pp. 9, 12.
- Zhicong Lin and Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
- Zhicong Lin and Shishuo Fu, On 120-avoiding inversion and ascent sequences, arXiv:2003.11813 [math.CO], 2020.
- Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
- Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See p. 2.
Programs
-
Mathematica
v[n_, a_] := v[n, a] = Sum[StirlingS2[a-1, i-1]i^(n-a), {i, a}]; u[0]=u[1]=1; u[n_]/; n>=2 := u[n] = Sum[u[n, a], {a, n}]; u[1, 1]=u[2, 1]=u[2, 2]=1; u[n_, a_]/; n>=3 && a==n := u[n-1]; u[n_, a_]/; n>=3 && a=3 && k==2 && a =3 && k>=3 && a =3 && k>=3 && a
Formula
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.
From Gary W. Adamson, Jul 08 2011: (Start)
a(n) = the upper left term in M^n, M = the production matrix:
1, 1
1, 2, 1
1, 2, 3, 1
1, 2, 3, 4, 1
1, 2, 3, 4, 5, 1
...
(End)
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
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
Comments