OFFSET
0,3
COMMENTS
From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q = 5{bar 1}32{bar 4}, then q1 = 532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)
The bar refers to a missing piece. In other words to say that a permutation has the pattern 21{bar 3}54 means that it has a 2154 (or equivalently a 2143) pattern but that there is no entry in the permutation so that we can extend this 2154 to a 21354 pattern.
(End)
From Mathilde Bouvel, Apr 26 2017: (Start)
Equivalently, permutations avoiding 21{bar 3}54 are those avoiding the vincular pattern 2-14-3.
This sequence also enumerates permutations avoiding the vincular pattern 2-41-3 (see Bouvel et al., 2017).
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..972 (terms n = 1..37 from David Bevan)
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
Beáta Bényi, Toufik Mansour, and José L. Ramírez, Pattern Avoidance in Weak Ascent Sequences, arXiv:2309.06518 [math.CO], 2023.
M. Bousquet-Mélou and S. Butler, Forest-like permutations, arXiv:math/0603617 [math.CO], 2006.
Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, Simone Rinaldi, Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence, arXiv:1702.04529 [math.CO], 2017.
Zhicong Lin, Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016 [Section 2.27].
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
L. Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.
Jannik Silvanus, Improved Cardinality Bounds for Rectangle Packing Representations, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).
Jannik Silvanus, Jens Vygen, Few Sequence Pairs Suffice: Representing All Rectangle Placements arXiv:1708.09779 [math.CO], 2017.
Chunyan Yan, Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
FORMULA
It appears that a(n) = ((-432-120*n^2-360*n)*A005258(n)+(-120*n+144+120*n^3)*A005258(n+1)) / (5*(n-1)*n^2*(n+2)^2*(n+3)^2*(n+4)), for n>1. - Mark van Hoeij, Oct 24 2011
It appears that the g.f. is: -(p*(x^4-78*x^3-1606*x^2+78*x+1)*hypergeom([1/12, 5/12],[1],1728*x^5*(1-11*x-x^2)/p^3)-(x^4+18*x^3+74*x^2-18*x+1)*(228*x-228*x^3+494*x^2+x^4+1)*hypergeom([5/12, 13/12],[1],1728*x^5*(1-11*x-x^2)/p^3))*(x^2+1)/(720*x^4*p^(5/4)) - (1+8*x-6*x^2+7*x^3)/(5*x^3) where p = 1-12*x+14*x^2+12*x^3+x^4. - Mark van Hoeij, Oct 25 2011
From Mathilde Bouvel, Apr 26 2017: (Start)
Recurrence formula for a(n) (see Bouvel et al., 2017):
a(n) = a(n-1)*(11*n^2+11*n-6)/((n+4)(n+3)) + a(n-2)*(n-3)*(n-2)/((n+4)*(n+3)).
Closed formulas for a(n) (see Bouvel et al., 2017):
a(n) = 24/(((n-1)*n^2*(n+1)*(n+2))) * Sum_{j=0..n}binomial(n,j+2)*binomial(n+2,j)*binomial(n+j+2,j+1)
= 24/(((n-1)*n^2*(n+1)*(n+2))) * Sum_{j=0..n}binomial(n,j+2)*binomial(n+1,j)*binomial(n+j+2,j+3)
= 24/(((n-1)*n^2*(n+1)*(n+2))) * Sum_{j=0..n}binomial(n+1,j+3)*binomial(n+2,j+1)*binomial(n+j+3,j).
Asymptotic behavior (see Bouvel et al., 2017):
a(n) ~ A*mu^n/n^6 where mu=phi^(-5) and A=(12/Pi)*5^(-1/4)*phi^(-15/2) for phi=(sqrt(5)-1)/2.
(End)
0 = a(n)*(-51*a(n+2) -6094*a(n+3) +345322*a(n+4) +14274640*a(n+5) -6134240*a(n+6) +594550*a(n+7)) +a(n+1)*(-408*a(n+2) +85125*a(n+3) -2325750*a(n+4) +78667094*a(n+5) -47947020*a(n+6) +6134240*a(n+7)) +a(n+2)*(-3570*a(n+2) -102714*a(n+3) +586187*a(n+4) +64518244*a(n+5) -78667094*a(n+6) +14274640*a(n+7)) +a(n+3)*(-102700*a(n+3) +994500*a(n+4) -586187*a(n+5) -2325750*a(n+6) -345322*a(n+7)) +a(n+4)*(+102700*a(n+4) -102714*a(n+5) -85125*a(n+6) -6094*a(n+7)) +a(n+5)*(+3570*a(n+5) -408*a(n+6) +51*a(n+7)) for all n>0. - Michael Somos, Apr 25 2017
EXAMPLE
G.f. = x + 2*x^2 + 6*x^3 + 23*x^4 + 104*x^5 + 530*x^6 + 2958*x^7 + 17734*x^8 + ...
a(4) = 23 because the permutation 2143 has the pattern 21{bar 3}54, but none of the other 23 permutations in S_4 do.
MAPLE
A117106 := proc(n)
local a, j, k ;
if n <=1 then
1 ;
else
a := 0 ;
for j from 0 to n do
k := binomial(n-1, j+1)*( binomial(n+j+1, j+5)+2*binomial(n+j+1, j)) ;
k := k+2*binomial(n-1, j+2)*(-binomial(n+j+2, j+5) +binomial(n+j+1, j+3) -binomial(n+j+2, j+2) +binomial(n+j+1, j)) ;
k := k+3*binomial(n-1, j+3)*(binomial(n+j+2, j+4)-binomial(n+j+2, j+2)) ;
a := a+binomial(n-1, j)*k ;
end do:
a/(n-1)
end if
end proc:
seq(A117106(n), n=0..20) ; # R. J. Mathar, Dec 05 2022
MATHEMATICA
Table[If[n == 1, 1, 24/(((n - 1) n^2*(n + 1) (n + 2))) Sum[Binomial[n + 1, j + 3] Binomial[n + 2, j + 1] Binomial[n + j + 3, j], {j, 0, n}]], {n, 24}] (* or *)
a[n_] := a[n] = If[n <= 3, Times @@ Range@ n, a[n - 1] (11 n^2 + 11 n - 6)/((n + 4) (n + 3)) + a[n - 2] (n - 3) (n - 2)/((n + 4) (n + 3))]; Array[a, 24] (* Michael De Vlieger, Apr 25 2017 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Steve Butler, Apr 18 2006
EXTENSIONS
More terms from David Bevan, Feb 12 2014
a(0)=1 prepended by Alois P. Heinz, Nov 11 2019
STATUS
approved