A123125 Triangle of Eulerian numbers T(n,k), 0 <= k <= n, read by rows.
1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 11, 11, 1, 0, 1, 26, 66, 26, 1, 0, 1, 57, 302, 302, 57, 1, 0, 1, 120, 1191, 2416, 1191, 120, 1, 0, 1, 247, 4293, 15619, 15619, 4293, 247, 1, 0, 1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1, 0, 1, 1013, 47840, 455192, 1310354, 1310354, 455192, 47840, 1013, 1
Offset: 0
Examples
The triangle T(n, k) begins: n\k 0 1 2 3 4 5 6 7 8 9 10... 0: 1 1: 0 1 2: 0 1 1 3: 0 1 4 1 4: 0 1 11 11 1 5: 0 1 26 66 26 1 6: 0 1 57 302 302 57 1 7: 0 1 120 1191 2416 1191 120 1 8: 0 1 247 4293 15619 15619 4293 247 1 9: 0 1 502 14608 88234 156190 88234 14608 502 1 10: 0 1 1013 47840 455192 1310354 1310354 455192 47840 1013 1 ... Reformatted. - _Wolfdieter Lang_, Feb 14 2015 ------------------------------------------------------------------ The width statistic over permutations, n=4. [1, 2, 3, 4] => 3; [1, 2, 4, 3] => 2; [1, 3, 2, 4] => 2; [1, 3, 4, 2] => 2; [1, 4, 2, 3] => 2; [1, 4, 3, 2] => 1; [2, 1, 3, 4] => 3; [2, 1, 4, 3] => 2; [2, 3, 1, 4] => 2; [2, 3, 4, 1] => 3; [2, 4, 1, 3] => 2; [2, 4, 3, 1] => 2; [3, 1, 2, 4] => 3; [3, 1, 4, 2] => 3; [3, 2, 1, 4] => 2; [3, 2, 4, 1] => 3; [3, 4, 1, 2] => 3; [3, 4, 2, 1] => 2; [4, 1, 2, 3] => 4; [4, 1, 3, 2] => 3; [4, 2, 1, 3] => 3; [4, 2, 3, 1] => 3; [4, 3, 1, 2] => 3; [4, 3, 2, 1] => 2; Gives row(4) = [0, 1, 11, 11, 1]. - _Peter Luschny_, Dec 09 2015 ------------------------------------------------------------------ From _Wolfdieter Lang_, Apr 03 2017: (Start) Recurrence: T(5, 3) = (6-3)*T(4, 2) + 3*T(4, 3) = 3*11 + 3*11 = 66. O.g.f. column k=2: (x/(1 - 2*x))*E_x*(x/(1-x)) = (x/(1-x))^2/(1-2*x). E.g.f. column k=2: A(2, x) = x*A(1, x) + x*E(1, x) = x*1 + x*(exp(x)-1) = x*exp(x), hence E(2, x) = (1 + int(x*exp(-x),x ))*exp(2*x) = exp(x)*(exp(x) - (1+x)). See A000295. (End)
References
- L. Comtet, Advanced Combinatorics, Reidel, Holland, 1978, page 245. [Roger L. Bagula, Nov 21 2009]
- Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, 2nd ed.; Addison-Wesley, 1994, p. 268, Row reversed table 268. - Wolfdieter Lang, Apr 03 2017
- Douglas C. Montgomery and Lynwood A. Johnson, Forecasting and Time Series Analysis, MaGraw-Hill, New York, 1976, page 91. - Roger L. Bagula and Gary W. Adamson, Aug 14 2008
Links
- Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
- Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, arXiv preprint arXiv:1105.3043 [math.CO], 2011, J. Int. Seq. 14 (2011) # 11.9.5
- Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Toda Chain Equations, Journal of Integer Sequences, 17 (2014), #14.2.3.
- Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
- Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
- V. Batyrev and M. Blume, The functor of toric varieties associated with Weyl chambers and Losev-Manin moduli spaces, p. 11, arXiv:/0911.3607 [math.AG], 2009. [_Tom Copeland_, Oct 16 2015]
- Anna Borowiec and Wojciech Mlotkowski, New Eulerian numbers of type D, arXiv:1509.03758 [math.CO], 2015.
- Patrick J. Burchell, A Generalisation of Ramanujan's (back of the envelope) Method for Divergent Series, arXiv:2303.14045 math.NT, 2023.
- A. Cohen, Eulerian polynomials of spherical type, Münster J. of Math. 1 (2008). [_Tom Copeland_, Oct 16 2015]
- Tom Copeland, The Elliptic Lie Triad: Ricatti and KdV Equations, Infinigens, and Elliptic Genera
- Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker and Amanda Welch, Homomesies on permutations -- an analysis of maps and statistics in the FindStat database, arXiv:2206.13409 [math.CO], 2022-2023. (Def. 4.20 and Prop. 4.22.)
- FindStat - Combinatorial Statistic Finder, The number of descents of a permutation.
- F. Hirzebruch, Eulerian polynomials, Münster J. of Math. 1 (2008), pp. 9-12.
- P. Hitczenko and S. Janson, Weighted random staircase tableaux, arXiv preprint arXiv:1212.5498 [math.CO], 2012.
- Hsien-Kuei Hwang, Hua-Huai Chern, and Guan-Huei Duh, An asymptotic distribution theory for Eulerian recurrences with applications, arXiv:1807.01412 [math.CO], 2018.
- Svante Janson, Euler-Frobenius numbers and rounding, arXiv preprint arXiv:1305.3512 [math.PR], 2013.
- Katarzyna Kril and Wojciech Mlotkowski, Permutations of Type B with Fixed Number of Descents and Minus Signs, Volume 26(1) of The Electronic Journal of Combinatorics, 2019.
- Wolfdieter Lang, On Sums of Powers of Arithmetic Progressions, and Generalized Stirling, Eulerian and Bernoulli numbers, arXiv:1707.04451 [math.NT], 2017.
- Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 22.
- A. Losev and Y. Manin, New moduli spaces of pointed curves and pencils of flat connections, arXiv preprint arXiv:math/0001003 [math.AG], 2000 (p. 8). - _Tom Copeland_, Oct 16 2015
- Peter Luschny, Permutation Trees
- G. Rzadkowski and M. Urlinska, A Generalization of the Eulerian Numbers, arXiv:1612.06635 [math.CO], 2016.
Crossrefs
Programs
-
Haskell
a123125 n k = a123125_tabl !! n !! k a123125_row n = a123125_tabl !! n a123125_tabl = [1] : zipWith (:) [0, 0 ..] a008292_tabl -- Reinhard Zumkeller, Nov 06 2013
-
Maple
gf := 1/(1 - t*exp(x)): ser := series(gf, x, 12): cx := n -> (-1)^(n + 1)*factor(n!*coeff(ser, x, n)*(t - 1)^(n + 1)): seq(print(seq(coeff(cx(n), t, k), k = 0..n)), n = 0..9); # Peter Luschny, Feb 11 2021 A123125 := proc(n, k) option remember; if k = n then 1 elif k <= 0 or k > n then 0 else k*procname(n-1, k) + (n-k+1)*procname(n-1, k-1) fi end: seq(print(seq(A123125(n, k), k=0..n)), n=0..10); # Peter Luschny, Mar 28 2021 # Alternative (Patrick J. Burchell): t := a -> Statistics:-Difference([0, a]): Trow := k -> (t@@(k+1))([seq(n^k, n = 0..k)]): seq(print(Trow(n)), n = 0..6); # Peter Luschny, Apr 02 2023
-
Mathematica
f[x_, n_] := f[x, n] = (1 - x)^(n + 1)*Sum[k^n*x^k, {k, 0, Infinity}]; Table[CoefficientList[f[x, n], x], {n,0,9}] // Flatten (* Roger L. Bagula, Aug 14 2008 *) t[n_ /; n >= 0, 0] = 1; t[n_, k_] /; k<0 || k>n = 0; t[n_, k_] := t[n, k] = (n-k) t[n-1, k-1] + (k+1) t[n-1, k]; T[n_, k_] := t[n, n-k]; Table[T[n, k], {n,0,10}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 26 2019 *) A123125[n_, k_] := Sum[(-1)^j*(n - j - k + 1)^n * Binomial[n + 1, j], {j, 0, n - k}]; Table[A123125[n, k], {n, 0, 9}, {k, 0, n}] // TableForm (* Peter Luschny, Aug 12 2022 *)
-
Python
from math import isqrt, comb def A123125(n): a = (m:=isqrt(k:=n+1<<1))+(k>m*(m+1)) b = comb(a+1,2)-n return sum(-(b-j)**(a-1)*comb(a,j) if j&1 else (b-j)**(a-1)*comb(a,j) for j in range(b)) # Chai Wah Wu, Nov 13 2024
-
Sage
def statistic_eulerian(pi): if not pi: return 0 h, i, branch, next = 0, len(pi), [0], pi[0] while True: while next < branch[len(branch)-1]: del(branch[len(branch)-1]) current = 0 h += 1 while next > current: i -= 1 if i == 0: return h branch.append(next) current, next = next, pi[i] def A123125_row(n): L = [0]*(n+1) for p in Permutations(n): L[statistic_eulerian(p)] += 1 return L [A123125_row(n) for n in range(7)] # Peter Luschny, Dec 09 2015
Formula
Sum_{k=0..n} T(n,k) = n! = A000142(n).
Sum_{k=0..n} 2^k*T(n,k) = A000629(n).
Sum_{k=0..n} 3^k*T(n,k) = abs(A009362(n+1)).
Sum_{k=0..n} 2^(n-k)*T(n,k) = A000670(n).
Sum_{k=0..n} T(n,k)*3^(n-k) = A122704(n). - Philippe Deléham, Nov 07 2007
G.f.: f(x,n) = (1 - x)^(n + 1)*Sum_{k>=0} k^n*x^k. - Roger L. Bagula and Gary W. Adamson, Aug 14 2008. f is not the g.f. of the triangle, it is the polynomial of row n. See an Apr 03 2017 comment above - Wolfdieter Lang, Apr 03 2017
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000142(n), A000629(n), A123227(n), A201355(n), A201368(n) for x = 0, 1, 2, 3, 4, 5 respectively. - Philippe Deléham, Dec 01 2011
E.g.f. (1-t)/(1-t*exp((1-t)x)). A123125 * A007318 = A130850 = unsigned A075263, related to reversed A028246. A007318 * A123125 = A046802. Evaluating the row polynomials at -1, giving the alternating-sign row sum, generates A009006. - Tom Copeland, Oct 14 2015
From Wolfdieter Lang, Apr 03 2017: (Start)
T(n, k) = A173018(n, n-k), 0 <= k <= n. Row reversed Euler's triangle. See Graham et al., p. 268.
Recurrence (from A173018): T(n, 0) = 1 if n=0 else 0; T(n, k) = 0 if n < k and T(n, k) = (n+1-k)*T(n-1, k-1) + k*T(n-1, k) else.
T(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(n-j, k-j)*S2(n, j)*j!, 0 <= k <= n, else 0. For S2(n, k)*k! see A131689.
The recurrence for the o.g.f. of the sequence of column k is
G(k, x) = (x/(1 - k*x))*(E_x - (k-2))*G(k-1, x), with the Euler operator E_x = x*d_x, for k >= 1, with G(0, x) = 1. (Proof from the recurrence of T(n, k)).
The e.g.f of the sequence of column k is found from E(k, x) = (1 + int(A(k, x),x)*exp(-k*x))*exp(k*x), k >= 1, with the recurrence
A(k, x) = x*A(k-1, x) +(1 + (1-k)*(1-x))*E(k-1, x) for k >= 1, with A(0,x)= 0. (Proof from the recurrence of T(n, k)). (End)
T(n, k) = Sum_{j=0..n-k} (-1)^j*(n-j-k+1)^n*binomial(n + 1, j). - Peter Luschny, Aug 12 2022
G.f.: Sum_{m >= 0} x^m/(1/(1-x)-m*t). - Mamuka Jibladze, Mar 12 2025
Comments