cp's OEIS Frontend

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).

%I A101280 #58 Jul 28 2025 20:18:06
%S A101280 1,1,1,2,1,8,1,22,16,1,52,136,1,114,720,272,1,240,3072,3968,1,494,
%T A101280 11616,34304,7936,1,1004,40776,230144,176896,1,2026,136384,1328336,
%U A101280 2265344,353792,1,4072,441568,6949952,21953408,11184128,1,8166,1398000,33981760
%N 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).
%C A101280 Row n has ceiling(n/2) terms.
%C A101280 The paper by Shapiro et al. explains why T(n,k) is the number of permutations of n elements having k peaks and with the further property that every rise (ascent) is immediately followed by a peak. [That is, the permutation p_1 ... p_n has the further property that (j > 1 and p_{j-1} < p_j) implies (j < n and p_j > p_{j+1}).] For example, the T(4,1)=8 permutations in the case n=4, k=1 are 1423, 2143, 2431, 3142, 3241, 3421, 4231, 4132.
%C A101280 A more elegant way to state this property: T(n,k) is the number of permutations of n objects with k descents such that every descent is a peak. The eight examples for n=4 and k=1 are now 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
%C A101280 The rows of this triangle are the gamma vectors of the n-dimensional (type A) permutohedra (Postnikov et al., p. 31). Cf. A055151 and A089627. - _Peter Bala_, Oct 28 2008
%D A101280 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.
%D A101280 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
%D A101280 T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 4.
%H A101280 Paul Barry, <a href="https://arxiv.org/abs/1805.02274">On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays</a>, arXiv:1805.02274 [math.CO], 2018.
%H A101280 François Bergeron, Philippe Flajolet and Bruno Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H A101280 Leonard Carlitz and Richard Scoville, <a href="http://dx.doi.org/10.1515/crll.1974.265.110">Generalized Eulerian numbers: combinatorial applications</a>, Journal für die reine und angewandte Mathematik 265 (1974), 111.
%H A101280 Colin Defant, <a href="https://arxiv.org/abs/2004.11367">Troupes, Cumulants, and Stack-Sorting</a>, arXiv:2004.11367 [math.CO], 2020.
%H A101280 Diego Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions</a>, arXiv:math/0501052 [math.CA], 2005.
%H A101280 Dominique Foata and Marcel-Paul Schützenberger, <a href="http://arxiv.org/abs/math/0508232">Théorie géometrique des polynômes eulériens</a>, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math. 138 (1970), 81-83.
%H A101280 Shi-Mei Ma, <a href="http://arxiv.org/abs/1304.6654">On gamma-vectors and the derivatives of the tangent and secant functions</a>, arXiv:1304.6654 [math.CO], 2013.
%H A101280 Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/1802.02861">On certain combinatorial expansions of descent polynomials and the change of grammars</a>, arXiv:1802.02861 [math.CO], 2018.
%H A101280 Shi-Mei Ma, Jianfeng Wang, Guiying Yan, Jean Yeh, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/2507.17667">Symmetric decompositions and Euler-Stirling statistics on Stirling permutations</a>, arXiv:2507.17667 [math.CO], 2025. See p. 5.
%H A101280 Shi-Mei Ma and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/1904.11437">The alternating run polynomials of permutations</a>, arXiv:1904.11437 [math.CO], 2019. See p. 4.
%H A101280 Alexander Postnikov, Victor Reiner, and Lauren Williams, <a href="http://arxiv.org/abs/math/0609184">Faces of generalized permutohedra</a>, arXiv:math/0609184 [math.CO], 2006-2007. [_Peter Bala_, Oct 28 2008]
%H A101280 Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, <a href="http://dx.doi.org/10.1137/0604046">Runs, slides and moments</a>, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
%H A101280 Andrei K. Svinin, <a href="https://arxiv.org/abs/2307.05866">Somos-4 equation and related equations</a>, arXiv:2307.05866 [math.CA], 2023. See p. 16.
%F A101280 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).
%F A101280 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).
%F A101280 From _Peter Bala_, Jun 26 2012: (Start)
%F A101280 T(n,k) = 2^k*A094503(n,k+1).
%F A101280 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! + ....
%F A101280 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.
%F A101280 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.
%F A101280 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.
%F A101280 Row sums A080635.
%F A101280 (End)
%e A101280 Triangle begins:
%e A101280   1;
%e A101280   1,
%e A101280   1,   2;
%e A101280   1,   8,
%e A101280   1,  22,  16;
%e A101280   1,  52, 136,
%e A101280   1, 114, 720, 272;
%e A101280   ...
%e A101280 From _Peter Bala_, Jun 26 2012: (Start)
%e A101280 n = 4: the 9 weighted plane increasing 0-1-2 trees on 4 vertices are
%e A101280 ..................................................................
%e A101280 ..4...............................................................
%e A101280 ..|...............................................................
%e A101280 ..3..........4...4...............4...4...............3...3........
%e A101280 ..|........./.....\............./.....\............./.....\.......
%e A101280 ..2....2...3.......3...2...3...2.......2...3...4...2.......2...4..
%e A101280 ..|.....\./.........\./.....\./.........\./.....\./.........\./...
%e A101280 ..1...(t)1........(t)1....(t)1........(t)1....(t)1........(t)1....
%e A101280 ..................................................................
%e A101280 ..3...4...4...3...................................................
%e A101280 ...\./.....\./....................................................
%e A101280 .(t)2....(t)2.....................................................
%e A101280 ....|.......|.....................................................
%e A101280 ....1.......1.....................................................
%e A101280 Hence R(4,t) = 1 + 8*t.
%e A101280 (End)
%p A101280 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
%t A101280 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 *)
%Y A101280 The numbers 2^{n-1-k} T(n, k) form the array shown in A008303.
%Y A101280 Cf. A055151, A089627. - _Peter Bala_, Oct 28 2008
%Y A101280 Cf. A008292, A094503, A080635 (row sums).
%K A101280 nonn,tabf,easy
%O A101280 1,4
%A A101280 _Don Knuth_, Jan 28 2005
%E A101280 More terms from _Emeric Deutsch_, Aug 06 2005