A neutral schematic of the objects and relations in the statement.
Problem. Let \(q_n\) be the probability that the cycle lengths of a uniformly random permutation in \(S_n\) are pairwise distinct. Equivalently,
\[
Q(x)=\sum_{n\geq0}q_nx^n=\prod_{k\geq1}\left(1+\frac{x^k}{k}\right).
\]
Determine whether
\[
q_{n+1}<q_n\qquad(n\geq30).
\]
1Status
The mathematical status has not passed editorial review.
1Packet records
5 records
Record
Kind
Assessment
Result
Established
claim · Theorem 1
The logarithmic derivative of the classical product computes every q_n from earlier coefficients.[3]
Relevance to this problem
For Eventual decrease for distinct cycle lengths in random permutations, record dclp-claim-generating-function-recurrence (“A divisor sum gives an exact coefficient recurrence”) records a bound, answer, status fact, or structural consequence. The record states: The logarithmic derivative of the classical product computes every q_n from earlier coefficients.
Evidence
EstablishedA complete argument is recorded and has been reviewed.
Cycle-index enumeration gives
\[
Q(x)=\prod_{k\geq1}\left(1+\frac{x^k}{k}\right).
\]
Define
\[
B_m=\sum_{d\mid m}\frac{(-1)^{m/d-1}}{d^{m/d-1}}.
\]
Expanding the logarithmic derivative factor by factor gives
\[
\frac{xQ'(x)}{Q(x)}=\sum_{m\geq1}B_mx^m.
\]
Coefficient comparison therefore yields the exact recurrence
\[
q_0=1,\qquad nq_n=\sum_{m=1}^nB_mq_{n-m}\quad(n\geq1).
\]
After multiplication by \(n!\), these are the integer permutation counts in OEIS A007838.
Result
Reproduced
claim · Computation 1
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]
Relevance to this problem
For Eventual decrease for distinct cycle lengths in random permutations, record dclp-claim-exact-decrease-through-5000 (“Strict decrease holds exactly through n=5000”) records a bound, answer, status fact, or structural consequence. The record states: 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.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
established
Scope
every comparison q_n < q_(n-1) for 31 <= n <= 5000
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.
Result
Supported
claim · Proposition 1
Published analysis gives q_n = e^(-gamma)(1+1/n)+O(log(n)/n^2) and a full expansion.[1]
Relevance to this problem
For Eventual decrease for distinct cycle lengths in random permutations, record dclp-claim-asymptotic-expansion (“The probabilities tend to Euler's constant exponential”) records a bound, answer, status fact, or structural consequence. The record states: Published analysis gives q_n = e^(-gamma)(1+1/n)+O(log(n)/n^2) and a full expansion.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Greene and Knuth obtained
\[
q_n=e^{-\gamma}\left(1+\frac1n\right)+O\left(\frac{\log n}{n^2}\right).
\]
Flajolet, Fusy, Gourdon, Panario, and Pouyanne derive a full expansion with logarithmic terms and periodic contributions caused by roots of unity. In particular \(q_n\to e^{-\gamma}\). A one-step monotonicity proof needs an explicit remainder bound after differencing, since the leading predicted difference has order \(n^{-2}\). The sources inspected here do not supply such a bound with a threshold.
Trace
Supported
attempt · Route 1
The focused audit found the sequence, its limit, and full asymptotics, with no theorem giving the requested threshold.[2][3][1][4]
Relevance to this problem
For Eventual decrease for distinct cycle lengths in random permutations, record dclp-attempt-literature-audit (“The literature establishes enumeration and precise asymptotics”) documents a concrete method, search boundary, or failed route. The record states: The focused audit found the sequence, its limit, and full asymptotics, with no theorem giving the requested threshold.
Evidence
SupportedBacked by a cited source or by evidence short of a proof.
Lehmer studies the same reciprocal weights on distinct partitions and proves the limit \(e^{-\gamma}\). Greene and Knuth obtain the first useful error term. Flajolet and coauthors derive the full root-of-unity expansion. Knopfmacher and Warlimont place the product in a broader class of restricted cycle types.
Searches using the sequence number, the product, `permutations with distinct cycle lengths`, `monotonicity`, and `decreasing probability` located no primary source proving strict decrease after 30. This audit supports an unresolved status rather than a claim that the question is new.
Artifact
Reproduced
artifact · Artifact 1
A standard-library Python program expands the product with a common factorial denominator and checks every adjacent pair.
Relevance to this problem
For Eventual decrease for distinct cycle lengths in random permutations, record dclp-artifact-integer-prefix-certificate (“Exact scaled-integer coefficient certificate”) supplies evidence or a replay used to check the packet. The record states: A standard-library Python program expands the product with a common factorial denominator and checks every adjacent pair.
Evidence
ReproducedA computation someone reran from the artifact on this page.
Record state
available
Scope
all coefficients and adjacent comparisons through degree 5000
Run
python3 certificate.py
Runtime
Python 3 standard library
Details
The program uses \(D=5000!\) as a common denominator. Its descending updates are exact divisions because each intermediate summand corresponds to a distinct-part set whose denominator divides \(D\). A reproduced run reports `exact_checked_through=5000 last_nondecrease_n=30`.
TheoremDB contributors, “Does the distinct-cycle-length probability decrease after n=30?,” TheoremDB research memory, snapshot of July 24, 2026. https://theoremdb.org/statements/dclp-problem-eventual-strict-decrease
The prefilled request prepares the target and checks drafts. It submits the accepted proof and polls verification through any packet-review handoff.
1References
Reference review is pending for 1 entry. Each affected row names the fields still awaiting review.
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/0606370 (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. ↗preprint · reference source · arXiv:math/0606370v1 · checked 2026-07-24Source use: citation only.For Eventual decrease for distinct cycle lengths in random permutations: Published analysis gives q_n = e^(-gamma)(1+1/n)+O(log(n)/n^2) and a full expansion.Also cited at Proposition 1 and the distinct-cycle-length example.
D. Lehmer, “On reciprocally weighted partitions”. Acta Arithmetica 21 (1972), 379-388. DOI 10.4064/aa-21-1-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. ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Eventual decrease for distinct cycle lengths in random permutations: The focused audit found the sequence, its limit, and full asymptotics, with no theorem giving the requested threshold.Also cited at Acta Arithmetica 21 (1972), 379-388.
Packet source. Generating function and recurrence; D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica 21 (1972), 379-388, Theorem 1. Generating function and recurrence; D. H. Lehmer, On reciprocally weighted partitions, Acta Arithmetica 21 (1972), 379-388, Theorem 1. ↗reference database · reference source · checked 2026-07-24Source use: citation only.For Eventual decrease for distinct cycle lengths in random permutations: The logarithmic derivative of the classical product computes every q_n from earlier coefficients.Also cited at A007838, generating function and bibliography.Also cited at Exact computation in dclp-artifact-integer-prefix-certificate, reproduced 2026-07-24.Source named by the research packet.
Counting permutations and polynomials with a restricted factorization pattern. Section 2, the k=1 distinct-cycle-length case. ↗website · reference source · checked 2026-07-24Reference review pending: relevance note.Source use: citation only.