A097591 Triangle read by rows: T(n,k) is the number of permutations of [n] with exactly k increasing runs of odd length.

1, 0, 1, 1, 0, 1, 0, 5, 0, 1, 6, 0, 17, 0, 1, 0, 70, 0, 49, 0, 1, 90, 0, 500, 0, 129, 0, 1, 0, 1890, 0, 2828, 0, 321, 0, 1, 2520, 0, 23100, 0, 13930, 0, 769, 0, 1, 0, 83160, 0, 215292, 0, 62634, 0, 1793, 0, 1, 113400, 0, 1549800, 0, 1697430, 0, 264072, 0, 4097, 0, 1

Offset: 0

Author

Emeric Deutsch, Aug 29 2004

Keywords

• nonn
• tabl

Examples

			Triangle starts:
     1;
     0,    1;
     1,    0,     1;
     0,    5,     0,    1;
     6,    0,    17,    0,     1;
     0,   70,     0,   49,     0,   1;
    90,    0,   500,    0,   129,   0,   1;
     0, 1890,     0, 2828,     0, 321,   0, 1;
  2520,    0, 23100,    0, 13930,   0, 769, 0, 1;
  ...
Row n has n+1 entries.
Example: T(3,1) = 5 because we have (123), 13(2), (2)13, 23(1) and (3)12 (the runs of odd length are shown between parentheses).
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Bisections of columns k=0-1 give: A000680, A302910.

Row sums give A000142.

T(n+1,n-1) gives A000337.

T(4n,2n) gives A308962.

Cf. A096654, A097592.

Programs

Maple

G:=t^2/(1-t*x-(1-t^2)*exp(-t*x)): Gser:=simplify(series(G,x=0,12)): P[0]:=1: for n from 1 to 11 do P[n]:=sort(expand(n!*coeff(Gser,x^n))) od: seq(seq(coeff(t*P[n],t^k),k=1..n+1),n=0..11);
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, x^t, expand(
      add(b(u+j-1, o-j, irem(t+1, 2)), j=1..o)+
      add(b(u-j, o+j-1, 1)*x^t, j=1..u)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..12);  # Alois P. Heinz, Nov 19 2013

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, x^t, Expand[Sum[b[u+j-1, o-j, Mod[t+1, 2]], {j, 1, o}] + Sum[b[u-j, o+j-1, 1]*x^t, {j, 1, u}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, Exponent[p, x]}]][b[n, 0, 1]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Formula

E.g.f.: t^2/[1-tx-(1-t^2)exp(-tx)].

Sum_{k=1..n} k * T(n,k) = A096654(n-1) for n > 0. - Alois P. Heinz, Jul 03 2019