Let $S$ be a permutation on $[n]$.
The cycle structure for $S$ is well known. For example, the expected number of cycles $C$ is given by $H_n$, the harmonic number. We also know in the limit that the distribution is approximately Gaussian with mean and variance $\log n$.
Let $0<r<n$. But what about permutations conditioned on the number of cycles being at least $r$.
Obviously now a lower bound for the number of cycles is $r$.
I know the expected number of cycles can be written as
$$ \frac{\sum_{i=k}^n i.s(n,i)}{\sum_{i=k}^n s(n,i)}$$
where $s(n,m)$ is the unsigned stirling number of the first kind. But I don't know how to simplify that.
My guess is that the expected number of cycles would be asymptotically something like $$r+\log (n-r)?$$
Is there a better way to count this number, or can this be simplified (asymptotically)?
If it helps, I would be interested for example when $r\approx \sqrt{n}$.
Are there any references for this problem or similar? I couldn't really find anything that discussed this problem. The main things I could find were things permutations conditioned on the cycle lengths or with certain cycle structures.
Best Answer
First of all, there is a great set of notes by Kevin Ford that I suggest you read and cite as much as possible. Section 4 is particularly relevant.
https://arxiv.org/abs/2104.12019
As to your question, since the number of cycles is asymptotically Poisson with mean $\log n$, there is a critical change in behavior around $r = \log n$. Since you appear to be most interested in $r \gg \log n$, I will focus on that case. Based on the Poisson model it is reasonable to expect that almost all permutations with at least $r$ cycles have exactly $r$ cycles, and the expectation should also be close to $r$.
When $1.01 \log n < r < 100 \log n$ (adjust constants as you like) this follows from Corollary 1.6 and Theorem 1.11 in Ford's notes.
When $r$ is enormous (you mention $\sqrt n$), these methods do not seem to be quite the right ones, but still it is reasonable to expect that the vast majority of permutations with at least $r$ cycles have exactly $r$ cycles.