login
A286076
Number of permutations of [n] with alternating cycle size parities.
8
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
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 *)
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 01 2017
STATUS
approved