

A019538


Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).


153



1, 1, 2, 1, 6, 6, 1, 14, 36, 24, 1, 30, 150, 240, 120, 1, 62, 540, 1560, 1800, 720, 1, 126, 1806, 8400, 16800, 15120, 5040, 1, 254, 5796, 40824, 126000, 191520, 141120, 40320, 1, 510, 18150, 186480, 834120, 1905120, 2328480, 1451520, 362880, 1, 1022, 55980, 818520, 5103000, 16435440, 29635200, 30240000, 16329600, 3628800
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Number of ways n labeled objects can be distributed into k nonempty parcels. Also number of special terms in n variables with maximal degree k.
In older terminology these are called differences of 0.  Michael Somos, Oct 08 2003
Number of surjections (onto functions) from an nelement set to a kelement set.
Also coefficients (in ascending order) of socalled ordered Bell polynomials.
(k1)!*Stirling2(n,k1) is the number of chain topologies on an nset having k open sets [Stephen].
Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162).  Mitch Harris, Jan 16 2007
Correction of comment before: Number of (nk)dimensional 'faces' of the permutohedron of order n (an (n1)dimensional polytope).  Tilman Piesk, Oct 29 2014
This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourthorder term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(5) * {24 a(1)^4  36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2  a(4) a(0)^3}. The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0D faces), 36 edges (1D faces), 6 squares (2D faces), 8 hexagons (2D faces) and 1 3D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron.  Tom Copeland, Sep 29 2008, Oct 07 2008
Further to the comments of Tom Copeland above, the permutohedron of type A_3 can be taken as the truncated octahedron. Its dual is the tetrakis hexahedron, a simplicial polyhedron, with fvector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p. 21]. The corresponding hvectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of fvectors for type B and type D permutohedra respectively.  Peter Bala, Oct 26 2008
Since T(n,k) counts surjective functions and surjective functions are "consistent", T(n,k) satisfies a binomial identity, namely, T(n,x+y) = Sum_{j=0..n} C(n,j)*T(j,x)*T(nj,y). For definition of consistent functions and a generalized binomial identity, see "Toy stories and combinatorial identities" in the link section below.  Dennis P. Walsh, Feb 24 2012
T(n,k) is the number of labeled forests on n+k vertices satisfying the following two conditions: (i) each forest consists of exactly k rooted trees with roots labeled 1, 2, ..., k; (ii) every root has at least one child vertex.  Dennis P. Walsh, Feb 24 2012
The triangle is the inverse binomial transform of triangle A028246, deleting the left column and shifting up one row.  Gary W. Adamson, Mar 05 2012
See A074909 for associations among this array and the Bernoulli polynomials and their umbral compositional inverses.  Tom Copeland, Nov 14 2014
E.g.f. for the shifted signed polynomials is G(x,t) = (e^t1)/[1+(1+x)(e^t1)] = 1(1+x)(e^t1) + (1+x)^2(e^t1)^2  ... (see also A008292 and A074909), which has the infinitesimal generator g(x,u)d/du = [(1x*u)(1(1+x)u)]d/du, i.e., exp[t*g(x,u)d/du]u eval. at u=0 gives G(x,t), and dG(x,t)/dt = g(x,G(x,t)). The compositional inverse is log((1xt)/(1(1+x)t)). G(x,t) is a generating series associated to the generalized Hirzebruch genera. See the G. Rzadowski link for the relation of the derivatives of g(x,u) to solutions of the Riccatt differential equation, soliton solns. to the KdV equation, and the Eulerian and Bernoulli numbers. In addition A145271 connects products of derivatives of g(x,u) and the refined Eulerian numbers to the inverse of G(x,t), which gives the normalized, reverse face polynomials of the simplices (A135278, divided by n+1). See A028246 for the generator g(x,u)d/dx.  Tom Copeland, Nov 21 2014
For connections to toric varieties and Eulerian polynomials, see the Dolgachev and Lunts and the Stembridge links.  Tom Copeland, Dec 31 2015
See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra.  Tom Copeland, Nov 14 2016
T(n, k) appears in a Worpitzky identity relating monomials to binomials: x^n = Sum_{k=1..n} T(n, k)*binomial(x,k), n >= 1. See eq. (11.) of the Worpitzky link on p. 209. The relation to the Eulerian numbers is given there in eqs. (14.) and (15.). See the formula below relating to A008292. See also Graham et al. eq. (6.10) (relating monomials to falling factorials) on p. 248 (2nd ed. p. 262). The Worpitzky identity given in the Graham et al. reference as eq. (6.37) (2nd ed. p. 269) is eq. (5.), p. 207, of Worpitzky.  Wolfdieter Lang, Mar 10 2017
T(n, m) is also the number of minimum clique coverings and minimum matchings in the complete bipartite graph K_{m,n}.  Eric W. Weisstein, Apr 26 2017
From the Hasan and Franco and Hasan papers: The mpermutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5cell. The first three are wellknown from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)permutohedron. Relations to toric CalabiYau Kahler manifolds are also discussed.  Tom Copeland, May 14 2020
Number of n X k binary matrices with row sums = 1 and no zero columns. These matrices are a subset of the matrices defining A183109.
The distribution into parcels in the leading comment can be regarded as a covering of an nelement set by k disjunct nonempty subsets. For the nondisjunct case see A183109. (End)


