A373340 Number of permutations of symmetric group S_n with an odd number of cycles of length 2 or more.

0, 0, 1, 5, 20, 84, 424, 2680, 20544, 182336, 1816448, 19963008, 239511040, 3113532928, 43589194752, 653837290496, 10461395173376, 177843714539520, 3201186853912576, 60822550206644224, 1216451004093038592, 25545471085864681472, 562000363888824811520

Offset: 0

Author

Julian Hatfield Iacoponi, Jun 01 2024

Keywords

• nonn

Examples

			a(0)=0 due to the sole permutation in S_0 being the empty permutation, with 0 non-fixed point cycles, not an odd number.
a(1)=0 due to the sole permutation in S_1 being the fixed point (1), with 0 non-fixed point cycles, not an odd number.
a(2)=1 due to 1 permutation in S_2 with an odd number of non-fixed point cycles: (12), with 1 non-fixed point cycle.
a(3)=5 due to 5 permutations in S_3 with an odd number of non-fixed point cycles: (12)(3),(13)(2),(23)(1),(123),(132), all with 1 non-fixed point cycle.
		

Crossrefs

Cf. A373339 (even case), A000142, A001710, A036289.

Row sums of triangle A373418.

Programs

PARI

a(n) = n!/2 + (n-2)*2^(n-2); \\ Michel Marcus, Jun 05 2024

Formula

a(n) = n!/2 + (n-2)*2^(n-2) = A001710(n) + A036289(n-2).

a(n) = A000142(n) - A373339(n).

E.g.f.: (1/(1 - x) - exp(2*x)*(1 - x))/2. - Stefano Spezia, Jun 05 2024