1,4

Row n has ceil(n/2) terms.

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.

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.

Contribution from Peter Bala (pbala(AT)toucansurf.com), Oct 28 2008): (Start)

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.

(End)

L. Carlitz and Richard Scoville, Generalized Eulerian numbers: combinatorial applications, Journal f\"ur die reine und angewandte Mathematik 265 (1974), 111.

D. Foata and M. P. Sch\"utzenberger, Th\'eorie g\'eometrique des polyn\^omes eul\'eriens, Lecture Notes in Math. 138 (1970), 81-83.

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.

Louis W. Shapiro, Wen-Jin Woan and Seyoum Getu, "Runs, slides and moments", SIAM J. Algebraic and Discrete Methods 4 (1983), 461.

A. Postnikov, V. Reiner, L. Williams, Faces of generalized permutohedra [From Peter Bala (pbala(AT)toucansurf.com), Oct 28 2008]

G.f.: sum_{n=1..infty, k=0..infty} 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).

Triangle begins:

1

1

1 2

1 8

1 22 16

1 52 136

1 114 720 272

...

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 (Deutsch)

The numbers 2^{n-1-k} T(n,k) form the array shown in A008303.

A055151, A089627. [From Peter Bala (pbala(AT)toucansurf.com), Oct 28 2008]

Sequence in context: A009385 A008308 A118931 this_sequence A008309 A131175 A066532

Adjacent sequences: A101277 A101278 A101279 this_sequence A101281 A101282 A101283

nonn,tabf,easy

D. E. Knuth, Jan 28 2005

More terms from Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 06 2005