

A006789


Bessel numbers: the number of nonoverlapping partitions of an nset 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 orderisomorphic 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 nonsingleton 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 Cartanlike 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 123 and 123, and we show that a permutation p avoids tau <=> p avoids both 123 and 123.
(=>) For an increasing triple abc in a tauavoider p, there must be a "5" between the a and b. So p certainly avoids 123, and similarly p avoids 123.
(<=) For an increasing triple abc in a (123)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. BousquetMélou, A. Denise, P. Flajolet, D. Gardy and D. GouyouBeauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(13), March 2002, pp. 2955.
A. Claesson, Generalized pattern avoidance, Europ. J. Combin., 22 (2001), 961971.
A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of BabsonSteingrimsson patterns, arXiv:math/0107044 [math.CO], 20012010.
P. Flajolet and R. Schott, Nonoverlapping Partitions, Continued Fractions, Bessel Functions and a Divergent Series In European Journal of Combinatorics, Vol. 11, 1990, pp. 412432.
M. Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 6387.
Lara Pudwell, Enumeration Schemes for PatternAvoiding 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, 2step).  Sergei N. Gladkovskii, Oct 13 2012
G.f.: T(0)/(1x), where T(k) = 1  x^2/( x^2  (1x*(k+1))*(1x*(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}] (* JeanFranç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



