|
%I M1462 #91 Apr 21 2024 21:07:27
%S 1,1,2,5,14,43,143,509,1922,7651,31965,139685,636712,3020203,14878176,
%T 75982829,401654560,2194564531,12377765239,71980880885,431114329728,
%U 2656559925883,16825918195484,109439943234749,730365368850192
%N Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.
%C From _Lara Pudwell_, Oct 23 2008: (Start)
%C 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.
%C 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.
%C 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.
%C 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)
%C 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
%C 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
%C From _Gary W. Adamson_, Dec 20 2008: (Start)
%C Convolved with A153197 = A006789 shifted: (1, 2, 5, 14, ...); equivalent to row sums of triangle A153206 = (1, 2, 5, 14, ...).
%C Equals inverse binomial transform of A153197 and INVERT transform of A153197 prefaced with a 1.
%C 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.
%C 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)
%C From _Gary W. Adamson_, Dec 21 2008: (Start)
%C 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)
%C From _David Callan_, Nov 11 2011: (Start)
%C 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.
%C 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.
%C (=>) 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.
%C (<=) 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)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vaclav Kotesovec, <a href="/A006789/b006789.txt">Table of n, a(n) for n = 0..640</a>
%H V. E. Adler, <a href="http://arxiv.org/abs/1510.02900">Set partitions and integrable hierarchies</a>, arXiv:1510.02900 [nlin.SI], 2015.
%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H David Callan, <a href="https://arxiv.org/abs/2204.02556">An involution on set partitions</a>, arXiv:2204.02556 [math.CO], 2022.
%H A. Claesson, <a href="http://dx.doi.org/10.1006/eujc.2001.0515">Generalized pattern avoidance</a>, Europ. J. Combin., 22 (2001), 961-971.
%H A. Claesson and T. Mansour, <a href="https://arxiv.org/abs/math/0107044">Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns</a>, arXiv:math/0107044 [math.CO], 2001-2010.
%H P. Flajolet and R. Schott, <a href="http://algo.inria.fr/flajolet/Publications/publist.html">Non-overlapping Partitions, Continued Fractions, Bessel Functions and a Divergent Series</a> In European Journal of Combinatorics, Vol. 11, 1990, pp. 412-432.
%H M. Klazar, <a href="http://dx.doi.org/10.1016/S0097-3165(03)00014-1">Bell numbers, their relatives and algebraic differential equations</a>, J. Combin. Theory, A 102 (2003), 63-87.
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%H <a href="/index/Be#Bessel">Index entries for sequences related to Bessel functions or polynomials</a>
%F 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
%F 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
%F 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
%F a(n) ~ Sum_{k>=0} k^(n+2)/(k!)^2 = A086880(n+2). - _Vaclav Kotesovec_, Aug 24 2014
%F a(n) = R_1(n, 0) for n >= 0 where R_1(n, q) = R_1(n-1, q+1) + Sum_{j=0..q-1} binomial(q, j+1)*R_1(n-1, j) for n > 0, q >= 0 with R_1(0, q) = 1 for q >= 0. Compare to: R_2(n, 0) = A000110(n+1) for n >= 0 where R_2(n, q) = R_2(n-1, q+1) + Sum_{j=0..q} binomial(q, j)*R_2(n-1, j) for n > 0, q >= 0 with R_2(0, q) = 1 for q >= 0. - _Mikhail Kurkov_, Aug 11 2023 [verification needed]
%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 43*x^5 + 143*x^6 + 509*x^7 + ...
%t 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_ *)
%o (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 */
%o (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 */
%o (PARI) upto(n)=my(v1, v2, v3, v4); v1=vector(n+1, i, 1); v2=v1; v3=vector(n+1, i, 0); v3[1]=1; v4=vector(n, i, vector(i, j, j==1 || j==i)); for(i=3, n, for(j=2, i-1, v4[i][j]=v4[i-1][j] + v4[i-1][j-1])); for(i=1, n, for(q=0, n-i, v2[q+1]=v1[q+2] + sum(j=0, q-1, v4[q+1][j+2]*v1[j+1])); v1=v2; v3[i+1]=v1[1]); v3 \\ _Mikhail Kurkov_, Aug 11 2023 [verification needed]
%Y Cf. A000110.
%Y Cf. A153197. - _Gary W. Adamson_, Dec 20 2008
%Y Cf. A086880.
%K nonn,changed
%O 0,3
%A _N. J. A. Sloane_, _Simon Plouffe_
%E Edited by _Michael Somos_, Oct 06 2003
|
