51
$\begingroup$

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

$\endgroup$
22
  • 5
    $\begingroup$ Point of interest: Where did this problem come from? Did you make it up, or did it come from a book, or what? $\endgroup$
    – Brian Tung
    Jul 19, 2016 at 17:19
  • 13
    $\begingroup$ 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. $\endgroup$
    – Brian Tung
    Jul 19, 2016 at 18:08
  • 2
    $\begingroup$ We're looking for the number of partitions into directed cycles of the undirected Hasse diagram of the divisibility poset. $\endgroup$ Jul 19, 2016 at 20:54
  • 2
    $\begingroup$ $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. $\endgroup$ Sep 17, 2017 at 6:24
  • 14
    $\begingroup$ In 2018, OEIS A320843 was added for the sequence in question. $\endgroup$ Dec 20, 2020 at 17:37

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .