login
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, 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,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
Cf. A374420 (odd case), A216778 (main diagonal), A373339 (first column).
Sequence in context: A356764 A085415 A187470 * A059124 A320604 A282445
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved