login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006789 Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.
(Formerly M1462)
12
1, 1, 2, 5, 14, 43, 143, 509, 1922, 7651, 31965, 139685, 636712, 3020203, 14878176, 75982829, 401654560, 2194564531, 12377765239, 71980880885, 431114329728, 2656559925883, 16825918195484, 109439943234749, 730365368850192 (list; graph; refs; listen; history; text; internal format)
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, ...).

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)

From Gary W. Adamson, 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)

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.

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.

L. Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.

Index entries for sequences related to Bessel functions or polynomials

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

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

Cf. A000110.

Cf. A153197. - Gary W. Adamson, Dec 20 2008

Cf. A086880.

Sequence in context: A155888 A254314 A249562 * A202060 A098569 A137549

Adjacent sequences:  A006786 A006787 A006788 * A006790 A006791 A006792

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Simon Plouffe

EXTENSIONS

Edited by Michael Somos, Oct 06 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 15 18:58 EST 2019. Contains 319170 sequences. (Running on oeis4.)