OFFSET
0,11
FORMULA
T(n,k) = T(n,k-1) - T(n-1,k-1) with T(n,0) = A373339(n).
T(n,k) = (1/2) * (Sum_{j=0..k} (-1)^j * binomial(k,j) * (n-j)! + 2^(n-k-1)*(2-n-k)).
EXAMPLE
Triangle array T(n,k) begins:
n: {k<=n}
0: {1}
1: {1, 0}
2: {1, 0, 0}
3: {1, 0, 0, 0}
4: {4, 3, 3, 3, 3}
5: {36, 32, 29, 26, 23, 20}
6: {296, 260, 228, 199, 173, 150, 130}
7: {2360, 2064, 1804, 1576, 1377, 1204, 1054, 924}
T(n,0) = A373339(n) = the number of permutations in S_n without k=0 particular fixed points (i.e., not filtered, so all permutations) with an even number of cycles.
T(n,n) = A216778(n) = the number of permutations in S_n without k=n particular fixed points (i.e., filtered down to just the derangements) with an even number of cycles.
T(4,1<=k<=4) = 3 because S_4 contains 3 permutations with an even number of non-fixed point cycles without k=1,2,3 or 4 particular fixed points, namely the 3 (2,2)-cycles: (12)(34), (13)(24), (14)(23).
T(4,0) = 4 is one more than the above because it includes the permutation without k=0 particular fixed points, i.e., the identity permutation of 4 fixed points.
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