|
|
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.
|
|
21
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Triangle a(n,k) read by rows; given by [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938.
Exponential Riordan array [exp(exp(x)-1), exp(x)-1]. - Paul Barry, Jan 12 2009
Equal to A048993*A007318. - Philippe Deléham, Oct 31 2011
|
|
LINKS
|
Alois P. Heinz, Rows n = 0..140, flattened
M. Aigner, A characterization of the Bell numbers, Discr. Math., 205 (1999), 207-210.
P. Barry, Constructing Exponential Riordan Arrays from Their A and Z Sequences, Journal of Integer Sequences, 17 (2014), #14.2.6.
J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359 [math.GR], 2014.
Tom Halverson, Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
A. Hennessy, P. 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.
|
|
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
|
|
EXAMPLE
|
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)
|
|
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 *)
|
|
PROG
|
(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
|
|
CROSSREFS
|
First column gives A000110, second column = A005493.
Third column = A003128, row sums = A001861, A059340.
See A244489 for another version of this triangle.
Cf. A245109.
Sequence in context: A060693 A172381 A089302 * A299105 A307899 A144634
Adjacent sequences: A049017 A049018 A049019 * A049021 A049022 A049023
|
|
KEYWORD
|
nonn,tabl,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane
|
|
EXTENSIONS
|
More terms from James A. Sellers.
Better definition from Geoffrey Critzer, Nov 30 2012.
|
|
STATUS
|
approved
|
|
|
|