A354756 - OEIS

%I #31 Jun 25 2022 10:01:53

%S 1,1,2,3,8,10,56,64,192,332,1184,1264,12192,12872,37568,100836,311760,

%T 322320,2338368,2408848,14433408,32058912,76931008,78528704,919469408,

%U 1158792224,2689828672,4675217824,21679173184,21984820864,381078324992,386159441600

%N a(n) is the number of permutations p of [n] such that lcm(i, p(i)) <= n for all i in [n].

%H Carl Pomerance, <a href="https://arxiv.org/abs/2206.01699">Permutations with arithmetic constraints</a>, arXiv:2206.01699 [math.NT], 2022.

%p b:= proc(s, m) option remember; `if`(s={}, 1, add(

%p      `if`(ilcm(nops(s), i)>m, 0, b(s minus {i}, m)), i=s))

%p     end:

%p a:= n-> b({$1..n}, n):

%p seq(a(n), n=0..20);  # _Alois P. Heinz_, Jun 06 2022

%t b[s_, m_] := b[s, m] = If[s == {}, 1, Sum[

%t      If[LCM[Length[s], i]>m, 0, b[s~Complement~{i}, m]], {i, s}]];

%t a[n_] := b[Range[n], n];

%t Table[Print[n, " ", a[n]]; a[n], {n, 0, 28}] (* _Jean-François Alcover_, Jun 25 2022, after _Alois P. Heinz_ *)

%o (PARI) a(n) = {my(nb=0); for (i=1, n!, my(p=numtoperm(n, i), ok=1); for (k=1, #p, if (lcm(k, p[k]) > n, ok = 0; break);); if (ok, nb++);); nb;}

%Y Cf. A320843.

%K nonn

%O 0,3

%A _Michel Marcus_, Jun 06 2022

%E a(12)-a(20) from _Seiichi Manyama_, Jun 06 2022

%E a(0), a(21)-a(31) from _Alois P. Heinz_, Jun 06 2022