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.

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

Links

Table of n, a(n) for n=0..54.

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. A047920, A062111, A047920.

Cf. A374419 (even case), A216779 (main diagonal), A373340 (first column).

Sequence in context: A194744 A132669 A276052 * A348340 A321028 A351169

Adjacent sequences: A374417 A374418 A374419 * A374421 A374422 A374423

Keyword

nonn,tabl

Author

Julian Hatfield Iacoponi, Jul 08 2024

Status

approved