1,5

Coefficients of Eulerian polynomials. Number of permutations of n objects with k-1 rises. Number of increasing rooted trees with n+1 nodes and k leaves.

T(n,k)=number of permutations of [n] with k runs. T(n,k)=number of permutations of [n] requiring k readings (see the Knuth reference). T(n,k)=number of permutations of [n] having k distinct entries in its inversion table. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 09 2004

T(n,k) = number of ways to write the Coxeter element s_{e1}s_{e1-e2}s_{e2-e3}s_{e3-e4}...s_{e_{n-1}-e_n} of the reflection group of type B_n, using s_{e_k} and as few reflections of the form s_{e_i+e_j}, where i = 1, 2, ..., n and j is not equal to i, as possible. - Pramook Khungurn (pramook(AT)mit.edu), Jul 07 2004

Subtriangle for k>=1 and n>=1 of triangle A123125 . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 22 2006

Comment from Stefano Zunino, Oct 25 2006: T(n,k)/n! also represents the n-dimensional volume of the portion of the n-dimensional hyper-cube cut by the (n-1)-dimensional hyperplanes x_1 + x_2 + ... x_n = k, x_1 + x_2 + ... x_n = k-1; or, equivalently, it represents the probability that the sum of n independent random variables with uniform distribution between 0 and 1 is between k-1 and k.

[ E(.,t)/(1-t)]^n = n!*Lag[n,-P(.,t)/(1-t)] and

[ -P(.,t)/(1-t)]^n = n!*Lag[n, E(.,t)/(1-t)] umbrally comprise a combinatorial Laguerre transform pair, where E(n,t) are the Eulerian polynomials and P(n,t) are the polynomials in A131758. - Tom Copeland (tcjpn(AT)msn.com), Sep 30 2007

L. Carlitz et al., Permutations and sequences with repetions by number of increases, J. Combin. Theory, 1 (1966), 350-374, p. 351.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 243.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.

J. Desarmenien and D. Foata, The signed Eulerian numbers. Discrete Math. 99 (1992), no. 1-3, 49-58.

Ehrenborg & Readdy (J Comb. Theory, Series A 81, 121-126).

D. Foata, Distributions eule'riennes et mahoniennes sur le group des permutations, pp. 27-49 of M. Aigner, editor, Higher Combinatorics, Reidel, Dordrecht, Holland, 1977.

Ghislain R. Franssens, On a Number Pyramid Related to the Binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 254.

A. Kerber and K.-J. Thuerlings, Eulerian numbers, Foulkes characters and Lefschetz characters of S_n, Seminaire Lotharingien, Vol. 8 (1984), 31-36.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1998, Vol. 3, p. 47, (exercise 5.1.4 Nr. 20) and p. 605 (solution).

P. A. MacMahon, The divisors of numbers, Proc. London Math. Soc., (2) 19 (1920), 305-340; Coll. Papers II, pp. 267-302.

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

R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Figure M3416, Academic Press, 1995.

H. S. Wall, Analytic Theory of Continued Fractions, Chelsea, 1973, see p. 208.

T. D. Noe, Rows 1 to 100 of triangle, flattened.

D. Barsky, Analyse p-adique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 1-21.

J. Desarmenien and D. Foata, The signed Eulerian Numbers

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

Ira Gessel, The Smith College diploma problem.

Matthew Hubbard and Tom Roby, Pascal's Triangle From Top to Bottom

A. R. Kr\"auter, \"Uber die Permanente gewisser zirkul\"arer Matrizen...

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

R. Mantaci and F. Rakotondrajao, A permutation representation that knows what "Eulerian" means, Discrete Mathematics and Theoretical Computer Science, 4 101-108, (2001)

A. Randrianarivony and J. Zeng, Une famille des polynomes qui interpole plusieurs suites..., Adv. Appl. Math. 17 (1996), 1-26.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

L. K. Williams, Enumeration of totally positive Grassmann cells

Index entries for sequences related to rooted trees

T(n, k)=k*T(n-1, k)+(n-k+1)*T(n-1, k-1), T(1, 1)=1. T(n, k)=Sum (-1)^j*(k-j)^n*C(n+1, j), j=0..k.

E.g.f.: ( e^(zx) - e^x )/( z*e^x - e^(zx) ).

