login
Number of permutations in S_n avoiding 21{bar 3}54 (i.e., every occurrence of 2154 is contained in an occurrence of a 21354).
3

%I #84 Sep 28 2023 13:18:19

%S 1,1,2,6,23,104,530,2958,17734,112657,750726,5207910,37387881,

%T 276467208,2097763554,16282567502,128951419810,1039752642231,

%U 8520041699078,70840843420234,596860116487097,5089815866230374,43886435477701502,382269003235832006,3361054683237796748

%N Number of permutations in S_n avoiding 21{bar 3}54 (i.e., every occurrence of 2154 is contained in an occurrence of a 21354).

%C From _Lara Pudwell_, Oct 23 2008: (Start)

%C 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.

%C 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.

%C 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.

%C 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)

%C 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.

%C (End)

%C From _Mathilde Bouvel_, Apr 26 2017: (Start)

%C Equivalently, permutations avoiding 21{bar 3}54 are those avoiding the vincular pattern 2-14-3.

%C This sequence also enumerates permutations avoiding the vincular pattern 2-41-3 (see Bouvel et al., 2017).

%C (End)

%H Alois P. Heinz, <a href="/A117106/b117106.txt">Table of n, a(n) for n = 0..972</a> (terms n = 1..37 from David Bevan)

%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 Beáta Bényi, Toufik Mansour, and José L. Ramírez, <a href="https://arxiv.org/abs/2309.06518">Pattern Avoidance in Weak Ascent Sequences</a>, arXiv:2309.06518 [math.CO], 2023.

%H M. Bousquet-Mélou and S. Butler, <a href="https://arxiv.org/abs/math/0603617">Forest-like permutations</a>, arXiv:math/0603617 [math.CO], 2006.

%H Mathilde Bouvel, Veronica Guerrini, Andrew Rechnitzer, Simone Rinaldi, <a href="https://arxiv.org/abs/1702.04529">Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence</a>, arXiv:1702.04529 [math.CO], 2017.

%H Zhicong Lin, 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 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 [Section 2.27].

%H Arturo Merino and Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.

%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.

%H L. Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.

%H Jannik Silvanus, <a href="http://hdl.handle.net/20.500.11811/7936">Improved Cardinality Bounds for Rectangle Packing Representations</a>, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).

%H Jannik Silvanus, Jens Vygen, <a href="https://arxiv.org/abs/1708.09779">Few Sequence Pairs Suffice: Representing All Rectangle Placements</a> arXiv:1708.09779 [math.CO], 2017.

%H Chunyan Yan, Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.

%F 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

%F 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

%F From _Mathilde Bouvel_, Apr 26 2017: (Start)

%F Recurrence formula for a(n) (see Bouvel et al., 2017):

%F 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)).

%F Closed formulas for a(n) (see Bouvel et al., 2017):

%F 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)

%F = 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)

%F = 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).

%F Asymptotic behavior (see Bouvel et al., 2017):

%F 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.

%F (End)

%F 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

%e G.f. = x + 2*x^2 + 6*x^3 + 23*x^4 + 104*x^5 + 530*x^6 + 2958*x^7 + 17734*x^8 + ...

%e 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.

%p A117106 := proc(n)

%p local a,j,k ;

%p if n <=1 then

%p 1 ;

%p else

%p a := 0 ;

%p for j from 0 to n do

%p k := binomial(n-1,j+1)*( binomial(n+j+1,j+5)+2*binomial(n+j+1,j)) ;

%p 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)) ;

%p k := k+3*binomial(n-1,j+3)*(binomial(n+j+2,j+4)-binomial(n+j+2,j+2)) ;

%p a := a+binomial(n-1,j)*k ;

%p end do:

%p a/(n-1)

%p end if

%p end proc:

%p seq(A117106(n),n=0..20) ; # _R. J. Mathar_, Dec 05 2022

%t 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 *)

%t 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 *)

%K nonn

%O 0,3

%A _Steve Butler_, Apr 18 2006

%E More terms from _David Bevan_, Feb 12 2014

%E a(0)=1 prepended by _Alois P. Heinz_, Nov 11 2019