A320843 Number of permutations sigma of {1,2,...,n} such that sigma(i) divides i or i divides sigma(i) for 1 <= i <= n.
1, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812, 449586, 1939684, 3853278, 8650900, 8840110, 60035322, 80605209, 177211024, 368759752, 1380348224, 1401414640, 8892787136, 9014369784, 33923638848, 59455553072, 126536289568, 207587882368
Offset: 0
Keywords
Examples
In case n = 4: permutation ------------ [1, 2, 3, 4] [1, 4, 3, 2] [2, 1, 3, 4] [2, 4, 3, 1] [3, 2, 1, 4] [3, 4, 1, 2] [4, 1, 3, 2] [4, 2, 3, 1]
Links
- Carl Pomerance, Coprime permutations, arXiv:2203.03085 [math.NT], 2022.
- Carl Pomerance, Permutations with arithmetic constraints, arXiv:2206.01699 [math.NT], 2022.
Programs
-
Mathematica
a[n_] := a[n] = If[n == 0, 1,Permanent[Table[If[Divisible[i, j] || Divisible[j, i], 1, 0], {i, n}, {j, n}]]]; Table[Print[n, " ", a[n]]; a[n], {n, 0, 22}] (* Jean-François Alcover, Jun 25 2022 *) -
PARI
a(n) = matpermanent(matrix(n, n, i, j, if (!(i%j) || !(j%i), 1, 0))); \\ Michel Marcus, Dec 30 2018
Formula
a(n) = Permanent((x_{ij})) with x_{ij} = 1 if i divides j or j divides i and x_{ij} = 0 otherwise for i,j = 1,...,n. - M. Farrokhi D. G., Dec 30 2018
Extensions
a(0), a(24)-a(30) from Alois P. Heinz, Dec 19 2018
a(31)-a(35) from M. Farrokhi D. G., Dec 30 2018