login
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).
20
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
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
Sequence in context: A141485 A005605 A300661 * A209765 A209759 A111785
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Nov 11 2008
STATUS
approved