A117106 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).

1, 1, 2, 6, 23, 104, 530, 2958, 17734, 112657, 750726, 5207910, 37387881, 276467208, 2097763554, 16282567502, 128951419810, 1039752642231, 8520041699078, 70840843420234, 596860116487097, 5089815866230374, 43886435477701502, 382269003235832006, 3361054683237796748

Offset: 0

Author

Steve Butler, Apr 18 2006

Keywords

• nonn

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)

Examples

			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.
		

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.

Programs

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

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) [phone]*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) [phone]*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) [phone]*a(n+5) -78667094*a(n+6) [phone]*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

Extensions

More terms from David Bevan, Feb 12 2014

a(0)=1 prepended by Alois P. Heinz, Nov 11 2019