A369080 Number of permutations of [n] such that the element sum of each cycle is odd.

1, 1, 1, 2, 6, 36, 180, 1080, 7560, 75600, 680400, 6804000, 74844000, 1047816000, 13621608000, 190702512000, 2860537680000, 51489678240000, 875324530080000, 15755841541440000, 299360989287360000, 6585941764321920000, 138304777050760320000, 3042705095116727040000

Offset

0,4

Comments

Number of permutations of [n] such that each cycle has an odd number of odd elements.

a(n+1)/a(n) is an integer for all n >= 0.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450

Wikipedia, Permutation

Example

a(0) = 1: the empty permutation.
a(1) = 1: (1).
a(2) = 1: (12).
a(3) = 2: (12)(3), (1)(23).
a(4) = 6: (124)(3), (142)(3), (12)(34), (14)(23), (1)(234), (1)(243).

Maple

b:= proc(x, y) option remember; `if`(x+y=0, 1, add(
      `if`(j::odd, binomial(x-1, j-1)*add((i+j-1)!*
       b(x-j, y-i)*binomial(y, i), i=0..y), 0), j=1..x))
    end:
a:= n-> (h-> b(n-h, h))(iquo(n, 2)):
seq(a(n), n=0..23);
# second Maple program:
b:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <-1|1|0|0|1>>^n. <<1, 2, 3, 6, 5>>)[1, 1]:
a:= proc(n) option remember; `if`(n<2, 1, a(n-1)*b(n-2)) end:
seq(a(n), n=0..23);

Crossrefs

Cf. A000142, A369079.

Sequence in context: A019020 A236692 A323945 * A101609 A281024 A152668

Adjacent sequences: A369077 A369078 A369079 * A369081 A369082 A369083

Keyword

nonn

Author

Alois P. Heinz, Jan 12 2024

Status

approved