A138771 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose 2nd cycle has k entries; each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements (n>=1; 0<=k<=n-1). For example, 1432=(1)(24)(3) has 2 entries in the 2nd cycle; 3421=(1324) has 0 entries in the 2nd cycle.

1, 1, 1, 2, 3, 1, 6, 11, 5, 2, 24, 50, 26, 14, 6, 120, 274, 154, 94, 54, 24, 720, 1764, 1044, 684, 444, 264, 120, 5040, 13068, 8028, 5508, 3828, 2568, 1560, 720, 40320, 109584, 69264, 49104, 35664, 25584, 17520, 10800, 5040

Offset: 1

Author

Emeric Deutsch, Apr 10 2008

Keywords

• nonn
• tabl

Comments

T(n,0)=(n-1)!=A000142(n-1).

T(n,1)=A000254(n-1).

T(n,2)=A001705(n-2).

T(n,3)=2*A001711(n-4).

T(n,4)=6*A001716(n-5).

T(n,n-1)=(n-2)! (n>=2).

Sum(kT(n,k),k=0..n-1)=(n-1)!(n-1)(n+2)/4=A138772(n).

Examples

			T(4,2)=5 because we have (1)(23)(4), (1)(24)(3), (13)(24), (12)(34) and (14)(23).
Triangle starts;
1;
1,1;
2,3,1;
6,11,5,2;
24,50,26,14,6;
120,274,154,94,54,24;
		

Crossrefs

Cf. A000142, A000254, A001705, A001711, A001716, A138772.

From Johannes W. Meijer, Oct 16 2009: (Start)

A000142 equals for n=>1 the row sums.

a(n) = A165680(n) * A165675(n-1).

(End)

Programs

Maple

T:=proc (n,k) if k = 0 then factorial(n-1) elif n <= k then 0 else (n-1)*T(n-1, k)+factorial(n-2) end if end proc: for n to 9 do seq(T(n, k), k=0..n-1) end do;

Formula

T(n,k)=(n-1)T(n-1,k)+(n-2)! (1<=k<=n-1). The row generating polynomials P[n](t) satisfy: P[n+1](t)=nP[n](t)+(n-1)!(t+t^2+...+t^n).