%I A008292
%S A008292 1,1,1,1,4,1,1,11,11,1,1,26,66,26,1,1,57,302,302,57,1,1,120,1191,2416,
%T A008292 1191,120,1,1,247,4293,15619,15619,4293,247,1,1,502,14608,88234,156190,
%U A008292 88234,14608,502,1,1,1013,47840,455192,1310354,1310354,455192,47840,1013
%N A008292 Triangle of Eulerian numbers T(n,k) read by rows.
%C A008292 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.
%C A008292 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
%C A008292 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
%C A008292 Subtriangle for k>=1 and n>=1 of triangle A123125 . - Philippe DELEHAM
(kolotoko(AT)wanadoo.fr), Oct 22 2006
%C A008292 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.
%C A008292 [ E(.,t)/(1-t)]^n = n!*Lag[n,-P(.,t)/(1-t)] and
%C A008292 [ -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
%C A008292 Comment from Tom Copeland (tcjpn(AT)msn.com), Oct 07 2008: (Start)
%C A008292 G(x,t) = 1/ {1 + [1-exp(x t)]/t} = 1 + 1 x + (2 + t) x^2/2! + (6 + 6t
+ t^2) x^3/3! + ...
%C A008292 gives row polynomials for A090582-- reverse f-polynomials for the permutohedra
(see A019538).
%C A008292 G(x,t-1) = 1 + 1 x + (1 + t) x^2 / 2! + (1 + 4t + t^2) x^3 / 3! + ...
%C A008292 gives row polynomials for A008292, the h-polynomials for permutohedra.
%C A008292 G[(t+1)x,-1/(t+1)] = 1 + (1+ t) x + (1 + 3t + 2 t^2) x^2 / 2! + ...
%C A008292 gives row polynomials for A028246.
%C A008292 (End)
%C A008292 A subexceedant function f on [n] is a map f:[n] -> [n] such that 1 <=
f(i) <= i for all i, 1 <= i <= n. T(n,k) equals the number of subexceedant
functions f of [n] such that the image of f has cardinality k [Mantaci
& Rakotondrajao]. Example T(3,2) = 4: if we identify a subexceedant
function f with the word f(1)f(2)...f(n) then the subexceedant functions
on [3] are 111, 112, 113, 121, 122 and 123 and four of these functions
have an image set of cardinality 2. [From Peter Bala (pbala(AT)toucansurf.com),
Oct 21 2008]
%C A008292 Further to the comments of T. Copeland above, the n-th row of this triangle
is the h-vector of the simplicial complex dual to a permutohedron
of type A_(n-1). The corresponding f-vectors are the rows of A019538.
For example, 1 + 4*x + x^2 = y^2 + 6*y + 6 and 1 + 11*x + 11*x^2
+ x^3 = y^3 + 14*y^2 + 36*y + 24, where x = y + 1, give [1,6,6] and
[1,14,36,24] as the third and fourth rows of A019538. The Hilbert
transform of this triangle (see A145905 for the definition) is A047969.
See A060187 for the triangle of Eulerian numbers of type B (the h-vectors
of the simplicial complexes dual to permutohedra of type B). See
A066094 for the array of h-vectors of type D. For tables of restricted
Eulerian numbers see A144696 - A144699. [From Peter Bala (pbala(AT)toucansurf.com),
Oct 26 2008]
%C A008292 For a natural refinement of A008292 with connections to compositional
inversion and iterated derivatives, see A145271. [From Tom Copeland
(tcjpn(AT)msn.com), Nov 06 2008]
%C A008292 Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), May 24
2009: (Start)
%C A008292 The polynomials E(z,n) = numer(sum((-1)^(n+1)*k^n*z^(k-1), k=1..infinity))
for n >=1 lead directly to the triangle of Eulerian numbers.
%C A008292 (End)
%C A008292 Contribution from Walther Janous (walther.janous(AT)tirol.com), Nov 01
2009: (Start)
%C A008292 The (Eulerian) polynomials e(n,x) = SUM(T(n,k+1)*x^k, k = 0 to n-1) turn
out to be also as the numerators of the closed-form-expressions of
the infinite sums
%C A008292 S(p,x):= SUM((j+1)^p*x^j, j = 0 to infinity), that is
%C A008292 S(p,x) = e(p,x)/(1-x)^(p+1), whenever |x| < 1 and p is a positive integer.
%C A008292 (Please be aware of the inconsistent use of T(n,k) in the part listing
the formulae. I adhere tacitly to the first one.) (End)
%D A008292 L. Carlitz et al., Permutations and sequences with repetions by number
of increases, J. Combin. Theory, 1 (1966), 350-374, p. 351.
%D A008292 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 243.
%D A008292 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied
Tables, Cambridge, 1966, p. 260.
%D A008292 J. Desarmenien and D. Foata, The signed Eulerian numbers. Discrete Math.
99 (1992), no. 1-3, 49-58.
%D A008292 Ehrenborg & Readdy (J Comb. Theory, Series A 81, 121-126).
%D A008292 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.
%D A008292 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.
%D A008292 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley,
Reading, MA, 1990, p. 254.
%D A008292 A. Kerber and K.-J. Thuerlings, Eulerian numbers, Foulkes characters
and Lefschetz characters of S_n, Seminaire Lotharingien, Vol. 8 (1984),
31-36.
%D A008292 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).
%D A008292 P. A. MacMahon, The divisors of numbers, Proc. London Math. Soc., (2)
19 (1920), 305-340; Coll. Papers II, pp. 267-302.
%D A008292 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p.
215.
%D A008292 R. Sedgewick and P. Flajolet, An Introduction to the Analysis of Algorithms,
Addison-Wesley, Reading, MA, 1996.
%D A008292 N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences,
Figure M3416, Academic Press, 1995.
%D A008292 H. S. Wall, Analytic Theory of Continued Fractions, Chelsea, 1973, see
p. 208.
%D A008292 Dominique Foata and Guo-Niu Han, Dimers and new q-tangent numbers, Preprint,
2008.
%H A008292 T. D. Noe, <a href="b008292.txt">Rows 1 to 100 of triangle, flattened.</
a>
%H A008292 D. Barsky, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05barsky.html">
Analyse p-adique et suites classiques de nombres</a>, Sem. Loth.
Comb. B05b (1981) 1-21.
%H A008292 J. Desarmenien and D. Foata, <a href="http://www-irma.u-strasbg.fr/~foata/
paper/pub62.html">The signed Eulerian Numbers</a>
%H A008292 E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/pdf/math.CO/0407326">
Congruences for Catalan and Motzkin numbers and related sequences</
a>, J. Num. Theory 117 (2006), 191-215.
%H A008292 Ira Gessel, <a href="http://www.cs.brandeis.edu/~ira/">The Smith College
diploma problem</a>.
%H A008292 Matthew Hubbard and Tom Roby, <a href="http://binomial.csuhayward.edu/
Euler.html">Pascal's Triangle From Top to Bottom</a>
%H A008292 A. R. Kr\"auter, <a href="http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html">
\"Uber die Permanente gewisser zirkul\"arer Matrizen...</a>
%H A008292 A. F. Labossiere, <a href="http://members.lycos.co.uk/sobalian/index.html">
Sobalian Coefficients</a>.
%H A008292 A. F. Labossiere, <a href="http://members.lycos.co.uk/stereotomography/
index.html">Miscellaneous</a>.
%H A008292 R. Mantaci and F. Rakotondrajao, <a href="http://www.dmtcs.org/volumes/
abstracts/dm040203.abs.html">A permutation representation that knows
what "Eulerian" means</a>, Discrete Mathematics and Theoretical Computer
Science, 4 101-108, (2001)
%H A008292 A. Randrianarivony and J. Zeng, <a href="http://igd.univ-lyon1.fr/home/
zeng/public_html/paper/publication.html">Une famille des polynomes
qui interpole plusieurs suites...</a>, Adv. Appl. Math. 17 (1996),
1-26.
%H A008292 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
EulerianNumber.html">Link to a section of The World of Mathematics.</
a>
%H A008292 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
EulersNumberTriangle.html">Link to a section of The World of Mathematics.</
a>
%H A008292 L. K. Williams, <a href="http://arXiv.org/abs/math.CO/0307271">Enumeration
of totally positive Grassmann cells</a>
%H A008292 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to
rooted trees</a>
%H A008292 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
EulerianNumber.html">Eulerian Number</a>
%H A008292 D. Foata, M. Schutzenberger. <a href="http://www.arXiv.org/abs/math.CO/
0508232">- Theorie Geometrique des Polynomes Euleriens</a>, Lecture
Notes in Math., no.138, Springer Verlag 1970. [From Peter Bala (pbala(AT)toucansurf.com),
Oct 26 2008]
%H A008292 S. Parker, <a href="http://people.brandeis.edu/~gessel/homepage/students/
parkerthesis.pdf">The Combinatorics of Functional Composition and
Inversion</a>, Dissertation, Brandeis Univ. (1993) [From Tom Copeland
(tcjpn(AT)msn.com), Nov 10 2008]
%F A008292 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.
%F A008292 E.g.f.: ( e^(zx) - e^x )/( z*e^x - e^(zx) ).
%F A008292 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
%F A008292 Four characterizations of Eulerian numbers T(i, n) from John Robertson
(jpr2718(AT)aol.com), Sep 02, 2002:
%F A008292 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).
%F A008292 2. T(i, n) = sum_{j=0}^{i} (-1)^j (n+1 combin j) (i-j+1)^n for n>=1,
i>=0.
%F A008292 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.
%F A008292 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.
%F A008292 O.g.f. for n-th row: (1-x)^(n+1)*polylog(-n, x)/x. - Vladeta Jovovic
(vladeta(AT)eunet.rs), Sep 02 2002
%F A008292 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.
%F A008292 Sum_{k = 1..n} T(n, k)*2^k = A000629(n) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr),
Jun 05 2004
%F A008292 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
%F A008292 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)! ].
%F A008292 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 Worpitzky identity is obtained; y^n = sum(j=0,
...,n) E(n,j) * C(y+j,n) .
%F A008292 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)
%F A008292 From the relations between the h- and f-polynomials of permutohedra and
reciprocals of e.g.f.s described in A049019: (t-1)[(t-1)d/dx]^n 1/
(t-exp(x)) evaluated at x=0 gives the n-th Eulerian row polynomial
in t and the n-th row polynomial in (t-1) of A019538 and A090582.
From the Comtet and Copeland references in A139605: [(t+exp(x)-1)d/
dx]^(n+1) x gives pairs of the Eulerian polynomials in t as the coefficients
of x^0 and x^1 in its Taylor series expansion in x. [From Tom Copeland
(tcjpn(AT)msn.com), Oct 05 2008]
%e A008292 Triangle begins:
%e A008292 1;
%e A008292 1,1;
%e A008292 1,4,1;
%e A008292 1,11,11,1;
%e A008292 1,26,66,26,1;
%e A008292 1,57,302,302,57,1;
%e A008292 ...
%o A008292 (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)))
%o A008292 (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))}
%Y A008292 Cf. A014630, A030196, A055325. Row sums give A000142(n).
%Y A008292 Cf. A027656 A084938, A049061, A008275, A008277, A087127.
%Y A008292 Columns 2 through 8: A000295, A000460, A000498, A000505, A000514, A001243,
A001244.
%Y A008292 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
%Y A008292 A019538 (f-vectors type A permutohedra), A047969 (Hilbert transform),
A060187 (h-vectors type B permutohedra), A066094. [From Peter Bala
(pbala(AT)toucansurf.com), Oct 26 2008]
%Y A008292 Sequence in context: A154986 A154983 A156534 this_sequence A157221 A146967
A156049
%Y A008292 Adjacent sequences: A008289 A008290 A008291 this_sequence A008293 A008294
A008295
%K A008292 nonn,tabl,nice,eigen,core,new
%O A008292 1,5
%A A008292 N. J. A. Sloane (njas(AT)research.att.com).
%E A008292 Thanks to Michael Somos for additional comments. Further comments from
Christian G. Bower (bowerc(AT)usa.net), May 12 2000
|
