|
| |
|
|
A006789
|
|
Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.
(Formerly M1462)
|
|
14
|
|
|
|
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
|
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
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)
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)
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
|
|
|
|
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
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,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
