A049020 Triangle of numbers a(n,k), 0 <= k <= n: number of set partitions of {1,2,...,n} in which exactly k of the blocks have been distinguished.
1, 1, 1, 2, 3, 1, 5, 10, 6, 1, 15, 37, 31, 10, 1, 52, 151, 160, 75, 15, 1, 203, 674, 856, 520, 155, 21, 1, 877, 3263, 4802, 3556, 1400, 287, 28, 1, 4140, 17007, 28337, 24626, 11991, 3290, 490, 36, 1, 21147, 94828, 175896, 174805, 101031, 34671, 6972, 786, 45, 1
Offset: 0
Examples
Triangle begins: 1; 1, 1; 2, 3, 1; 5, 10, 6, 1; 15, 37, 31, 10, 1; ... From _Paul Barry_, Jan 12 2009: (Start) Production array begins 1, 1; 1, 2, 1; 0, 2, 3, 1; 0, 0, 3, 4, 1; 0, 0, 0, 4, 5, 1; ... (End)
Links
- Alois P. Heinz, Rows n = 0..140, flattened
- M. Aigner, A characterization of the Bell numbers, Discr. Math., 205 (1999), 207-210.
- Paul Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
- Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See p. 11.
- Marc Chamberland, Factored matrices can generate combinatorial identities, Linear Algebra and its Applications, Volume 438, Issue 4, 15 Feb. 2013, pp. 1667-1677.
- J. East and R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359 [math.GR], 2014.
- Tom Halverson and Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
- Aoife Hennessy and Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2.
- Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.
- W. F. Lunnon et al., Arithmetic properties of Bell numbers to a composite modulus I, Acta Arith., 35 (1979), 1-16.
- J. Riordan, Letter, Oct 31 1977. The array is on the second page.
Crossrefs
Programs
-
Maple
a:= proc(n, k) option remember; `if`(k<0 or k>n, 0, `if`(n=0, 1, a(n-1, k-1) +(k+1)*(a(n-1, k) +a(n-1, k+1)))) end: seq(seq(a(n, k), k=0..n), n=0..15); # Alois P. Heinz, Nov 30 2012 -
Mathematica
a[n_, k_] = Sum[StirlingS2[n, i]*Binomial[i, k], {i, 0, n}]; Flatten[Table[a[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Aug 29 2011, after Vladeta Jovovic *) -
PARI
T(n,k)=if(k<0 || k>n,0,n!*polcoeff(polcoeff(exp((1+y)*(exp(x+x*O(x^n))-1)),n),k))
-
Sage
def A049020_triangle(dim): M = matrix(ZZ, dim, dim) for n in (0..dim-1): M[n, n] = 1 for n in (1..dim-1): for k in (0..n-1): M[n, k] = M[n-1, k-1]+(k+1)*M[n-1, k]+(k+1)*M[n-1, k+1] return M A049020_triangle(9) # Peter Luschny, Sep 19 2012
Formula
a(n,k) = a(n-1, k-1) + (k+1)*a(n-1, k) + (k+1)*a(n-1, k+1), n >= 1.
a(n,k) = Sum_{i=0..n} Stirling2(n,i)*binomial(i,k). - Vladeta Jovovic, Jan 27 2001
E.g.f. for the k-th column is (1/k!)*(exp(x)-1)^k*exp(exp(x)-1). - Vladeta Jovovic, Jan 27 2001
G.f.: 1/(1-x-xy-x^2(1+y)/(1-2x-xy-2x^2(1+y)/(1-3x-xy-3x^2(1+y)/(1-4x-xy-4x^2(1+y)/(1-... (continued fraction). - Paul Barry, Apr 29 2009
E.g.f.: exp((y+1)*(exp(x)-1)). - Geoffrey Critzer, Nov 30 2012
Note that A244489 (which is essentially the same triangle) has the formula T(n,k) = Sum_{j=k..n} binomial(n,j)*Stirling_2(j,k)*Bell(n-j), where Bell(n) = A000110(n), for n >= 1, 0 <= k <= n-1. - N. J. A. Sloane, May 17 2016
a(2n,n) = A245109(n). - Alois P. Heinz, Aug 23 2017
Empirical: a(n,k) = p(1^n)[st(1^k)] (see A002872 for notation). - Andrey Zabolotskiy, Oct 17 2017
a(n,k) = Sum_{j=0..k} (-1)^(k-j)*A046716(k, k-j)*Bell(n + j)/k!. - Peter Luschny, Dec 06 2023
Extensions
More terms from James Sellers.
Better definition from Geoffrey Critzer, Nov 30 2012.
Comments