A097898 Triangle read by rows: T(n,k) is the number of permutations of [n] with k runs of length 1. For example, 457/3/26/1 has two runs of length 1: 3 and 1.

1, 0, 1, 1, 0, 1, 1, 4, 0, 1, 6, 6, 11, 0, 1, 19, 51, 23, 26, 0, 1, 109, 212, 269, 72, 57, 0, 1, 588, 1571, 1419, 1140, 201, 120, 0, 1, 4033, 10470, 13343, 7432, 4272, 522, 247, 0, 1, 29485, 87672, 107853, 87552, 33683, 14841, 1291, 502, 0, 1, 246042, 763612

Offset: 0

Author

Emeric Deutsch and Ira M. Gessel, Sep 03 2004

Keywords

• nonn
• tabl

Examples

			Triangle starts:
1;
0,1;
1,0,1;
1,4,0,1;
6,6,11,0,1;
19,51,23,26,0,1
Row n has n+1 terms.
T(3,0)=1, T(3,1)=4, T(3,2)=0 and T(3,3)=1 because we have 123, 13(2), (2)13, 23(1), (3)12, (3)(2)(1), the runs of length 1 being shown between parentheses.
		

References

• Ira. M. Gessel, Generating functions and enumeration of sequences, Ph. D. Thesis, MIT, 1977.

Programs

Maple

A:=(1-t)/2: B:=sqrt(t^2+2*t-3)/2: G:=B/exp(A*z)/(A*sinh(B*z)+B*cosh(B*z)-sinh(B*z)): Gserz:=simplify(series(G,z=0,12)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(n!*coeff(Gserz,z^n)) od: seq(seq(coeff(t*P[n],t^k),k=1..n+1),n=0..10);

Formula

E.g.f.: Bexp(-Ax)/[A*sinh(Bx)+B*cosh(Bx)-sinh(Bx)], where A=(1-t)/2 and B=(1/2)sqrt(t^2+2t-3).