A184178 Irregular triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k isolated fixed points.

1, 0, 1, 2, 3, 3, 13, 8, 3, 56, 51, 12, 1, 325, 294, 93, 8, 2193, 2068, 687, 90, 2, 17133, 16392, 5862, 888, 45, 151403, 146484, 54861, 9463, 660, 9, 1492804, 1454716, 565044, 106652, 9320, 264, 16236705, 15903261, 6354090, 1285990, 131145, 5565, 44

Offset

0,4

Comments

A fixed point j of a permutation is said to be isolated if neither j-1 nor j+1 is a fixed point. For example, 4135267 has only 3 as an isolated fixed point.

Row n has 1+ceiling(n/2) terms if n >= 4.

Links

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

Formula

T(n,k) = Sum_{j=k..n} d(n-j)*Sum_{m=0..floor((j-k)/2)} binomial(j-k-m-1, m-1)*binomial(n+1-j, k+m)*binomial(k+m, k), where d(i)=A000166(i) are the derangement numbers.

Sum of entries in row n is n!.

T(n,0) = A184179(n).

Sum_{k>=0} k*T(n,k) = A001564(n-2) (n>=3).

Example

T(3,1)=3 because we  have 132, 321, and 213.
T(4,2)=3 because we have 1432, 1324, and 3214.
Triangle starts:
    1;
    0,   1;
    2;
    3,   3;
   13,   8,   3;
   56,  51,  12,   1;
  325, 294,  93,   8;

Maple

d[0] := 1: d[1] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n, k) options operator, arrow: add(d[n-j]*add(binomial(j-k-m-1, m-1)*binomial(n+1-j, k+m)*binomial(k+m, k), m = 0 .. floor((1/2)*j-(1/2)*k)), j = k .. n) end proc: 1; 0, 1; 2; 3, 3; for n from 4 to 11 do seq(a(n, k), k = 0 .. ceil((1/2)*n)) end do; # yields sequence in triangular form

Crossrefs

Cf. A000166, A001564, A184179.

Sequence in context: A370554 A127003 A211673 * A350531 A039793 A106243

Adjacent sequences: A184175 A184176 A184177 * A184179 A184180 A184181

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 13 2011

Status

approved