A374419 Triangle read by rows: T(n,k) = number of permutations in symmetric group S_n with an even number of non-fixed point cycles, without k<=n particular fixed points.
1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 4, 3, 3, 3, 3, 36, 32, 29, 26, 23, 20, 296, 260, 228, 199, 173, 150, 130, 2360, 2064, 1804, 1576, 1377, 1204, 1054, 924, 19776, 17416, 15352, 13548, 11972, 10595, 9391, 8337, 7413, 180544, 160768, 143352, 128000, 114452, 102480, 91885, 82494, 74157, 66744
Offset: 0
Examples
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.
Crossrefs
Programs
-
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}]
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)).