login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A019538 Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n). 86
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 (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 n-element set to a k-element set.

Also coefficients (in ascending order) of so-called ordered Bell polynomials.

(k-1)!*Stirling2(n,k-1) is the number of chain topologies on an n-set 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

This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth order 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 (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D 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 f-vector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p.21]. The corresponding h-vectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of f-vectors for type B and type D permutohedra respectively. - Peter Bala, Oct 26 2008

Subtriangle of triangle in A131689. - Philippe Deléham, Nov 03 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(C(n,j)*T(j,x)*T(n-j,y), j=0..n). 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

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.

Moussa Benoumhani, The number of topologies on a finite set, Preprint, 2005.

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.

J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.

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.

Delucchi, Emanuele; Pixton, Aaron; Sabalka, Lucas. Face vectors of subdivided simplicial complexes. Discrete Math. 312 (2012), no. 2, 248--257. MR2852583 (2012j:05470). See p. 250. - N. J. A. Sloane, Apr 04 2014

Gabor Hetyei. The Stirling polynomial of a simplicial complex. Discrete and Computational Geometry 35, Number 3, March 2006, pp 437-455. [From Peter Bala, Oct 26 2008]

M. Iida, On Triangle of numbers, Josai Mathematical Monographs, Vol. 5 (2012), 61-70; http://libir.josai.ac.jp/infolib/user_contents/pdf/JOS-13447777-05_61.pdf

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 [From N. J. A. Sloane, Jul 10 2009]

G. Kreweras, Les preordres totaux compatibles avec un ordre partiel. Math. Sci. Humaines No. 53 (1976), 5-30.

E. Mendelson, Races with ties, Math. Mag. 55 (1982), 170-175.

T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.

T. S. Motzkin, Sorting numbers ...: for a link to this paper see A000262.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.

R. Simion, "Convex Polytopes and Enumeration", Adv. in Appl. Math. 18 (1997) pp. 149-180.

J. F. Steffensen, Interpolation, 2nd ed., Chelsea, NY, 1950, see p. 54.

D. Stephen, Topology on finite sets, Amer. Math. Monthly, 75 (1968), 739-741.

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, 4-th ed., 1949; p. 7.

LINKS

T. D. Noe, Rows n=1..100 of triangle, flattened

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010, 2013

J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624, 2013

K. N. Boyadzhiev, A Series transformation formula and related polynomials, Int. J. Math. Math. Sc. 23 (2005), 3849-3866.

S. Fomin, N. Reading, Root systems and generalized associahedra, Lecture notes for IAS/Park-City 2004. [From Peter Bala, Oct 26 2008]

M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)

J. Gubeladze and J. Love, Vertex maps between simplices, cubes, and crosspolytopes, arXiv preprint arXiv:1304.3775, 2013

Li Guo, Baxter algebras, Stirling numbers and partitions, arXiv:math/0402348v1 [math.AC]

G. Hetyei, Face enumeration using generalized binomial coefficients. Online draft version of the Hetyei paper referenced above. [From Peter Bala, Nov 10 2008]

L. Liu, Y. Wang, A unified approach to polynomial sequences with only real zeros [From Peter Bala, Oct 26 2008]

J. Loday, The Multiple Facets of the Associahedron [From Tom Copeland, Sep 29 2008]

K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem

S. M. Tanny, On some numbers related to the Bell numbers, Canad. Math. Bull. Vol. 17 (5), 733-738, 1975

D. P. Walsh, Toy stories and combinatorial identities

Wikipedia, Truncated octahedron [From Peter Bala, Oct 26 2008]

FORMULA

T(n, k) = Sum_{j=0..k} (-1)^j*C(k, j)*(k-j)^n. Proof: count the number of surjections of [n] onto [k] with the inclusion-exclusion principle, as an alternating sum of the number of functions from [n] to [k-j]. [proof added by Bert Seghers, Jun 29 2013]

