S2(n, k) = k*S2(n-1, k) + S2(n-1, k-1), n > 1. S2(1, k) = 0, k > 1. S2(1, 1) = 1.
E.g.f.: A(x, y) = e^(y*e^x-y). E.g.f. for m-th column: (e^x-1)^m/m!.
S2(n, k) = (1/k!) * Sum_{i=0..k} (-1)^(k-i)*binomial(k, i)*i^n.
Row sums: Bell number
A000110(n) = Sum_{k=1..n} S2(n, k), n>0.
S(n, k) = Sum (i_1*i_2*...*i_(n-k)) summed over all (n-k)-combinations {i_1, i_2, ..., i_k} with repetitions of the numbers {1, 2, ..., k}. Also S(n, k) = Sum (1^(r_1)*2^(r_2)*...* k^(r_k)) summed over integers r_j >= 0, for j=1..k, with Sum{j=1..k} r_j = n-k. [Charalambides]. -
Wolfdieter Lang, Aug 15 2019.
For asymptotics see Hsu (1948), among other sources.
Sum_{n>=0} S2(n, k)*x^n = x^k/((1-x)(1-2x)(1-3x)...(1-kx)).
Let P(n) = the number of integer partitions of n (
A000041), p(i) = the number of parts of the i-th partition of n, d(i) = the number of distinct parts of the i-th partition of n, p(j, i) = the j-th part of the i-th partition of n, m(i, j) = multiplicity of the j-th part of the i-th partition of n, and Sum_{i=1..P(n), p(i)=m} = sum running from i=1 to i=P(n) but taking only partitions with p(i)=m parts into account. Then S2(n, m) = Sum_{i=1..P(n), p(i)=m} n!/(Product_{j=1..p(i)} p(i, j)!) * 1/(Product_{j=1..d(i)} m(i, j)!). For example, S2(6, 3) = 90 because n=6 has the following partitions with m=3 parts: (114), (123), (222). Their complexions are: (114): 6!/(1!*1!*4!) * 1/(2!*1!) = 15, (123): 6!/(1!*2!*3!) * 1/(1!*1!*1!) = 60, (222): 6!/(2!*2!*2!) * 1/(3!) = 15. The sum of the complexions is 15+60+15 = 90 = S2(6, 3). -
Thomas Wieder, Jun 02 2005
Sum_{k=1..n} k*S2(n,k) = B(n+1)-B(n), where B(q) are the Bell numbers (
A000110). -
Emeric Deutsch, Nov 01 2006
Recurrence: S2(n+1,k) = Sum_{i=0..n} binomial(n,i)*S2(i,k-1). With the starting conditions S2(n,k) = 1 for n = 0 or k = 1 and S2(n,k) = 0 for k = 0 we have the closely related recurrence S2(n,k) = Sum_{i=k..n} binomial(n-1,i-1)*S2(i-1,k-1). -
Thomas Wieder, Jan 27 2007
Representation of Stirling numbers of the second kind S2(n,k), n=1,2,..., k=1,2,...,n, as special values of hypergeometric function of type (n)F(n-1): S2(n,k)= (-1)^(k-1)*hypergeom([ -k+1,2,2,...,2],[1,1,...,1],1)/(k-1)!, i.e., having n parameters in the numerator: one equal to -k+1 and n-1 parameters all equal to 2; and having n-1 parameters in the denominator all equal to 1 and the value of the argument equal to 1. Example: S2(6,k)= seq(evalf((-1)^(k-1)*hypergeom([ -k+1,2,2,2,2,2],[1,1,1,1,1],1)/(k-1)!),k=1..6)=1,31,90,65,15,1. -
Karol A. Penson, Mar 28 2007
Bell_n(x) = Sum_{j=0..n} S2(n,j) * x^j = Sum_{j=0..n} E(n,j) * Lag(n,-x, j-n) = Sum_{j=0..n} (E(n,j)/n!) * (n!*Lag(n,-x, j-n)) = Sum_{j=0..n} E(n,j) * binomial(Bell.(x)+j, n) umbrally where Bell_n(x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m.
For x = 0, the equation gives Sum_{j=0..n} E(n,j) * binomial(j,n) = 1 for n=0 and 0 for all other n. By substituting the umbral compositional inverse of the Bell polynomials, the lower factorial n!*binomial(y,n), for x in the equation, the Worpitzky identity is obtained; y^n = Sum_{j=0..n} E(n,j) * binomial(y+j,n).
Note that E(n,j)/n! = E(n,j)/(Sum_{k=0..n}E(n,k)). Also (n!*Lag(n, -1, j-n)) is
A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to the equation for x=1; n!*Bell_n(1) = n!*Sum_{j=0..n} S2(n,j) = Sum_{j=0..n} E(n,j) * (n!*Lag(n, -1, j-n)).
(Appended Sep 16 2020) For connections to the Bernoulli numbers, extensions, proofs, and a clear presentation of the number arrays involved in the identities above, see my post Reciprocity and Umbral Witchcraft. (End)
n-th row = leftmost column of nonzero terms of
A127701^(n-1). Also, (n+1)-th row of the triangle =
A127701 * n-th row; deleting the zeros. Example:
A127701 * [1, 3, 1, 0, 0, 0, ...] = [1, 7, 6, 1, 0, 0, 0, ...]. -
Gary W. Adamson, Nov 21 2007
The row polynomials are given by D^n(e^(x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf.
A147315 and
A094198. See also
A185422. -
Peter Bala, Nov 25 2011
O.g.f. for the n-th diagonal is D^n(x), where D is the operator x/(1-x)*d/dx. -
Peter Bala, Jul 02 2012
n*i!*S2(n-1,i) = Sum_{j=(i+1)..n} (-1)^(j-i+1)*j!/(j-i)*S2(n,j). -
Leonid Bedratyuk, Aug 19 2012
G.f.: (1/Q(0)-1)/(x*y), where Q(k) = 1 - (y+k)*x - (k+1)*y*x^2/Q(k+1); (continued fraction). -
Sergei N. Gladkovskii, Nov 09 2013
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result as
A007318(x) = P(x).
With Bell(n,x)=B(n,x) defined above, D = d/dx, and :xD:^n = x^n*D^n, a Dobinski formula gives umbrally f(y)^B(.,x) = e^(-x)*e^(f(y)*x). Then f(y)^B(.,:xD:)g(x) = [f(y)^(xD)]g(x) = e^[-(1-f(y)):xD:]g(x) = g[f(y)x].
In particular, for f(y) = (1+y),
A) (1+y)^B(.,x) = e^(-x)*e^((1+y)*x) = e^(x*y) = e^[log(1+y)B(.,x)],
B) (I+dP)^B(.,x) = e^(x*dP) = P(x) = e^[x*(e^M-I)]= e^[M*B(.,x)] with dP =
A132440, M =
A238385-I = log(I+dP), and I = identity matrix, and
C) (1+dP)^(xD) = e^(dP:xD:) = P(:xD:) = e^[(e^M-I):xD:] = e^[M*xD] with action e^(dP:xD:)g(x) = g[(I+dP)*x].
D) P(x)^m = P(m*x), which implies (Sum_{k=1..m} a_k)^j = B(j,m*x) where the sum is umbrally evaluated only after exponentiation with (a_k)^q = B(.,x)^q = B(q,x). E.g., (a1+a2+a3)^2=a1^2+a2^2+a3^2+2(a1*a2+a1*a3+a2*a3) = 3*B(2,x)+6*B(1,x)^2 = 9x^2+3x = B(2,3x).
E) P(x)^2 = P(2x) = e^[M*B(.,2x)] =
A038207(x), the face vectors of the n-Dim hypercubes.
(End)
As a matrix equivalent of some inversions mentioned above,
A008277*
A008275 = I, the identity matrix, regarded as lower triangular matrices. -
Tom Copeland, Apr 26 2014
O.g.f. for the n-th diagonal of the triangle (n = 0,1,2,...): Sum_{k>=0} k^(k+n)*(x*e^(-x))^k/k!. Cf. the generating functions of the diagonals of
A039755. Also cf.
A112492. -
Peter Bala, Jun 22 2014
Floor(1/(-1 + Sum_{n>=k} 1/S2(n,k))) =
A034856(k-1), for k>=2. The fractional portion goes to zero at large k. -
Richard R. Forberg, Jan 17 2015
Let x_(n), called a factorial term (Boole, 1970) or a factorial polynomial (Elaydi, 2005: p. 60), denote the falling factorial Product_{k=0..n-1} (x-k). Then, for n >= 1, x_(n) = Sum_{k=1..n}
A008275(n,k) * x^k, x^n = Sum_{k=1..n} T(n,k) * x_(k), where
A008275(n,k) are Stirling numbers of the first kind.
For n >= 1, the row sums yield the exponential numbers (or Bell numbers): Sum_{k=1..n} T(n,k) =
A000110(n), and Sum_{k=1..n} (-1)^(n+k) * T(n,k) = (-1)^n * Sum_{k=1..n} (-1)^k * T(n,k) = (-1)^n *
A000587(n), where
A000587 are the complementary Bell numbers. (End)
O.g.f. for the m-th column: x^m/(Product_{j=1..m} 1-j*x). -
Daniel Checa, Aug 25 2022
S2(n,k) ~ (k^n)/k!, for fixed k as n->oo. -
Daniel Checa, Nov 08 2022
S2(2n+k, n) ~ (2^(2n+k-1/2) * n^(n+k-1/2)) / (sqrt(Pi*(1-c)) * exp(n) * c^n * (2-c)^(n+k)), where c = -LambertW(-2 * exp(-2)). -
Miko Labalan, Dec 21 2024
For a general proof of the formulas below via generating functions, see Mathematics Stack Exchange link.
Recursion for the n-th row (independently of other rows): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} (j-2)!*binomial(-k,j)*T(n,k+j-1) for 1 <= k < n with T(n,n) = 1 (see Fedor Petrov link).
Recursion for the k-th column (independently of other columns): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} binomial(n,j)*T(n-j+1,k)*(-1)^j for 1 <= k < n with T(n,n) = 1. (End)
Comments