0,3

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)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A. Claesson, Generalized pattern avoidance, Europ. J. Combin., 22 (2001), 961-971.

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.

M. Klazar, Bell numbers, their relatives and algebraic differential equations

A. Claesson and T. Mansour, Permutations avoiding a pair of generalized patterns....

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.

Index entries for sequences related to Bessel functions or polynomials

G.f. 1/(1-x-x^2/(1-2x-x^2/(1-3x-x^2/...))) (a continued fraction).

(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 */

(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))}

Cf. A000110.

A153197 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 20 2008]

Sequence in context: A005425 A035349 A155888 this_sequence A098569 A137549 A014327

Adjacent sequences: A006786 A006787 A006788 this_sequence A006790 A006791 A006792

nonn

N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)

Edited by Michael Somos, Oct 06, 2003