%I #22 Jul 10 2023 07:51:28
%S 1,1,2,5,14,43,144,522,2030,8398,36714,168793,813112,4091735,21451972,
%T 116891160,660554822,3863775322,23353384298,145634065581,935743895590,
%U 6187151514364,42050180222692,293448121230999,2100678197412864
%N Number of permutations in S_n avoiding 31{bar 5}{bar 4}2 (i.e., every occurrence of 312 is contained in an occurrence of a 31542).
%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 From _David Callan_, Oct 14 2012: (Start)
%C a(n) appears to be the number of integer sequences u = (u(0),u(1),...,u(n-1)) satisfying (i) 0<=u(i)<=i for all i, (ii) either u(i)<u(i+1) or u(i+1)=0 for all i, (iii) whenever nonzero entries a,b (in that order) are separated in u by precisely k>=1 0's, b-k does not lie in the interval [1,a].
%C To illustrate, 020 violates condition (i), 011 violates condition (ii), and 0102 violates condition (iii).
%C When n=3 the 5 "u" sequences are 000, 001, 002, 010, 012, and when n=4 the 14 "u" sequences are 0000, 0001, 0002, 0003, 0010, 0012, 0013, 0020, 0023, 0100, 0101, 0103, 0120, 0123.
%C The sequences satisfying the first two conditions are counted by the Bell numbers A000110. (End)
%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 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.
%Y Cf. A000110.
%K nonn
%O 0,3
%A _Lara Pudwell_, Apr 25 2008
%E a(0)=1 prepended by _Alois P. Heinz_, Jul 10 2023