OFFSET
0,7
FORMULA
T(n,k) = T(n,k-1) - T(n-1,k-1) with T(n,0) = A373340(n).
T(n,k) = (1/2)*(Sum_{j=0..k} (-1)^j * binomial(k,j) * (n-j)! - 2^(n-k-1)*(2-n-k)).
T(n,k) = (A047920(n, k) + 2^(n-k-1)*(n+k-2))/2. - Peter Luschny, Jul 28 2024
EXAMPLE
Triangle array T(n,k)
n: {k<=n}
0: {0}
1: {0, 0}
2: {1, 1, 1}
3: {5, 4, 3, 2}
4: {20, 15, 11, 8, 6}
5: {84, 64, 49, 38, 30, 24}
6: {424, 340, 276, 227, 189, 159, 135}
7: {2680, 2256, 1916, 1640, 1413, 1224, 1065, 930}
T(n,0) = A373340(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an odd number of cycles.
T(n,n) = A216779(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an odd number of cycles.
T(2,k) = 1 because S_2 contains 1 permutation with an odd number of non-fixed point cycles without k=0,1 or 2 particular fixed points, namely the derangement (12).
T(3,2) = 3 because S_3 contains 3 permutations with an odd number of non-fixed point cycles without k=2 particular fixed points: say, without fixed points (1) and (2), namely (12)(3), (123), (132).
MATHEMATICA
Table[Table[1/2*(Sum[(-1)^j*Binomial[k, j]*(n - j)!, {j, 0, k}] - 2^(n - k - 1)*(2 - n - k)), {k, 0, n}], {n, 0, 10}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Julian Hatfield Iacoponi, Jul 08 2024
STATUS
approved