3 deleted 64 characters in body

This isn't an answer to your question, but without any restrictions, the expected number of $r$-cycles in a permutation of at least $r$ elements is $\frac{1}{r}$, so the expected number of cycles in a permutation in $S_n$ is $1 + \frac{1}{2} + ... + \frac{1}{n} = H_n \sim \log n$. So this provides a heuristic upper bound on the number you're actually looking for.

Edit: Okay, so here's one way to get an answer. It's not elegant, but it's fairly automatic. Our starting point is the exponential formula

$$\sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$

where $Z_{S_m}$ is the cycle index polynomial of $S_n$. We want to ignore fixed points, so we set $z_1 = 0$. We want to count the remaining types of cycles together, so we set $z_2 = z_3 = ... = z$. Then

$$\sum_{m \ge 0} \frac{1}{m!} \sum_{\sigma} z^{c(\sigma)} t^m = \exp \left( \frac{zt^2}{2} + \frac{zt^3}{3} + ... \right) = e^{-zt} \frac{1}{(1 - t)^z}$$

where the inner sum is over permutations in $S_m$ with no fixed points and $c(\sigma)$ denotes the number of cycles. To compute the expected number of cycles we now need to differentiate with respect to $z$ and set it equal to $1$. Using logarithmic differentiation gives

$$\sum_{m \ge 0} \frac{1}{m!} (\sum_{\sigma} c(\sigma)) t^m = e^{-t} \frac{1}{1 - t} \left( \log \frac{1}{1-t} - t \right).$$

Now the number we are actually interested in is $\frac{1}{!m} \sum_{\sigma} c(\sigma)$ but this essentially differs only by a multiple of $e$ so it suffices to analyze the asymptotics of the above sequence. Note that

$$\frac{1}{1-t} \left( \log \frac{1}{1-t} - t \right) = \sum_{n \ge 0} (H_n - 1) t^n$$

so it suffices to analyze the effect of the factor $e^{-t}$. This gives the sequence

$$c_n = \sum_{k=0}^{n} (-1)^k \frac{H_{n-k} - 1}{k!}$$

and by taking, say, the $\frac{n}{2}$ largest terms it's not hard to believe that $c_n \sim \frac{H_n}{e}$. So my money is on the constant you're looking for being equal to $1$, or perhaps being a function which approaches $1$ rather slowly.1$. 2 added 1928 characters in body This isn't an answer to your question, but without any restrictions, the expected number of$r$-cycles in a permutation of at least$r$elements is$\frac{1}{r}$, so the expected number of cycles in a permutation in$S_n$is$1 + \frac{1}{2} + ... + \frac{1}{n} = H_n \sim \log n$. So this provides a heuristic upper bound on the number you're actually looking for. Edit: Okay, so here's one way to get an answer. It's not elegant, but it's fairly automatic. Our starting point is the exponential formula $$\sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right)$$ where$Z_{S_m}$is the cycle index polynomial of$S_n$. We want to ignore fixed points, so we set$z_1 = 0$. We want to count the remaining types of cycles together, so we set$z_2 = z_3 = ... = z$. Then $$\sum_{m \ge 0} \frac{1}{m!} \sum_{\sigma} z^{c(\sigma)} t^m = \exp \left( \frac{zt^2}{2} + \frac{zt^3}{3} + ... \right) = e^{-zt} \frac{1}{(1 - t)^z}$$ where the inner sum is over permutations in$S_m$with no fixed points and$c(\sigma)$denotes the number of cycles. To compute the expected number of cycles we now need to differentiate with respect to$z$and set it equal to$1$. Using logarithmic differentiation gives $$\sum_{m \ge 0} \frac{1}{m!} (\sum_{\sigma} c(\sigma)) t^m = e^{-t} \frac{1}{1 - t} \left( \log \frac{1}{1-t} - t \right).$$ Now the number we are actually interested in is$\frac{1}{!m} \sum_{\sigma} c(\sigma)$but this essentially differs only by a multiple of$e$so it suffices to analyze the asymptotics of the above sequence. Note that $$\frac{1}{1-t} \left( \log \frac{1}{1-t} - t \right) = \sum_{n \ge 0} (H_n - 1) t^n$$ so it suffices to analyze the effect of the factor$e^{-t}$. This gives the sequence $$c_n = \sum_{k=0}^{n} (-1)^k \frac{H_{n-k} - 1}{k!}$$ and by taking, say, the$\frac{n}{2}$largest terms it's not hard to believe that$c_n \sim \frac{H_n}{e}$. So my money is on the constant you're looking for being equal to$1$, or perhaps being a function which approaches$1$rather slowly. 1 This isn't an answer to your question, but without any restrictions, the expected number of$r$-cycles in a permutation is$\frac{1}{r}$, so the expected number of cycles in a permutation in$S_n$is$1 + \frac{1}{2} + ... + \frac{1}{n} = H_n \sim \log n\$. So this provides a heuristic upper bound on the number you're actually looking for.