For a column listing, n-th term: T(c, n)=c^(n+c-1)+sum(i=1, c-1, (-1)^i/i!*(c-i)^(n+c-1)*prod(j=1, i, n+c+1-j)) - Randall L. Rathbun (randallr(AT)abac.com), Jan 23 2002

Four characterizations of Eulerian numbers T(i, n) from John Robertson (jpr2718(AT)aol.com), Sep 02, 2002:

1. T(0, n)=1 for n>=1, T(i, 1)=0 for i>=1, T(i, n) = (n-i)T(i-1, n-1) + (i+1)T(i, n-1).

2. T(i, n) = sum_{j=0}^{i} (-1)^j (n+1 combin j) (i-j+1)^n for n>=1, i>=0.

3. Let Cn be the unit cube in R^n with vertices (e_1, e_2, ..., e_n) where each e_i is 0 or 1 and all 2^n combinations are used. Then T(i, n)/n! is the volume of Cn between the hyperplanes x_1 + x_2 + ... + x_n = i and x_1 + x_2 + ... + x_n = i+1. Hence T(i, n)/n! is the probability that i <= X_1 + X_2 + ... + X_n < i+1 where the X_j are independent uniform [0, 1] distributions. - See Ehrenborg & Readdy reference.

4. Let f(i, n) = T(i, n)/n!. The f(i, n) are the unique coefficients so that (1/(r-1)^(n+1)) sum_{i=0}^{n-1} f(i, n) r^{i+1} = sum_{j=0}^{infinity} (j^n)/(r^j) whenever n>=1 and abs(r)>1.

O.g.f. for n-th row: (1-x)^(n+1)*polylog(-n, x)/x. - Vladeta Jovovic (vladeta(AT)Eunet.yu), Sep 02 2002

Triangle T(n, k), n>0 and k>0, read by rows; given by [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] (positive integers interspersed with 0's) where DELTA is Deleham's operator defined in A084938.

Sum_{k = 1..n} T(n, k)*2^k = A000629(n) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Jun 05 2004

a(n,k) = Sum_{i=1..n} (-1)^(n-i) * (i^k) * C(k+1,n-i). - Andre F. Labossiere (boronali(AT)laposte.net), Aug 16 2006

Formulae and comments from Tom Copeland, Oct 10 2007 (Start): 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) * C(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; Lag(n,x,m), the associated Laguerre polynomials of order m; and C(x,y) = x!/[ y!*(x-y)! ].

For x = 0, the equation gives sum(j=0,...,n) E(n,j) * C(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!*C(y,n), for x in the equation, the Worpitsky identity is obtained; y^n = sum(j=0,...,n) E(n,j) * C(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)]} . (End)

Triangle begins:

1;

1,1;

1,4,1;

1,11,11,1;

1,26,66,26,1;

1,57,302,302,57,1;

...

(PARI) T(n, k)=if(k<1|k>n, 0, if(n==1, 1, k*T(n-1, k)+(n-k+1)*T(n-1, k-1)))

(PARI) {T(n, k)=sum(j=0, k, (-1)^j*(k-j)^n*binomial(n+1, j))} {A008292(c, n)=c^(n+c-1)+sum(i=1, c-1, (-1)^i/i!*(c-i)^(n+c-1)*prod(j=1, i, n+c+1-j))}

Cf. A014630, A030196, A055325. Row sums give A000142(n).

Cf. A027656 A084938, A049061, A008275, A008277, A087127.

Columns 2 through 8: A000295, A000460, A000498, A000505, A000514, A001243, A001244.

Cf. A062253, noting that A008292 gives the (unsigned) polynomial coefficients of (kn). Also note that taking alternating differences of rows with an odd number of terms (e.g. 1=1, -1+4-1=2, 1-26+66-26+1=16, -1+120-1191+2416-1191+120-1=272 etc.) gives A000182. - Henry Bottomley (se16(AT)btinternet.com), Jun 15 2001

Adjacent sequences: A008289 A008290 A008291 this_sequence A008293 A008294 A008295

Sequence in context: A090981 A087903 A112500 this_sequence A101919 A055106 A080416

nonn,tabl,nice,eigen,core

njas

Thanks to Michael Somos for additional comments. Further comments from Christian G. Bower (bowerc(AT)usa.net), May 12 2000