A286076 Number of permutations of [n] with alternating cycle size parities.

1, 1, 1, 5, 8, 78, 206, 2722, 10516, 169544, 883580, 16569420, 110272040, 2339828920, 19127099680, 450962267600, 4399562960000, 113769961266000, 1295735797694000, 36390357922438000, 475484093140888000, 14390912055770276000, 212715123602601932000

Offset

0,4

Comments

Each cycle is written with the smallest element first and cycles are arranged in increasing order of their first elements.

Links

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

Wikipedia, Permutation

Example

a(3) = 5: (123), (132), (12)(3), (13)(2), (1)(23).
a(4) = 8: (1234), (1243), (1324), (1342), (1423), (1432), (1)(23)(4), (1)(24)(3).

Maple

b:= proc(n, t) option remember; `if`(n=0, 1, add(`if`((i+t)::odd,
      b(n-i, 1-t)*(i-1)!*binomial(n-1, i-1), 0), i=1..n))
    end:
a:= n-> `if`(n=0, 1, b(n, 0)+b(n, 1)):
seq(a(n), n=0..30);

Mathematica

b[n_, t_] := b[n, t] = If[n == 0, 1, Sum[If[(i + t) // OddQ, b[n - i, 1 - t]*(i - 1)!*Binomial[n - 1, i - 1], 0], {i, 1, n}]];
a[n_] := If[n == 0, 1, b[n, 0] + b[n, 1]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 28 2018, from Maple *)

Crossrefs

Cf. A275679, A286071, A286072, A286073, A286074, A286075, A286077.

Sequence in context: A250067 A213239 A123819 * A302651 A260695 A153720

Adjacent sequences: A286073 A286074 A286075 * A286077 A286078 A286079

Keyword

nonn

Author

Alois P. Heinz, May 01 2017

Status

approved