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,4

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

Links

Table of n, a(n) for n=1..45.

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

Example

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;

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;

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)

Sequence in context: A155856 A086960 A165675 * A121748 A174893 A008275

Adjacent sequences: A138768 A138769 A138770 * A138772 A138773 A138774

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 10 2008

Status

approved