For the numbers $1, \ldots, N$, how many ways can I arrange them such that either:
- The number at $i$ is evenly divisible by $i$, or
- $i$ is evenly divisible by the number at $i$.
Example: for $N = 2$, we have:
$\{1, 2\}$
- number at $i = 1$ is $1$ and is evenly divisible by $i = 1$.
- number at $i = 2$ is $2$ and $i = 2$ is evenly divisible by $2$.
$\{2, 1\}$
- number at $i = 1$ is $2$ and is evenly divisible by $i = 1$.
- number at $i = 2$ is $1$ and $i = 1$ is evenly divisible by $1$.
so there are two such arrangements for $N = 2$.
[reformulation that might be useful]
The following matrix tells if the number $j$ can be the $i$-th term of the sequence ($1$ means 'true', $0$ means 'false'). The general term is $M_{ij}$ and the index counting starts at $1$.
$$M = \begin{bmatrix}[1] & [1] & [1] & [1] & [1] & [1] & [1] & [1] & [1] & \cdots \\ (1) & [1 & 0] & [1 & 0] & [1 & 0] & [1 & 0] & \cdots\\ (1) & 0 & [1 & 0 & 0] & [1 & 0 & 0] & [1 & \cdots\\ (1) & (1) & 0 & [1 & 0 & 0 & 0] & [1 & 0 & \cdots\\ (1) & 0 & 0 & 0 & [1 & 0 & 0 & 0 & 0] & \cdots\\ (1) & (1) & (1) & 0 & 0 & [1 & 0 & 0 & 0 & \cdots\\ (1) & 0 & 0 & 0 & 0 & 0 & [1 & 0 & 0 & \cdots\\ (1) & (1) & 0 & (1) & 0 & 0 & 0 & [1 & 0 & \cdots\\ (1) & 0 & (1) & 0 & 0 & 0 & 0 & 0 & [1 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$
Below the main diagonal, each $(1)$ value indicates that $j$ divides $i$. In the rest of each row, we have a pattern for the multiples of $i$, which is a 'one' followed by $i-1$ 'zeroes': $\begin{bmatrix}1&0&0&\cdots&0\end{bmatrix}$.
Note that $M$ is $\textbf{symmetric}$! So the pattern for the multiples can be seen in the columns too, even for the values below the main diagonal:
$$M = \begin{bmatrix}\color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{1} & \color{blue}{\cdots} \\ \color{blue}{1} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{0} & \color{green}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{0} & \color{orange}{1} & \color{orange}{0} & \color{orange}{0} & \color{orange}{0} & \color{orange}{1} & \color{orange}{0} & \color{orange}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{0} & \color{orange}{0} & \color{magenta}{1} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{0} & \color{magenta}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{1} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{1} & \color{brown}{0} & \color{brown}{0} & \color{brown}{0} & \color{brown}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{0} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{1} & \color{gray}{0} & \color{gray}{0} & \color{gray}{\cdots}\\ \color{blue}{1} & \color{green}{1} & \color{red}{0} & \color{orange}{1} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{0} & \color{cyan}{1} & \color{cyan}{0} & \color{cyan}{\cdots}\\ \color{blue}{1} & \color{green}{0} & \color{red}{1} & \color{orange}{0} & \color{magenta}{0} & \color{brown}{0} & \color{gray}{0} & \color{cyan}{0} & \color{teal}{1} & \color{teal}{\cdots}\\ \color{blue}{\vdots} & \color{green}{\vdots} & \color{red}{\vdots} & \color{orange}{\vdots} & \color{magenta}{\vdots} & \color{brown}{\vdots} & \color{gray}{\vdots} & \color{cyan}{\vdots} & \color{teal}{\vdots} & \ddots \end{bmatrix}$$
Once we have this matrix, the problem can be reformulated as:
Which I believe is equivalent to what Andrew Szymczak said in the comments: "we need to count the number of cycle partitions of the undirected divisibility graph (edge if i|j or j|i). This is equivalent to computing the permanent of the adjacency matrix, which is in general NP-hard."
As a small development to the problem, we might define an upper bound for the number of valid sequences.
Note that any prime number $p$ such that $\frac{N}{2} < p \leq N$ has only two possible positions ($i=1$ and $i=p$). And that, if one of these prime numbers is used as the first term, then the $p$-th term must be $1$.
Therefore, if $m$ is the number of prime numbers in $\left]\frac{N}{2},N\right]$, the number of valid sequences can be, at most, $\boxed{[N-m]! + m\,[N-m-1]!}$.
For $N$ ranging from $2$ to $10$, this upper bound is $\{2,3,8,10,144,168,960,6\,480,403\,200\}$. It corresponds to the exact number of valid sequences only for $N\leq 5$, after that, it rapidly becomes much larger than the exact number. Evidently, to have lower upper bounds, more terms must be considered in the analysis (not only a few prime numbers).