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