T(n, k) = k*(T(n-1, k-1)+T(n-1, 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.

Also T(n, k)=Sum((-1)^(k-j)j^n*C(k, j), j=0, .., k). - Mario Catalani (mario.catalani(AT)unito.it), Nov 28 2003

Sum(T(n, k)(-1)^(n-k), k=0, .., n)=1, Sum(T(n, k)(-1)^k, k=0, .., n)=(-1)^n. - Mario Catalani (mario.catalani(AT)unito.it), Dec 11 2003

O.g.f. for n-th row: polylog(-n, x/(1+x))/(x+x^2). - Vladeta Jovovic, Jan 30 2005

E.g.f. 1 / {1 + t[1-exp(x)]}. - Tom Copeland, Oct 13 2008

From Peter Bala, Oct 26 2008: (Start)

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 f-vectors of the (simplicial complexes dual to the) type A permutohedra, whose h-vectors form the Eulerian number triangle A008292, the coefficients of the polynomial (x-1)^n*R(n,1/(x-1) give the n-th 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)^(k-j)*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 S-transform 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 S-transform of the shifted n-th 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*(x-1)/2 = 1 + 3*x + 3*x^2 = (x+1)^3 - x^3. For fixed k, the values S(Q(n,k)) give the non-zero entries in column (k-1) of the triangle A047969 (the Hilbert transform of the Eulerian numbers). (End)

E.g.f. (exp(x)-1)^k=\sum T(n,k)x^n/n!. - Vladimir Kruchinin, Aug 10 2010

T(n,k) = Sum_{i=1...k} A(n,i)*Binomial(n-i,k-i) where A(n,i) is the number of n-permutations that have i ascending runs, A008292.

From Tom Copeland, Oct 11 2011: (Start)

With e.g.f.. A(x,t)= -1 + 1/[1+t*(1-exp(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 (1/n!)(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.  (End)

The term linear in x of [x*h(d/dx,t)]^n 1 gives the n-th row polynomial. (See A134685). - Tom Copeland, Nov 07 2011

Row polynomials are given by D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. - Peter Bala, Nov 25 2011

T(n,x+y)=sum(C(n,j)*T(j,x)*T(n-j,y),j=0..n). - Dennis P. Walsh, Feb 24 2012

Let P be a Rota-Baxter 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

Sum_{i=1..n} (-1)^i*T(n,i)/i = 0, for n>1. - Leonid Bedratyuk, Aug 09 2012

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

EXAMPLE

Triangle begins:

1

1,2

1,6,6

1,14,36,24

1,30,150,240,120

...

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) * (k-i)^n))}; /* Michael Somos, Oct 08 2003 */

(Haskell)

a019538 n k = a019538_tabl !! (n-1) !! (k-1)

a019538_row n = a019538_tabl !! (n-1)

a019538_tabl = iterate f [1] where

   f xs = zipWith (*) [1..] $ zipWith (+) ([0] ++ xs) (xs ++ [0])

-- Reinhard Zumkeller, Dec 15 2013

CROSSREFS

Row sums give A000670. 2nd diagonal is A001286. 3rd diag. is A037960. Maximal terms in rows give A002869. Cf. A008275, A048594.

Cf. A008277, A000918, A001117, A000919, A001118, A059117, A059515, A084938.

Reflected version of A090582. Diagonal is n! (A000142).

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.

Cf. A008292, A047969, A145901, A145902. - Peter Bala, Oct 26 2008

Cf. A028246.

Cf. A233734 (central terms), A008277.

Sequence in context: A202190 A089231 A052296 * A046521 A104684 A060538

Adjacent sequences:  A019535 A019536 A019537 * A019539 A019540 A019541

KEYWORD

nonn,tabl,easy,nice,changed

AUTHOR

N. J. A. Sloane, Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de)

EXTENSIONS

Boole reference from Michael Somos, Oct 10 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 25 19:04 EDT 2014. Contains 244918 sequences.