OFFSET
0,3
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)
Nonoverlapping means that the intervals associated with the minimum to maximum integers of any two non-singleton blocks of a partition do not overlap. Instead, the intervals are disjoint or one contains another. - Michael Somos, Oct 06 2003
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, Apr 25 2008
From Gary W. Adamson, Dec 20 2008: (Start)
Convolved with A153197 = A006789 shifted: (1, 2, 5, 14, ...); equivalent to row sums of triangle A153206 = (1, 2, 5, 14, ...).
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)
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,...). - Gary W. Adamson, Dec 21 2008
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)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 0..640
V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
David Callan, An involution on set partitions, arXiv:2204.02556 [math.CO], 2022.
A. Claesson, Generalized pattern avoidance, Europ. J. Combin., 22 (2001), 961-971.
A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns, arXiv:math/0107044 [math.CO], 2001-2010.
P. Flajolet and R. Schott, Non-overlapping Partitions, Continued Fractions, Bessel Functions and a Divergent Series In European Journal of Combinatorics, Vol. 11, 1990, pp. 412-432.
M. Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 63-87.
Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.
FORMULA
G.f.: 1 / (1 - x - x^2 / (1 - 2*x - x^2 / (1 - 3*x - x^2 / ...))) (a continued fraction). - Michael Somos, Oct 06 2003
G.f.: 1/(U(0)-1) + 1/x^2 where U(k)= 1 - x*(k+1) + x/(1 + x/U(k+1)) ; (continued fraction, 2-step). - Sergei N. Gladkovskii, Oct 13 2012
G.f.: T(0)/(1-x), where T(k) = 1 - x^2/( x^2 - (1-x*(k+1))*(1-x*(k+2))/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 02 2013
a(n) ~ Sum_{k>=0} k^(n+2)/(k!)^2 = A086880(n+2). - Vaclav Kotesovec, Aug 24 2014
Conjecture: a(n) = R(n, 0) for n >= 0 where R(n, q) = R(n-1, q+1) + Sum_{j=0..q-1} binomial(q, j+1)*R(n-1, j) for n > 0, q >= 0 with R(0, q) = 1 for q >= 0. - Mikhail Kurkov, Aug 11 2023
EXAMPLE
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 43*x^5 + 143*x^6 + 509*x^7 + ...
MATHEMATICA
nmax = 24; m = SparseArray[{{i_, i_} :> i, Band[{1, 2}] -> 1, Band[{2, 1}] -> 1}, {nmax, nmax}]; a[n_] := MatrixPower[m, n][[1, 1]]; Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Nov 22 2012, after Gary W. Adamson *)
PROG
(PARI) {a(n) = local(m); if( n<0, 0, m = contfracpnqn(matrix(2, n\2, i, k, if( i==1, -x^2, 1 - (k+1)*x))); polcoeff( 1 / (1 - x + m[2, 1] / m[1, 1]) + x * O(x^n), n))}; /* Michael Somos, Oct 06 2003 */
(PARI) {a(n) = local(A); if( n<0, 0, A = O(x^0); for(i=0, n\2, A = subst((1 + x) / (1 - x^2*A), x, x / (1 - x))); polcoeff( A, n))}; /* Michael Somos, Sep 22 2005 */
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
Edited by Michael Somos, Oct 06 2003
STATUS
approved