login
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.
0

%I #7 Jan 24 2013 10:05:10

%S 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,

%T 588,1571,1419,1140,201,120,0,1,4033,10470,13343,7432,4272,522,247,0,

%U 1,29485,87672,107853,87552,33683,14841,1291,502,0,1,246042,763612

%N 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.

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

%F 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).

%e Triangle starts:

%e 1;

%e 0,1;

%e 1,0,1;

%e 1,4,0,1;

%e 6,6,11,0,1;

%e 19,51,23,26,0,1

%e Row n has n+1 terms.

%e 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.

%p 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);

%K nonn,tabl

%O 0,8

%A _Emeric Deutsch_ and _Ira M. Gessel_, Sep 03 2004