A145882 Triangle read by rows: T(n,k) is the number of even permutations of {1,2,...,n} having k descents (n >= 1, k >= 0).

1, 1, 1, 2, 1, 5, 5, 1, 1, 14, 30, 14, 1, 1, 29, 147, 155, 28, 1, 64, 586, 1208, 605, 56, 1, 127, 2133, 7819, 7819, 2133, 127, 1, 1, 262, 7288, 44074, 78190, 44074, 7288, 262, 1, 1, 517, 23893, 227569, 655315, 655039, 227623, 23947, 496, 1, 1044, 76332, 1101420

Offset

1,4

Comments

Number of entries in row n is 1+floor(binomial(n,2)/2)-floor(binomial(n-2,2)/2).

Sum of entries in row n is A001710(n) for n>=2.

Links

Alois P. Heinz, Rows n = 1..142, flattened

J. Shareshian and M. L. Wachs, q-Eulerian polynomials: excedance number and major index, Electronic Research Announcements of the Amer. Math. Soc., 13 (2007), 33-45.

R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combinat. Theory, A 20 (1976), 336-356.

S. Tanimoto, A study of Eulerian numbers for permutations in the alternating group, Integers, Electronic J. of Combinatorial Number Theory, 6 (2006), #A31.

Formula

In the Shareshian and Wachs reference (p. 35) a q-analog of the exponential g.f. of the Eulerian polynomials is given for the joint distribution of (inv, des) (see also the Stanley reference). The first Maple program given below makes use of this function by considering its even part.

T(n,k) = (euler(n,k) + Sum_{j=max(0, k+1-ceiling(n/2))..min(floor(n/2), k)} binomial(j-1-floor(n/2), j) * euler(ceiling(n/2), k-j)) / 2, where euler(n,k) is the Eulerian number A173018 (not A008292, which has different indexing). - Robert A. Russell, Nov 15 2018

Example

T(4,2) = 5 because we have 4132, 2143, 4213, 2431 and 3241.
Triangle begins with T(1,0):
  1
  1
  1    2
  1    5      5       1
  1   14     30      14       1
  1   29    147     155      28
  1   64    586    1208     605      56
  1  127   2133    7819    7819    2133     127       1
  1  262   7288   44074   78190   44074    7288     262     1
  1  517  23893  227569  655315  655039  227623   23947   496
  1 1044  76332 1101420 4869558 7862124 4868556 1102068 76305 992

Maple

for n to 11 do qbr := proc (m) options operator, arrow; sum(q^i, i = 0 .. m-1) end proc; qfac := proc (m) options operator, arrow; product(qbr(j), j = 1 .. m) end proc; Exp := proc (z) options operator, arrow; sum(q^binomial(m, 2)*z^m/qfac(m), m = 0 .. 19) end proc; g := (1-t)/(Exp(z*(t-1))-t); gser := simplify(series(g, z = 0, 17)); a[n] := simplify(qfac(n)*coeff(gser, z, n)); b[n] := (a[n]+subs(q = -q, a[n]))*1/2; P[n] := sort(subs(q = 1, b[n])) end do; for n to 11 do seq(coeff(P[n], t, j), j = 0 .. floor((1/2)*binomial(n, 2)) -floor((1/2)*binomial(n-2, 2))) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, t, expand(
       add(b(u+j-1, o-j, irem(t+j-1+u, 2)), j=1..o)+
       add(b(u-j, o+j-1, irem(t+u-j, 2))*x, j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))
        (add(b(j-1, n-j, irem(j, 2)), j=1..n)):
seq(T(n), n=1..12);  # Alois P. Heinz, Nov 19 2013

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, t, Expand[Sum[b[u+j-1, o-j, Mod[t+j-1+u, 2]], {j, 1, o}] + Sum[b[u-j, o+j-1, Mod[t+u-j, 2]]*x, {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]] [Sum[b[j-1, n-j, Mod[j, 2]], {j, 1, n}]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)
Needs["Combinatorica`"];
Table[(Eulerian[n, k] + Sum[Binomial[j-1-Floor[n/2], j] Eulerian[Ceiling[n/2], k-j], {j, Max[0, k-Ceiling[n/2]], Min[Floor[n/2], k]}])/2, {n, 25}, {k, 0, n-1}] // Flatten // DeleteCases[0] (* Robert A. Russell, Nov 14 2018 *)

Crossrefs

Cf. A001710, A145883.

Sequence in context: A141485 A005605 A300661 * A209765 A209759 A111785

Adjacent sequences: A145879 A145880 A145881 * A145883 A145884 A145885

Keyword

nonn,tabf

Author

Emeric Deutsch, Nov 11 2008

Status

approved