What is the probability distribution of the maximum cycle length in a permutation game? There is a "classic" counterintuitive scenario, in which you have $N$ boxes, $N$ players. Player $i$ has a dollar bill tagged with the number $i$. Each player places their dollar bill into a box at random, where each box is tagged with a distinct number between $1$ and $N$.
Now each of the $N$ players gets to examine $n$ boxes ($n<N$), and if all of them find their associated bill, then each player receives $R>1$ dollars. Otherwise they all lose their starting bill. The players can coordinate before the game starts but cannot communicate after they begin opening boxes.
The "winning strategy", at least if $n$ is not too much smaller than $N$, is for player $i$ to open box $i$, then the box whose number is printed on the bill they found, etc. The idea is that if you connect $i$ to $j$ if and only if box $i$ contains bill $j$, then you get a decomposition of $\{ 1,2,\dots,N \}$ into cycles.
Now if all players are using this strategy, then they win if and only if the largest cycle contains at most $n$ boxes. This condition is sufficient for victory, because player $i$ will find bill $i$ when the procedure would instruct them to open box $i$ a second time. This condition is also necessary, because for every cycle there exists at least one player that will traverse it, and they will only win if they can get all the way to the end of the cycle before being stopped.
What is counterintuitive is that, if all players use this strategy, then the group wins with a probability far greater than $(n/N)^N$; for example if $n=50,N=100$ then the winning probability is about 0.31 while the "choose randomly" strategy wins with probability $2^{-100} \approx 8 \cdot 10^{-31}$. The usual intuitive explanation for how this can happen even though each player separately has only a probability of $n/N$ to find their bill is that the "winning strategy" makes it so that the players tend to either all find their bill or else many of them don't. And indeed, in support of that explanation, one can see that if any players don't find their bill, then at least $n+1$ players don't.
The usual question is, given $n,N,R$, and teammates that are perfect rational agents, do you take the bet? The additional information needed to answer that is the probability to win.
With that in mind, my question is: is there an explicit formula for the probability that the players win this game as a function of $n$ and $N$? My question can be rephrased in math jargon as: given a random directed graph on $N$ vertices where each vertex has out-degree $1$ and in-degree $1$, what is the probability distribution of the size of the largest cycle in the graph?
 A: While not an explicit formula, there is a very good asymptotic estimate for this number; it was proved by Goncharov in 1944 (see for example Section 1.4 of this paper by Granville).
In that notation, let's think about the probability that a randomly chosen permutation of $N$ numbers has all of its cycles less than $N/u$ in size. (In the OP's formulation, $n=N/u$ and hence $u=N/n$.) As $N$ gets large, the probability that a random permutation of $N$ numbers has all cycles smaller than $N/u$ approaches a particular constant $\rho(u)$ (the Dickman rho function).
The exact function $\rho(u)$ is pretty ugly, but there are two observations we can make about it.
First, $\rho(2) = 1-\ln 2 \approx 0.306853$, which explains the $31\%$ the OP observed; if $N=1000$ and $n=500$, we would be even closer to $1-\ln2$.
Second, $\rho(u)$ is roughly $u^{-u}$ when $u$ is large; in the OP's notation, that's about $(N/n)^{-N/n} = (n/N)^{N/n}$, which is the $n$th root of the "choose random" probability (that is, way higher). One way to view this is that when $N$ is large and $n$ is rather smaller than $N$, the probabilility of winning one "choose randomly" game is approximately the same as winning $n$ consecutive "winning strategy" games! That's how much better this strategy is than choosing randomly.
