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
Examples
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
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.
Programs
-
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 *)
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
Comments