A153197 -id:A153197 - cp's OEIS frontend

A153206 Convolution triangle by rows, T(n,k) = A153197(n-k) * A153198.

1, 1, 1, 2, 1, 2, 5, 2, 2, 5, 15, 5, 4, 5, 14, 51, 15, 10, 10, 14, 43, 189, 51, 30, 25, 28, 43, 143, 748, 189, 102, 75, 70, 86, 143, 509, 3128, 748, 378, 255, 210, 215, 286, 509, 1922, 13731, 3128, 1496, 945, 714, 645, 715, 1018, 1922, 7651

Offset: 0

Gary W. Adamson, Dec 20 2008

A153197 prefaced with a 1: (1, 1, 2, 5, 15, 51,...) convolved with A006789 (1, 1, 2, 5, 14, 43,...) = A006789 shifted: (1, 2, 5, 14, 43, 143,...).

Right border = A006789, row sums = A006789 shifted.

			First few rows of the triangle =
1;
1, 1;
2, 1, 2;
5, 2, 2, 5;
15, 5, 4, 5, 14;
51, 15, 10, 10, 14, 43;
189, 51, 30, 25, 28, 43, 143;
748, 189, 102, 75, 70, 86, 143, 509;
3128, 748, 378, 255, 210, 215, 286, 509, 1922;
13731, 3128, 1496, 945, 714, 645, 715, 1018, 1922, 7651;
62969, 13731, 6256, 3740, 2646, 2193, 2145, 2545, 3844, 7651, 31965;
...
Row 5 = (51, 15, 10, 10, 14, 43), = termwise products of (51, 15, 5, 2, 1, 1) and (1, 1, 2, 5, 14, 43), where A153197 = (1, 2, 5, 15, 51,...); and A006789 = (1, 1, 2, 5, 14, 43,...).

Cf. A006789, A153197

Convolution triangle by rows, T(n,k) = A153197(n-k) * A153198 = a * b, where a = an infinite lower triangular matrix with A153197 prefaced with a 1: (1, 1, 2, 5, 15, 51, 189, 748,...) in every column; and b = an infinite lower triangular matrix with A006789 in the main diagonal and the rest zeros.

A006789 Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Simon Plouffe

nonn

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)
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,...). - Gary W. Adamson, Dec 21 2008
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)

			G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 43*x^5 + 143*x^6 + 509*x^7 + ...

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

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.
David Callan, An involution on set partitions, arXiv:2204.02556 [math.CO], 2022.
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.
Lara 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

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

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 *)

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

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

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
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

Edited by Michael Somos, Oct 06 2003

cp's OEIS Frontend

A153206 Convolution triangle by rows, T(n,k) = A153197(n-k) * A153198.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A006789 Bessel numbers: the number of nonoverlapping partitions of an n-set into equivalence classes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A153198 Triangle read by rows, T(n,k) = A006789(k) if (n=k) otherwise zero. = (A006789 * 0^(n-k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A153199 Triangle read by rows, A007318 * A153198.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula