A329945 Number of permutations of [n] whose cycle lengths avoid squares.

1, 0, 1, 2, 3, 44, 175, 1434, 12313, 59912, 1057761, 9211850, 118785931, 1702959972, 21390805423, 339381890834, 4027183717425, 89818053205904, 1477419923299393, 28377482210884242, 608128083110593171, 11954214606663753500, 269933818505222203311

Offset: 0

Author

Alois P. Heinz, Nov 24 2019

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• David Harry Richman and Andrew O'Desky, Derangements and the p-adic incomplete gamma function, arXiv:2012.04615 [math.NT], 2020.

Crossrefs

Cf. A000290, A059841, A205801, A271751, A329944.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1, add(`if`(issqr(j), 0,
      a(n-j)*binomial(n-1, j-1)*(j-1)!), j=1..n))
    end:
seq(a(n), n=0..25);

Mathematica

a[n_] := a[n] = If[n == 0, 1, Sum[If[IntegerQ@Sqrt[j], 0,
     a[n-j] Binomial[n-1, j-1] (j-1)!], {j, 1, n}]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 31 2021, after Alois P. Heinz *)

Formula

a(n) mod 2 = 1 - (n mod 2) = A059841(n).

a(n) mod 10 = period 10: repeat [1,0,1,2,3,4,5,4,3,2] = A271751(n-1) for n>0.