Why does this connection of increasingly exclusive partitions $P_{n,k}$ to the harmonic series $H_k$ exist?

Question

$\mathbf{SETUP}$

In this previous question, I show how the sum of all cycles of type defined by non-unity partitions of $n$ relates to the derangement numbers / subfactorial $!n$ (number of permutations with no fixed points), to ask what explains the remarkable arithmetic form of the equality.

Famously, $!n$ tends to $e^{-1}$ as a fraction of the factorial $n!$, meaning we can write:

\begin{align} \lim_{n\rightarrow\infty} \left( \sum_{k=0}^{n} \frac{(-1)^k}{k!} = \sum_{\lambda \in P_{n,1}} \frac{1} {2^{\alpha_2} ... n^{\alpha_n} \times \alpha_2! ... \alpha_n!} \equiv \sum_{\lambda \in P_{n,1}} \frac{1}{\Lambda_\lambda} \right) = e^{-1} \end{align}

In that question I define $P_{n,1} \equiv P_{n, \lambda \nsupseteq \{1\}}$ as the set of cycle types formed by all the non-unity partitions of $n$ (all partitions excluding the use of 1). This excludes all permutations that have any fixed points (1-cycles) in its cyclic structure.

$\mathbf{RESULT}$

If one then excludes transpositions also, one defines the group of cycle types that excludes 1-cycles and 2-cycles $P_{n, \lambda \nsupseteq \{1,2\}} \equiv P_{n,2}$, and performs the same sum, taking the limit $n \rightarrow \infty$:

\begin{align} \lim_{n \rightarrow \infty} \sum_{\lambda \in P_{n,2}} \frac{1} {3^{\alpha_3} ... n^{\alpha_n} \times \alpha_3! ... \alpha_n!} = e^{-\frac{3}{2}} = e^{-(1 + \frac{1}{2})} = e^{-H_2} \end{align}

Doing the same for $P_{n,3}$ gives:

\begin{align} \lim_{n \rightarrow \infty} \sum_{\lambda \in P_{n,3}} \frac{1} {4^{\alpha_4} ... n^{\alpha_n} \times \alpha_4! ... \alpha_n!} = e^{-\frac{11}{6}} = e^{-(1 + \frac{1}{2} + \frac{1}{3})} = e^{-H_3} \end{align}

Again for $P_{n,4}$ gives:

\begin{align} \lim_{n \rightarrow \infty} \sum_{\lambda \in P_{n,4}} \frac{1} {5^{\alpha_5} ... n^{\alpha_n} \times \alpha_5! ... \alpha_n!} = e^{-\frac{25}{12}} = e^{-(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4})} = e^{-H_4} \end{align} and so on, where $H_k$ is the $k$th harmonic number!

I do not have a proof of why this seems to be the case, but computer code I wrote confirms this up to the highest $n$ I tried to do ($n \sim 50$ or so).

$\mathbf{QUESTION}$

What explains this remarkable pattern?

I think I've only found something like this result in this paper by Arratia and Tavaré:

https://projecteuclid.org/journals/annals-of-probability/volume-20/issue-3/The-Cycle-Structure-of-Random-Permutations/10.1214/aop/1176989707.full

on the cyclic nature of random permutations... but I am not versed enough in its notation to understand it very well, other than simply recognising it must be describing the same underlying pattern. (The 'result' appears as comment at the end of the proof at the top of page 1581.)

$\mathbf{UPDATE / ANSWER?}$

This answer to the "Name Drawing Problem" describes a recurrence relation that gives intuition to why the harmonic numbers appear in this kind of question... I think.

Answer 1

You are inching towards a very beautiful general result, which doesn't have a great name that I know of, but which I know as "the exponential formula in permutation form." This result is a little difficult to state but well worth it; I wrote an old blog post on it here.

Write $S_n$ for the permutation group on $n$ letters. For a permutation $\pi \in S_n$ write $c_i(\pi)$ for the number of $i$-cycles in the cycle decomposition of $\pi$. Write

$$Z(S_n) = \sum_{\pi \in S_n} \prod_{i=1}^n z_i^{c_i(\pi)};$$

this is called a cycle index polynomial. The $z_i$ are formal variables. The Polya enumeration theorem can be used to write down a generating function for the cycle index polynomials of every symmetric group at once, given by

$$\boxed{ \sum_{n \ge 0} Z(S_n) \frac{t^n}{n!} = \exp \left( \sum_{i \ge 1} z_i \frac{t^i}{i} \right) }.$$

This single generating function contains enormous amounts of information about the statistical and combinatorial properties of cycles of permutations, which it takes a little experience to learn how to extract. In particular, by setting some of the variables $z_i$ to $0$ we can write down generating functions for permutations which do not contain specific cycles, as follows: if $S \subseteq \mathbb{N}$ is any set of positive integers, then the (exponential) generating function for permutations which don't have any $i$-cycles for any $i \in S$ is

$$\exp \left( \sum_{i \not \in S} \frac{t^i}{i} \right).$$

In particular, the (exponential) generating function for permutations which don't have any $i$-cycles for $1 \le i \le k$ is

$$\begin{eqnarray*} \exp \left( \sum_{i \ge k+1} \frac{t^i}{i} \right) &=& \exp \left( \sum_{i \ge 1} \frac{t^i}{i} - \sum_{i=1}^k \frac{t^i}{i} \right) \\ &=& \exp \left( \sum_{i \ge 1} \frac{t^i}{i} \right) \exp \left( - \sum_{i=1}^k \frac{t^i}{i} \right) \\ &=& \exp \left( \ln \frac{1}{1 - t} \right) \exp \left( - \sum_{i=1}^k \frac{t^i}{i} \right) \\ &=& \frac{1}{1 - t} \exp \left( - \sum_{i=1}^k \frac{t^i}{i} \right). \end{eqnarray*}$$

This generating function has a pole at $t = 1$ and so its coefficients converge asymptotically to a constant. This constant tells us the asymptotic probability that a random permutation does not contain any $i$-cycles for $1 \le i \le k$ and is given by taking the residue at $t = 1$, which is

$$\exp \left( - \sum_{i=1}^k \frac{1}{i} \right) = \exp \left( - H_k \right)$$

as desired. We have more generally that the asymptotic probability that a random permutation does not contain any $i$-cycles for $i \in S$ is $\exp \left( - \sum_{i \in S} \frac{1}{i} \right)$, and in fact much more than this: we can extract an asymptotic description of the joint distribution of the number of $i$-cycles for $1 \le i \le k$; see Granville's The Anatomy of Integers and Permutations, and/or this old blog post of mine.

For a reference to the general result, although stated in a different form, see Corollary 5.1.8 in Stanley's Enumerative Combinatorics, Volume II, and see also Proposition II.4 in Flajolet and Sedgewick's Analytic Combinatorics, and section 3.5 of Wilf's Generatingfunctionology. These last two are legally freely available online to download at the links. Wilf's approach to this material uses some custom terminology that I personally find a little awkward; Flajolet and Sedgewick work in an intimidating level of generality but personally I find their setup more streamlined and elegant, and their book is packed with many interesting detailed examples of the methods they describe.