A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).
1, 1, 1, 2, 1, 8, 1, 22, 16, 1, 52, 136, 1, 114, 720, 272, 1, 240, 3072, 3968, 1, 494, 11616, 34304, 7936, 1, 1004, 40776, 230144, 176896, 1, 2026, 136384, 1328336, 2265344, 353792, 1, 4072, 441568, 6949952, 21953408, 11184128, 1, 8166, 1398000, 33981760
Offset: 1
Examples
Triangle begins: 1; 1, 1, 2; 1, 8, 1, 22, 16; 1, 52, 136, 1, 114, 720, 272; ... From _Peter Bala_, Jun 26 2012: (Start) n = 4: the 9 weighted plane increasing 0-1-2 trees on 4 vertices are .................................................................. ..4............................................................... ..|............................................................... ..3..........4...4...............4...4...............3...3........ ..|........./.....\............./.....\............./.....\....... ..2....2...3.......3...2...3...2.......2...3...4...2.......2...4.. ..|.....\./.........\./.....\./.........\./.....\./.........\./... ..1...(t)1........(t)1....(t)1........(t)1....(t)1........(t)1.... .................................................................. ..3...4...4...3................................................... ...\./.....\./.................................................... .(t)2....(t)2..................................................... ....|.......|..................................................... ....1.......1..................................................... Hence R(4,t) = 1 + 8*t. (End)
References
- D. Foata and V. Strehl, "Euler numbers and variations of permutations", in Colloquio Internazionale sulle Teorie Combinatorie, Rome, September 1973, (Atti dei Convegni Lincei 17, Rome, 1976), 129.
- Guoniu Han, Frédéric Jouhet, Jiang Zeng, Two new triangles of q-integers via q-Eulerian polynomials of type A and B, Ramanujan J (2013) 31:115-127, DOI 10.1007/s11139-012-9389-3
- T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 4.
Links
- Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
- François Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
- Leonard Carlitz and Richard Scoville, Generalized Eulerian numbers: combinatorial applications, Journal für die reine und angewandte Mathematik 265 (1974), 111.
- Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
- Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
- Dominique Foata and Marcel-Paul Schützenberger, Théorie géometrique des polynômes eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math. 138 (1970), 81-83.
- Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
- Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of descent polynomials and the change of grammars, arXiv:1802.02861 [math.CO], 2018.
- Shi-Mei Ma, Jianfeng Wang, Guiying Yan, Jean Yeh, and Yeong-Nan Yeh, Symmetric decompositions and Euler-Stirling statistics on Stirling permutations, arXiv:2507.17667 [math.CO], 2025. See p. 5.
- Shi-Mei Ma and Yeong-Nan Yeh, The alternating run polynomials of permutations, arXiv:1904.11437 [math.CO], 2019. See p. 4.
- Alexander Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007. [_Peter Bala_, Oct 28 2008]
- Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
- Andrei K. Svinin, Somos-4 equation and related equations, arXiv:2307.05866 [math.CA], 2023. See p. 16.
Crossrefs
Programs
-
Maple
T:=proc(n,k) if k<0 then 0 elif n=1 and k=0 then 1 elif k>floor((n-1)/2) then 0 else (k+1)*T(n-1,k)+(2*n-4*k)*T(n-1,k-1) fi end: for n from 1 to 13 do seq(T(n,k),k=0..floor((n-1)/2)) od; # yields sequence in triangular form # Emeric Deutsch, Aug 06 2005
-
Mathematica
t[, k?Negative] = 0; t[1, 0] = 1; t[n_, k_] /; k > (n-1)/2 = 0; t[n_, k_] := t[n, k] = (k+1)*t[n-1, k] + (2*n-4*k)*t[n-1, k-1]; Table[t[n, k], {n, 1, 13}, {k, 0, (n-1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012 *)
Formula
G.f.: Sum_{n>=1, k>=0} T(n, k) t^k z^n/n! = C(t)(2-C(t))/(exp^(-z sqrt(1-4t)) + 1 - C(t)) - C(t), where the sum on k is actually finite, running up to ceiling(n/2) - 1; here C(t) = (1 - sqrt(1-4t))/2t is the generating function for the Catalan numbers (A000108).
Sum_{k} Eulerian(n, k) x^k = Sum_{k} T(n, k) x^k (1+x)^(n-1-2k). E.g., 1 + 11x + 11x^2 + x^3 = (1+x)^3 + 8x(1+x).
From Peter Bala, Jun 26 2012: (Start)
T(n,k) = 2^k*A094503(n,k+1).
Let r(t) = sqrt(1 - 2*t) and w(t) = (1 - r(t))/(1 + r(t)). Define F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ...; F(t,z) is the e.g.f. for A094503. The e.g.f. for the present table is A(t,z) := (F(2*t,z) - 1)/(2*t) = z + z^2/2! + (1+2*t)*z^3/3! + (1+8*t)*z^4/4! + ....
The e.g.f. A(t,z) satisfies the autonomous partial differential equation dA/dz = 1 + A + t*A^2 with A(t,0) = 0. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = int {x = 0..z} 1/(1+x+t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the row polynomial R(n,t) is the generating function for rooted plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
Row sums A080635.
(End)
Extensions
More terms from Emeric Deutsch, Aug 06 2005
Comments