A conjecture harmonic numbers

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

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

• Very nice! I've updated the OEIS sequence accordingly. Commented Nov 20, 2020 at 15:34

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.