cp's OEIS Frontend

A161129 Triangle read by rows: T(n,k) is the number of non-derangements of {1,2,...,n} for which the difference between the largest and smallest fixed points is k (n>=1; 0 <= k <= n-1).

%I A161129 #14 Nov 28 2017 13:46:50
%S A161129 1,0,1,3,0,1,8,3,2,2,45,8,9,8,6,264,45,44,42,36,24,1855,264,265,256,
%T A161129 234,192,120,14832,1855,1854,1810,1704,1512,1200,720,133497,14832,
%U A161129 14833,14568,13950,12864,11160,8640,5040,1334960,133497,133496,131642,127404
%N A161129 Triangle read by rows: T(n,k) is the number of non-derangements of {1,2,...,n} for which the difference between the largest and smallest fixed points is k (n>=1; 0 <= k <= n-1).
%C A161129 Row sums give the number of non-derangement permutations of {1,2,...,n} (A002467).
%C A161129 T(n,0) = A000240(n) = number of permutations of {1,2,...,n} with exactly 1 fixed point.
%C A161129 T(n,1) = A000240(n-1).
%C A161129 T(n,2) = A000166(n-1) (the derangement numbers).
%C A161129 T(n,3) = A018934(n-1).
%C A161129 Sum_{k=0..n-1} k*T(n,k) = A161130(n).
%H A161129 E. Deutsch and S. Elizalde, <a href="http://arxiv.org/abs/0904.2792">The largest and the smallest fixed points of permutations</a>, arXiv:0904.2792 [math.CO], 2009.
%F A161129 T(n,0) = n*d(n-1); T(n,k) = (n-k)*Sum_{j=0..k-1}d(n-2-j)*binomial(k-1,j) for 1 <= k <= n-1, where d(i)=A000166(i) are the derangement numbers.
%e A161129 T(4,1)=3 because we have 1243, 4231, and 2134; T(4,2)=2 because we have 1432 and 3214; T(5,4)=6 because we have 1xyz5 where xyz is any permutation of 234.
%e A161129 Triangle starts:
%e A161129     1;
%e A161129     0,  1;
%e A161129     3,  0,  1;
%e A161129     8,  3,  0,  1;
%e A161129    45,  8,  9,  8,  6;
%e A161129   264, 45, 44, 42, 36, 24;
%p A161129 d[0] := 1: for n to 15 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if k = 0 then n*d[n-1] elif k < n then (n-k)*(sum(binomial(k-1, j)*d[n-2-j], j = 0 .. k-1)) else 0 end if end proc: for n to 10 do seq(T(n, k), k = 0 .. n-1) end do; # yields sequence in triangular form
%t A161129 d = Subfactorial;
%t A161129 T[n_, 0] := n*d[n - 1];
%t A161129 T[n_, k_] := (n - k)*Sum[d[n - j - 2]*Binomial[k - 1, j], {j, 0, k - 1}];
%t A161129 Table[T[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* _Jean-François Alcover_, Nov 28 2017 *)
%Y A161129 Cf. A000166, A000240, A002467, A018934, A161130.
%K A161129 nonn,tabl
%O A161129 1,4
%A A161129 _Emeric Deutsch_, Jul 18 2009