| Comment from Lara Pudwell (Lara.Pudwell(AT)valpo.edu), 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)
Nonoverlapping means that the intervals associated with the minimum to maximum integers of any two blocks of a partition do not overlap. Instead, the intervals are disjoint or one contains another.
Apparently, also the number of permutations in S_n avoiding 2{bar 5}3{bar 1}4 (i.e. every occurrence of 234 is contained in an occurrence of a 25314). - Lara Pudwell (Lara.Pudwell(AT)valpo.edu), Apr 25 2008
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 20 2008: (Start)
Convolved with A153197 = A006789 shifted: (1, 2, 5, 14,...); equivalent to row sums of triangle A153206 = (1, 2, 5, 14,...).
Equals inverse binomial transform of A153197 and INVERT transform of A153197 prefaced with a 1.
Can be generated from the Hankel transform [1,1,1,...] through successive
iterative operations of: binomial transform, INVERT transform, binomial
transform, (repeat)...; or starting with INVERT transform. The operations
converge to a two sequence limit cycle of A006789 and its binomial transform, A153197.
Shifts to (1, 2, 5, 14,...) with A006789 * A153197 prefaced with a 1; i.e.
(1, 2, 5, 14, 43,...) = (1, 1, 2, 5, 14,...) * (1, 1, 2, 5, 15,...); where A153197 = (1, 2, 5, 15, 51, 189, 748, 3128, 13731,...). (End)
Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 21 2008: (Start)
a(n) = term (1,1) of M^n, where M = an infinite Cartan-like matrix with 1's
the super- and subdiagonals (diagonals starting at (1,2) and (2,1)
respectively; and the main diagonal = (1,2,3,...). (End)
Comment from David Callan, Nov 11 2011. (Start)
a(n) is indeed the number of permutations in S_n avoiding the pattern tau = 2{bar 5}3{bar 1}4 of the Pudwell comment.
Proof. It is known (Claesson and Mansour link, Proposition 2, p.2) that a(n) is the number of permutations in S_n avoiding both of the dashed patterns 1-23 and 12-3, and we show that a permutation p avoids tau <=> p avoids both 1-23 and 12-3.
(=>) For an increasing triple abc in a tau-avoider p, there must be a "5" between the a and b. So p certainly avoids 12-3, and similarly p avoids 1-23.
(<=) For an increasing triple abc in a (12-3)-avoider, there must be an entry x between a and b. We will see that an x>c can be found and this x will serve as the required "5". If x<b, you can take x as a new "a" and the new abc are closer in position. Repeat until x>b. If x<c, you can take x as a new "b" that is closer to c in value. Repeat until x>c. Done. An analogous method produces the required "1". (End)
| 