How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

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$$.

• Point of interest: Where did this problem come from? Did you make it up, or did it come from a book, or what? Jul 19, 2016 at 17:19
• As I understand the question, the number of combinations for $N = 1$ to $10$ are $1, 2, 3, 8, 10, 36, 41, 132, 250, 700$. I couldn't find this sequence in OEIS, but it's possible I've made an error somewhere. Jul 19, 2016 at 18:08
• We're looking for the number of partitions into directed cycles of the undirected Hasse diagram of the divisibility poset. Jul 19, 2016 at 20:54
• $T_{32} = 33923638848$... As @barto said, 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. Here is my $\mathcal{O}(n 2^n)$ python implementation that uses the BBFG formula. Sep 17, 2017 at 6:24
• In 2018, OEIS A320843 was added for the sequence in question. Dec 20, 2020 at 17:37

[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:

• what is the number of row-permutations (or column-permutations) that keep the diagonal full of 'ones'?

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).