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

Author

Alois P. Heinz, May 01 2017

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Programs

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 *)