# P2540: Eventual decrease for distinct cycle lengths in random permutations

- ID: `P2540`
- Reference: `distinct-cycle-length-probability-decreasing`
- Page: https://theoremdb.org/statements/P2540
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(q_n\) be the probability that all cycle lengths of a uniformly random permutation of n elements are distinct. Is \(q_{n+1}<q_n\) for every \(n\ge30\)?

### Remarks

- **Remark.** Repeated cycles of the same length violate the event, even when the cycles contain different labels.
- **Remark.** The ordinary coefficient of \(x^n\) in \(\prod_{k\ge1}(1+x^k/k)\) equals q_n.

### What counts as a solution

- Prove strict decrease for every n at least 30, or give a counterexample n at least 30.

## Status

Exact integer arithmetic proves \(q_n<q_{n-1}\) for every \(31\le n\le5000\); proving the same inequality for every \(n\ge5001\) remains open. [3](#reference-3)

## Work

### Evidence for the current status

**Computation 1 (Strict decrease holds exactly through n=5000).** Exact integer arithmetic proves \(q_n<q_{n-1}\) for every \(31\le n\le5000\); proving the same inequality for every \(n\ge5001\) remains open.

Set \(D=5000!\) and compute the coefficients of the finite product through degree 5000 after scaling by \(D\). Every scaled coefficient is an integer. Indeed, a term indexed by a set \(A\) of distinct positive integers with sum at most 5000 has denominator \(\prod_{a\in A}a\), which divides \(5000!\).

The descending update in the executable artifact constructs \(c_n=Dq_n\) exactly. Direct integer comparisons give
\[
c_n<c_{n-1}\qquad(31\leq n\leq5000).
\]
Across the whole prefix, the last index satisfying \(c_n\geq c_{n-1}\) is \(n=30\). Thus \(q_{30}>q_{29}\), followed by all 4,970 strict decreases certified here.

### Background and intake notes

The exact product recurrence makes long finite verification cheap. The analytic threshold remains the reusable proof target.

- Original intake status: Status not established. No literature search was performed. Permutations with distinct cycle sizes are a standard enumerative class.
- The attractive route removes n+1, shortens its cycle, and aims for a map of good permutations into size n.
- The obstruction is that shortening one cycle can collide with another existing cycle length. A successful injection must track the neighboring forbidden lengths.
- Singularity analysis can prove eventual behavior only with an explicit error smaller than the one-step difference.

- Recorded example: \(q_{30}\approx0.578179345171\) and \(q_{31}<q_{30}\).

### Other known results

- **Theorem 1** (established): The logarithmic derivative of the classical product computes every q_n from earlier coefficients. [3](#reference-3)
- **Proposition 1** (supported): Published analysis gives q_n = e^(-gamma)(1+1/n)+O(log(n)/n^2) and a full expansion. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): The focused audit found the sequence, its limit, and full asymptotics, with no theorem giving the requested threshold. [2](#reference-2) [3](#reference-3) [1](#reference-1) [4](#reference-4)

### Open directions

- **Question 1** (supported): Determine whether q_(n+1) is strictly smaller than q_n for every n at least 30.

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library Python program expands the product with a common factorial denominator and checks every adjacent pair.

### Computational notes

- Exact rational coefficient dynamic programming checked every n through 1000. The last observed increase occurred at n=30, meaning \(q_{30}>q_{29}\); every comparison \(q_{n+1}<q_n\) with \(30\le n<1000\) held. Values at n=50, 100, 200, 500, and 1000 were approximately 0.571685906, 0.566786405, 0.564182473, 0.562566685, and 0.562016610.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `distinct-cycle-length-probability-decreasing`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Philippe Flajolet, Eric Fusy, Xavier Gourdon, Daniel Panario, and Nicolas Pouyanne, A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, arXiv:math/0606370v1 (2006). Philippe Flajolet et al., A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics, Electronic Journal of Combinatorics 13 (2006), R103, Proposition 1; D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms, 2nd ed., 1982, pp. 52-54 https://arxiv.org/abs/math/0606370
   - Also cited at Proposition 1 and the distinct-cycle-length example
   - preprint; reference source; arXiv:math/0606370v1; checked 2026-07-24
   - Source use: citation_only
   - Derives the full root-of-unity asymptotic expansion for distinct-cycle probabilities, without an effective monotonicity threshold.
2. <a id="reference-2"></a>D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica 21 (1972), 379-388. D. H. Lehmer, Acta Arithmetica 21 (1972), 379-388; Flajolet et al., EJC 13 (2006), R103; A. Knopfmacher and R. Warlimont, Australasian Journal of Combinatorics 13 (1996), 151-162 https://doi.org/10.4064/aa-21-1-379-388
   - Also cited at Acta Arithmetica 21 (1972), 379-388
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Proves the limiting constant exp(-gamma) for the reciprocal-weighted distinct-partition model underlying these probabilities.
3. <a id="reference-3"></a>OEIS Foundation Inc., A007838, permutations with distinct cycle lengths (checked 27 July 2026). Generating function and recurrence; D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica 21 (1972), 379-388, Theorem 1 https://oeis.org/A007838
   - Also cited at A007838, generating function and bibliography
   - Also cited at Exact computation in dclp-artifact-integer-prefix-certificate, reproduced 2026-07-24
   - reference_database; reference source; web version checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - Records the distinct-cycle permutation counts, product generating function, and bibliography used to check the recurrence.
   - Source named by the research packet.
4. <a id="reference-4"></a>Arnold Knopfmacher and Richard Warlimont, Counting Permutations and Polynomials with a Restricted Factorization Pattern, Australasian Journal of Combinatorics 13 (1996), 151-162. Section 2, the k=1 distinct-cycle-length case https://ajc.maths.uq.edu.au/pdf/13/ocr-ajc-v13-p151.pdf
   - journal_article; primary source; version of record; checked 2026-07-24
   - Source use: citation_only
   - Places the distinct-cycle product in a general theory of restricted permutation factorization patterns.