A374420 - OEIS

%I #13 Jul 30 2024 15:35:42

%S 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,

%T 189,159,135,2680,2256,1916,1640,1413,1224,1065,930,20544,17864,15608,

%U 13692,12052,10639,9415,8350,7420,182336,161792,143928,128320,114628,102576,91937,82522,74172,66752

%N 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.

%F T(n,k) = T(n,k-1) - T(n-1,k-1) with T(n,0) = A373340(n).

%F T(n,k) = (1/2)*(Sum_{j=0..k} (-1)^j * binomial(k,j) * (n-j)! - 2^(n-k-1)*(2-n-k)).

%F T(n,k) = (A047920(n, k) + 2^(n-k-1)*(n+k-2))/2. - _Peter Luschny_, Jul 28 2024

%e Triangle array T(n,k)

%e n: {k<=n}

%e 0:  {0}

%e 1:  {0,       0}

%e 2:  {1,       1,       1}

%e 3:  {5,       4,       3,       2}

%e 4:  {20,      15,      11,      8,       6}

%e 5:  {84,      64,      49,      38,      30,      24}

%e 6:  {424,     340,     276,     227,     189,     159,     135}

%e 7:  {2680,    2256,    1916,    1640,    1413,    1224,    1065,   930}

%e 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.

%e 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.

%e 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).

%e 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).

%t 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}]

%Y Cf. A047920, A062111, A047920.

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

%K nonn,tabl

%O 0,7

%A _Julian Hatfield Iacoponi_, Jul 08 2024