login
A374420
Triangle T(n, k) for the number of permutations of symmetric group S_n with an odd number of non-fixed point cycles, without k <= n particular fixed points.
1
0, 0, 0, 1, 1, 1, 5, 4, 3, 2, 20, 15, 11, 8, 6, 84, 64, 49, 38, 30, 24, 424, 340, 276, 227, 189, 159, 135, 2680, 2256, 1916, 1640, 1413, 1224, 1065, 930, 20544, 17864, 15608, 13692, 12052, 10639, 9415, 8350, 7420, 182336, 161792, 143928, 128320, 114628, 102576, 91937, 82522, 74172, 66752
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
Cf. A374419 (even case), A216779 (main diagonal), A373340 (first column).
Sequence in context: A194744 A132669 A276052 * A348340 A321028 A351169
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved