A conjecture harmonic numbers

Question

I will outlay a few observations applying to the harmonic numbers that may be interesting to prove (if it hasn't already been proven).

From the Online Encyclopedia of Positive Integers we have:

$a(n)$ is the number of permutations $p$ of $\{1,\ldots,n\}$ such that the minimum number of block interchanges required to sort the permutation $p$ to the identity permutation is maximized.
$1, 1, 5, 8, 84, 180, 3044, 8064, 193248, 604800,\ldots$ (https://oeis.org/A260695)

Consider the following harmonic numbers:

$$1 + 1/2 = (1 + 2)\cdot 1/2!$$ $$1 + 1/2 + 1/3 + 1/4 = (1 + 2 + 3 + 4)\cdot 5/4!$$ $$1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 = (1 + 2 + 3 + 4 + 5 + 6)\cdot 84/6!$$ $$1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)\cdot 3044/8!$$

and so on.

Therefore, the following generalization suggests itself:

$$1 + 1/2 + 1/3 + 1/4 + \cdots + 1/2n = (2n^2 + n)\cdot a(2n - 1)/(2n)!$$

If this hasn't been proven, then I will leave it as a conjecture.

Cheers,

Robert

Answer 1

We can use the characterization by Christie. Let $\pi \in S_n$. Add a fixed point $0$ to $\pi$, and let $c$ be the cycle $(0, 1, \ldots, n)$. Then the smallest number of block interchanges to sort $\pi$ is equal to $\frac{n + 1 - t}{2}$, where $t$ is the number of cycles in decomposition of $c \pi^{-1} c^{-1} \pi$. When $n$ is odd, the maximum value is obtained at $t = 2$, and we are counting $\pi$ such that $c \pi^{-1} c^{-1} \pi$ decomposes into two cycles. Note that $\pi^{-1} c^{-1} \pi$ is itself a cycle, and for any cycle $d$ the equation $d = \pi^{-1} c^{-1} \pi$ has a single solution for $\pi$ (under $\pi(0) = 0$).

According to a result of Zagier (a different presentation here), the product $cd$ of two random $2n$-cycles $c, d$ decomposes into exactly two cycles with probability $2s_{2n + 1, 2} / (2n + 1)! = 2H_{2n} / (2n + 1)$, where $s_{2n + 1, 2}$ is the Stirling number of the first kind. Since $c$ is fixed, we immediately have $a(2n - 1) = (2n - 1)! \frac{2H_{2n}}{2n + 1} = (2n)! \frac{H_{2n}}{n(2n + 1)}$.

For $a(2n)$ we want to count the number of $(2n + 1)$-cycles $d$ such that $cd$ is a $(2n + 1)$-cycle. Using the same formula, we have an even simpler relation $a(2n) = \frac{(2n)!}{n + 1}$.

Answer 2

The sequence OEIS A260695 can be seen as the interweaving of nonzero Hultman numbers $\mathcal{H}(n,k)$ for $k=1$ and $k=2$. Namely, $$a(n) = \mathcal{H}(n,1+(n\bmod 2)).$$

It is known that $\mathcal{H}(n,k)$ is nonzero only when $n-k$ is odd, in which case its value is given by $$\mathcal{H}(n,k) = \frac{c(n+2,k)}{\binom{n+2}2},$$ where $c(\cdot,\cdot)$ are unsigned Stirling numbers of first kind.

Noticing that $c(n+2,2)=(n+1)!H_{n+1}$, we obtain the same formulae as in Mikhail's answer.