REFERENCES

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 89, ex. 1; also p. 210.
Miklos Bona, Combinatorics of Permutations, Chapman and Hall,2004, p.12.
G. Boole, A Treatise On The Calculus of Finite Differences, Dover Publications, 1960, p. 20.
H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, 1989, p. 155. Also eqs.(6.10) and (6.37).
Kiran S. Kedlaya and Andrew V. Sutherland Computing L Series of Hyperelliptic Curves in Algorithmic Number Theory Lecture Notes in Computer Science Volume 5011/2008
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.6.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
J. F. Steffensen, Interpolation, 2nd ed., Chelsea, NY, 1950, see p. 54.
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.
E. Whittaker and G. Robinson, The Calculus of Observations, Blackie, London, 4th ed., 1949; p. 7.


LINKS

Xavier Bultel, Jannik Dreier, Matthieu Giraud, Marie Izaute, Timothée Kheyrkhah, Pascal Lafourcade, Dounia Lakhzoum, Vincent Marlin and Ladislav Motá, Security Analysis and Psychological Study of Authentication Methods with PIN Codes, RCIS 2018  IEEE 12th International Conference on Research Challenges in Information Science, 2018.
Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 20162017.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257260. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Matching


FORMULA

T(n, k) = k*(T(n1, k1)+T(n1, k)) with T(0, 0) = 1 [or T(1, 1) = 1].  Henry Bottomley, Mar 02 2001
E.g.f.: (y*(exp(x)1)  exp(x))/(y*(exp(x)1)  1).  Vladeta Jovovic, Jan 30 2003
Equals [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] where DELTA is Deléham's operator defined in A084938.
T(n, k) = Sum_{j=0..k} (1)^(kj)*j^n*binomial(k, j).  Mario Catalani (mario.catalani(AT)unito.it), Nov 28 2003. See Graham et al., eq. (6.19), p. 251. For a proof see Bert Seghers, Jun 29 2013.
Sum_{k=0..n} T(n, k)(1)^(nk) = 1, Sum_{k=0..n} T(n, k)(1)^k = (1)^n.  Mario Catalani (mario.catalani(AT)unito.it), Dec 11 2003
O.g.f. for nth row: polylog(n, x/(1+x))/(x+x^2).  Vladeta Jovovic, Jan 30 2005
O.g.f. as a continued fraction: 1/(1  x*t/(1  (x + 1)*t/(1  2*x*t/(1  2*(x + 1)*t/(1  ...))))) = 1 + x*t + (x + 2*x^2)*t^2 + (x + 6*x^2 + 6*x^3)*t^3 + ... .
The row polynomials R(n,x), which begin R(1,x) = x, R(2,x) = x + 2*x^2, R(3,x) = x + 6*x^2 + 6*x^3, satisfy the recurrence x*d/dx ((x + 1)*R(n,x)) = R(n+1,x). It follows that the zeros of R(n,x) are real and negative (apply Corollary 1.2 of [Liu and Wang]).
Since this is the triangle of fvectors of the (simplicial complexes dual to the) type A permutohedra, whose hvectors form the Eulerian number triangle A008292, the coefficients of the polynomial (x1)^n*R(n,1/(x1) give the nth row of A008292. For example, from row 3 we have x^2 + 6*x + 6 = 1 + 4*y + y^2, where y = x + 1, producing [1,4,1] as the third row of A008292. The matrix product A008292 * A007318 gives the mirror image of this triangle (see A090582).
For n,k >= 0, T(n+1,k+1) = Sum_{j=0..k} (1)^(kj)*binomial(k,j)*[(j+1)^(n+1)  j^(n+1)]. The matrix product of Pascal's triangle A007318 with the current array gives (essentially) A047969. This triangle is also related to triangle A047969 by means of the Stransform of [Hetyei], a linear transformation of polynomials whose value on the basis monomials x^k is given by S(x^k) = binomial(x,k). The Stransform of the shifted nth row polynomial Q(n,x) := R(n,x)/x is S(Q(n,x)) = (x+1)^n  x^n. For example, from row 3 we obtain S(1 + 6*x + 6*x^2) = 1 + 6*x + 6*x*(x1)/2 = 1 + 3*x + 3*x^2 = (x+1)^3  x^3. For fixed k, the values S(Q(n,k)) give the nonzero entries in column (k1) of the triangle A047969 (the Hilbert transform of the Eulerian numbers). (End)
T(n,k) = Sum_{i=1..k} A(n,i)*Binomial(ni,ki) where A(n,i) is the number of npermutations that have i ascending runs, A008292.
With e.g.f.. A(x,t)= 1 + 1/(1+t*(1exp(x)), the comp. inverse in x is
B(x,t) = log(((1+t)/t)  1/(t(1+x))).
With h(x,t) = 1/(dB/dx)= (1+x)((1+t)(1+x)1), the row polynomial P(n,t) is given by (h(x,t)*d/dx)^n x, eval. at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t), with P(0,t)=0.
(A factor of 1/n! was removed by Copeland on Aug 25 2016.) (End)
The term linear in x of [x*h(d/dx,t)]^n 1 gives the nth row polynomial. (See A134685.)  Tom Copeland, Nov 07 2011
Row polynomials are given by D^n(1/(1x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx.  Peter Bala, Nov 25 2011
T(n,x+y) = Sum_{j=0..n} binomial(n,j)*T(j,x)*T(nj,y).  Dennis P. Walsh, Feb 24 2012
Let P be a RotaBaxter operator of weight 1 satisfying the identity P(x)*P(y) = P(P(x)*y) + P(x*P(y)) + P(x*y). Then P(1)^2 = P(1) + 2*P^2(1). More generally, Guo shows that P(1)^n = Sum_{k=1..n} T(n,k)*P^k(1).  Peter Bala, Jun 08 2012
T(n, k) = Sum_{j=0..k} (1)^j*binomial(k, j)*(kj)^n. [M. Catalani's reindexed formula from Nov 28 2003] Proof: count the surjections of [n] onto [k] with the inclusionexclusion principle, as an alternating sum of the number of functions from [n] to [kj].  Bert Seghers, Jun 29 2013
nth row polynomial = 1/(1 + x)*( Sum_{k>=0} k^n*(x/(1 + x))^k ), valid for x in the open interval (1/2, inf). See Tanny link. Cf. A145901.  Peter Bala, Jul 22 2014
Sum_{n>=0} n^k*a^n = Sum_{i=1..k} (a / (1  a))^i * T(k, i)/(1a) for a < 1.  David A. Corneth, Mar 09 2015
The row polynomials R(n,x) satisfy (1 + x)*R(n,x) = (1)^n*x*R(n,(1 + x)).
For a fixed integer k, the expansion of the function A(k,z) := exp( Sum_{n >= 1} R(n,k)*z^n/n ) has integer coefficients and satisfies the functional equation A(k,z)^(k + 1) = BINOMIAL(A(k,z))^k, where BINOMIAL(F(z))= 1/(1  z)*F(z/(1  z)) denotes the binomial transform of the o.g.f. F(z). Cf. A145901. For cases see A084784 (k = 1), A090352 (k = 2), A090355 (k = 3), A090357 (k = 4), A090362 (k = 5) and A084785 (k = 2 with z > z).
A(k,z)^(k + 1) = A((k + 1),z)^k and hence BINOMIAL(A(k,z)) = A((k + 1),z). (End)
Let a(1) = 1 + x + B(1) = x + 1/2 and a(n) = B(n) = (B.)^n, where B(n) are the Bernoulli numbers defined by e^(B.t) = t / (e^t1), then t / e^(a.t) = t / [(x + 1) * t + exp(B.t)] = (e^t  1) /[ 1 + (x + 1) (e^t  1)] = exp(p.(x)t), where (p.(x))^n = p_n(x) are the shifted, signed row polynomials of this array: p_0(x) = 0, p_1(x) = 1, p_2(x) = (1 + 2 x), p_3(x) = 1 + 6 x + 6 x^2, ... and p_n(x) = n * b(n1), where b(n) are the partition polynomials of A133314 evaluated with these a(n).
Sum_{n > 0} R(n,1/2) x^n/n! = 2 * tanh(x/2), where R(n,x) = Sum_{k = 1..n} T(n,k) x^(k1) are the shifted row polynomials of this entry, so R(n,1/2) = 4 * (2^(n+1)1) B(n+1)/(n+1). (Cf. A000182.)
(End)
Also the Bernoulli numbers are given by B(n) = Sum_{k =1..n} (1)^k T(n,k) / (k+1).  Tom Copeland, Nov 06 2016
G.f. for column k: k! x^k / Product_{i=1..k} (1i*x).  Robert A. Russell, Sep 25 2018


EXAMPLE

The triangle T(n, k) begins:
n\k 1 2 3 4 5 6 7 8 9 10
1: 1
2: 1 2
3: 1 6 6
4: 1 14 36 24
5: 1 30 150 240 120
6: 1 62 540 1560 1800 720
7: 1 126 1806 8400 16800 15120 5040
8: 1 254 5796 40824 126000 191520 141120 40320
9: 1 510 18150 186480 834120 1905120 2328480 1451520 362880
10: 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800

T(4,1) = 1: {1234}. T(4,2) = 14: {1}{234} (4 ways), {12}{34} (6 ways), {123}{4} (4 ways). T(4,3) = 36: {12}{3}{4} (12 ways), {1}{23}{4} (12 ways), {1}{2}{34} (12 ways). T(4,4) = 1: {1}{2}{3}{4} (1 way).


MAPLE

with(combinat): A019538 := (n, k)>k!*stirling2(n, k);


MATHEMATICA

Table[k! StirlingS2[n, k], {n, 9}, {k, n}] // Flatten


PROG

(PARI) {T(n, k) = if( k<0  k>n, 0, sum(i=0, k, (1)^i * binomial(k, i) * (ki)^n))}; /* Michael Somos, Oct 08 2003 */
(Haskell)
a019538 n k = a019538_tabl !! (n1) !! (k1)
a019538_row n = a019538_tabl !! (n1)
a019538_tabl = iterate f [1] where
f xs = zipWith (*) [1..] $ zipWith (+) ([0] ++ xs) (xs ++ [0])
(Sage) def T(n, k): return factorial(k)*stirling_number2(n, k) # Danny Rorabaugh, Oct 10 2015


CROSSREFS

Cf. A000918, A000919, A001117, A001118, A008275, A008279, A048594, A059117, A059515, A074909, A084938.
See also the two closely related triangles: A008277(n, k) = T(n, k)/k! (Stirling numbers of second kind) and A028246(n, k) = T(n, k)/k.
Cf. A033282 'faces' of the associahedron.
Visible in the 3D array in A249042.


KEYWORD



AUTHOR

N. J. A. Sloane, Manfred Goebel (goebel(AT)informatik.unituebingen.de), Dec 11 1996


STATUS

approved



