A373340 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

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

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

EXAMPLE

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.

PROG

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

CROSSREFS

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

Row sums of triangle A373418.

Sequence in context: A002213 A099949 A006231 * A069007 A126987 A152185

Adjacent sequences: A373337 A373338 A373339 * A373341 A373342 A373343

KEYWORD

nonn

AUTHOR

Julian Hatfield Iacoponi, Jun 01 2024

STATUS

approved