login
A184178
Irregular triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k isolated fixed points.
1
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.
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Feb 13 2011
STATUS
approved