cp's OEIS Frontend

A137538 Number of permutations in S_n avoiding 25{bar 1}34 (i.e., every occurrence of 2534 is contained in an occurrence of a 25134).

%I A137538 #34 Nov 23 2024 09:49:07
%S A137538 1,1,2,6,23,104,532,3004,18426,121393,851810,6325151,49448313,
%T A137538 405298482,3470885747,30965656442,287083987270,2759838731485,
%U A137538 27458514900626,282264050120512,2993392570828096,32704759586810036,367673428857985261
%N A137538 Number of permutations in S_n avoiding 25{bar 1}34 (i.e., every occurrence of 2534 is contained in an occurrence of a 25134).
%C A137538 From _Lara Pudwell_, Oct 23 2008: (Start)
%C A137538 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 A137538 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 A137538 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 A137538 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 A137538 The number of permutations of length n avoiding the dashed pattern 1-42-3. - _Andrew Baxter_, May 17 2011
%C A137538 Apparently, also the number of permutations of length n avoiding the barred pattern 23{bar 1}54, which are the same as the permutations avoiding dashed pattern 1-24-3. - _Andrew Baxter_, May 17 2011
%H A137538 Andrew M. Baxter, <a href="https://pdfs.semanticscholar.org/2c5d/79e361d3aecb25c380402144177ad7cd9dc8.pdf">Algorithms for Permutation Statistics</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2011.
%H A137538 Andrew M. Baxter and Lara K. Pudwell, <a href="http://arxiv.org/abs/1108.2642">Enumeration schemes for dashed patterns</a>, arXiv preprint arXiv:1108.2642 [math.CO], 2011.
%H A137538 Andrea Frosini, Veronica Guerrini, and Simone Rinaldi, <a href="https://doi.org/10.20944/preprints202411.1611.v1">Constrained Underdiagonal Paths and pattern Avoiding Permutations</a>, Preprints:202411.1611 (2024). See pp. 13-14, 16-17.
%H A137538 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 A137538 Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%e A137538 See example in A137546.
%Y A137538 Cf. A110447, A113226, A137546.
%K A137538 nonn
%O A137538 0,3
%A A137538 _Lara Pudwell_, Apr 25 2008
%E A137538 Edited by _Andrew Baxter_, May 17 2011
%E A137538 Offset corrected by _Alois P. Heinz_, Jul 10 2023