Problem 902: Permutation Cycles

Mathematical Analysis

Cycle Structure of Permutations

Every permutation $\sigma \in S_n$ decomposes uniquely into disjoint cycles. The cycle type of $\sigma$ is the partition $\lambda = (1^{c_1} 2^{c_2} \cdots n^{c_n})$ where $c_k$ is the number of $k$-cycles. The number of permutations with cycle type $\lambda$ is:

This follows because each $k$-cycle can be written in $k$ equivalent ways (cyclic rotations), and cycles of the same length are interchangeable.

Exponential Generating Functions for Bounded Cycles

The exponential generating function (EGF) for the class of permutations with all cycle lengths at most $m$ is a foundational result in analytic combinatorics (Flajolet & Sedgewick, Ch. II):

This arises because the EGF for a single cycle of length $k$ is $x^k/k$, and the exponential formula for labeled combinatorial structures yields $\exp(\cdot)$ when structures are sets of components.

Theorem (Exponential Formula). If $C(x) = \sum_{k \ge 1} c_k x^k/k!$ is the EGF for connected structures, then the EGF for sets of such structures is $\exp(C(x))$.

Proof. A permutation with all cycles $\le m$ is a set of cycles, each of length $\le m$. The EGF for a single $k$-cycle is $\frac{(k-1)!}{k!} x^k = \frac{x^k}{k}$ (there are $(k-1)!$ distinct $k$-cycles on $k$ labeled elements). Summing over allowed lengths and applying the exponential formula gives (2). $\square$

Inclusion-Exclusion for Exact Maximum

Define $a(n, m) = n! [x^n] F_m(x)$, the number of permutations of $[n]$ with all cycle lengths $\le m$. Then:

This is exact: permutations with max cycle $= 10$ equals those with max cycle $\le 10$ minus those with max cycle $\le 9$.

Alternative: Direct Cycle-Building Recurrence

Lemma. Let $D(s, m)$ be the number of permutations of $[s]$ with all cycles $\le m$. Then:

Proof. Element 1 lies in some $k$-cycle. Choose $k-1$ other elements from $\{2, \ldots, s\}$: $\binom{s-1}{k-1}$ ways. Arrange them in a cycle with element 1: $(k-1)!$ ways. The remaining $s-k$ elements form a permutation with all cycles $\le m$. $\square$

Note that $\binom{s-1}{k-1}(k-1)! = \frac{(s-1)!}{(s-k)!}$, the falling factorial.

Concrete Verification

For $n = 4$, $\lfloor 4/2 \rfloor = 2$. The 24 permutations of $S_4$ by cycle type:

So $C(4) = 6 + 3 = 9$. Verification: $a(4,2) = 1 + 6 + 3 = 10$, $a(4,1) = 1$, $C(4) = 10 - 1 = 9$. Correct.

Verification Table for Small $n$

The fraction $C(n)/n!$ stabilizes around 0.43-0.46, reflecting that roughly half of all permutations have their longest cycle covering about half the elements (the Golomb-Dickman constant governs the asymptotic distribution of the longest cycle).

Connection to the Golomb-Dickman Constant

The probability that the longest cycle in a random permutation of $[n]$ has length $\le \alpha n$ converges to the Dickman function $\rho(1/\alpha)$ as $n \to \infty$. The density of the longest cycle length near $\alpha = 1/2$ is related to:

So the probability that the longest cycle exceeds $n/2$ is roughly $1 - \rho(2) = \ln 2 \approx 0.6931$. The probability of max cycle exactly $n/2$ involves the derivative of $\rho$ and is $O(1/n)$ in the continuous limit, but for the discrete problem the value is well-defined.

Derivation of the EGF Computation

Step 1: Build the EGF Polynomial

Compute $F_m(x) = \exp\!\left(\sum_{k=1}^{m} x^k/k\right)$ as a truncated power series up to degree $n$:

1. Compute $g(x) = \sum_{k=1}^{m} x^k/k$ (a polynomial of degree $m$).

2. Exponentiate: $F_m(x) = \exp(g(x))$ via the identity $F'(x) = g'(x) F(x)$, giving the recurrence:

   $$[x^j] F_m = \frac{1}{j} \sum_{k=1}^{\min(j,m)} [x^{j-k}] F_m \cdot x^{k-1} \cdot [x^{k-1}] g'(x)$$

   More concretely, if $f_j = [x^j] F_m$ and noting $g'(x) = \sum_{k=0}^{m-1} x^k$:

   $$f_j = \frac{1}{j} \sum_{i=1}^{\min(j,m)} i \cdot g_i \cdot f_{j-i} \tag{5}$$

   where $g_i = 1/i$ for $1 \le i \le m$.

Step 2: Extract Counts

$a(n, m) = n! \cdot f_n$.

Step 3: Modular Arithmetic

For exact computation (feasible for $n = 20$), use rational arithmetic. For modular: use Fermat’s little theorem for divisions modulo $10^9 + 7$.

Proof of Correctness

Theorem. Algorithm (3) with EGF computation (2) correctly computes $C(n)$.

Proof. The EGF $F_m(x)$ encodes precisely the class of permutations with all cycle lengths in $\{1, \ldots, m\}$ by the exponential formula. The coefficient extraction $a(n, m) = n! [x^n] F_m(x)$ counts such permutations of $[n]$. The difference $a(n, m) - a(n, m-1)$ isolates those with at least one cycle of length exactly $m$ and no longer cycle. $\square$

Complexity Analysis

• EGF polynomial method: Building $F_m(x)$ to degree $n$ takes $O(nm)$ per coefficient via recurrence (5), total $O(n^2 m)$. For $n = 20$, $m = 10$: roughly $20^2 \times 10 = 4000$ operations.
• Direct cycle recurrence (4): $O(nm)$ per value of $s$, total $O(n^2 m)$, same asymptotic cost.
• Brute-force enumeration: $O(n! \cdot n)$ — completely infeasible for $n = 20$ ($20! \approx 2.4 \times 10^{18}$).
• Space: $O(n)$ for the DP array.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 902: Permutation Cycles
 *
 * Count permutations of {1,...,20} whose longest cycle has length exactly
 * floor(20/2) = 10.  Answer: C(20) = a(20,10) - a(20,9) mod 10^9+7.
 *
 * Two methods:
 *   1. Cycle-building DP:  D(s,m) = sum_{k=1}^{min(s,m)} fallfact(s-1,k-1) * D(s-k,m)
 *   2. EGF polynomial:     F_m(x) = exp(sum_{k=1}^{m} x^k/k), extract n! * [x^n]
 *
 * Both use exact 128-bit integers for n <= 20 (no overflow issues).
 */

const long long MOD = 1e9 + 7;
const int N = 20;

/*
 * Method 1: Cycle-building DP (exact, __int128 for safety)
 *
 * D(0) = 1
 * D(s) = sum_{k=1}^{min(s,m)} (s-1)(s-2)...(s-k+1) * D(s-k)
 *
 * The factor (s-1)!/(s-k)! counts: choose k-1 elements to join element 1
 * in a k-cycle, then arrange them cyclically.
 */
__int128 count_dp(__int128 *dp, int m) {
    dp[0] = 1;
    for (int s = 1; s <= N; s++) {
        dp[s] = 0;
        __int128 coeff = 1;  // falling factorial (s-1)(s-2)...(s-k+1)
        for (int k = 1; k <= min(s, m); k++) {
            if (k >= 2)
                coeff *= (s - k + 1);
            dp[s] += coeff * dp[s - k];
        }
    }
    return dp[N];
}

/*
 * Method 2: EGF with rational arithmetic (using double for moderate n)
 * For exact verification of small cases.
 */
long long count_egf_mod(int n, int m, long long mod) {
    // Compute a(n, m) mod p using the EGF recurrence
    // f[j] = [x^j] F_m(x), computed via f'(x) = g'(x)*f(x)
    // where g(x) = sum_{k=1}^{m} x^k/k
    // Recurrence: j * f[j] = sum_{i=1}^{min(j,m)} i * (1/i) * f[j-i]
    //                       = sum_{i=1}^{min(j,m)} f[j-i]
    // So: f[j] = (1/j) * sum_{i=1}^{min(j,m)} f[j-i]
    // Then a(n,m) = n! * f[n]

    vector<long long> f(n + 1, 0);
    f[0] = 1;

    auto modinv = [&](long long a) -> long long {
        long long result = 1, exp = mod - 2;
        a %= mod;
        while (exp > 0) {
            if (exp & 1) result = result * a % mod;
            a = a * a % mod;
            exp >>= 1;
        }
        return result;
    };

    for (int j = 1; j <= n; j++) {
        long long s = 0;
        for (int i = 1; i <= min(j, m); i++) {
            s = (s + f[j - i]) % mod;
        }
        f[j] = s % mod * modinv(j) % mod;
    }

    // Multiply by n!
    long long fact = 1;
    for (int i = 1; i <= n; i++)
        fact = fact * i % mod;

    return f[n] % mod * fact % mod;
}

int main() {
    int half = N / 2;  // = 10

    // Method 1: Cycle DP (exact)
    __int128 dp1[N + 1], dp2[N + 1];
    __int128 a1 = count_dp(dp1, half);
    __int128 b1 = count_dp(dp2, half - 1);
    long long ans1 = (long long)((a1 - b1) % MOD);
    if (ans1 < 0) ans1 += MOD;

    // Method 2: EGF mod p
    long long a2 = count_egf_mod(N, half, MOD);
    long long b2 = count_egf_mod(N, half - 1, MOD);
    long long ans2 = (a2 - b2 + MOD) % MOD;

    // Cross-check
    assert(ans1 == ans2);

    cout << ans1 << endl;  // 436180200
    return 0;
}

"""
Problem 902: Permutation Cycles

Let C(n) be the number of permutations of {1,2,...,n} whose longest cycle
has length exactly floor(n/2). Find C(20) mod 10^9+7.

Key identity: C(n) = a(n, floor(n/2)) - a(n, floor(n/2) - 1)
where a(n, m) = number of permutations of [n] with all cycle lengths <= m.

The EGF for such permutations is:
    F_m(x) = exp(sum_{k=1}^{m} x^k / k)

Methods implemented:
    1. EGF polynomial truncation (exact rational arithmetic)
    2. Cycle-building DP recurrence
    3. Direct enumeration for small n (verification)
"""

from fractions import Fraction
from math import factorial, comb
from collections import Counter
import random

MOD = 10**9 + 7

def count_perms_max_cycle_le_egf(n: int, m: int):
    """Count permutations of [n] with all cycles <= m using EGF.

    F_m(x) = exp(sum_{k=1}^{m} x^k / k), then a(n,m) = n! * [x^n] F_m(x).
    We compute F_m(x) by multiplying exp(x^k/k) for k = 1..m.
    """
    poly = [Fraction(0)] * (n + 1)
    poly[0] = Fraction(1)
    for k in range(1, m + 1):
        new_poly = [Fraction(0)] * (n + 1)
        for i in range(n + 1):
            if poly[i] == 0:
                continue
            # Multiply by exp(x^k / k) = sum_{j>=0} x^{jk} / (k^j * j!)
            coeff = Fraction(1)
            for j in range(0, (n - i) // k + 1):
                new_poly[i + j * k] += poly[i] * coeff
                coeff /= (k * (j + 1))
        poly = new_poly
    return int(poly[n] * factorial(n))

def count_perms_max_cycle_le_dp(n: int, m: int):
    """Count permutations of [n] with all cycles <= m using DP.

    D(s) = sum_{k=1}^{min(s,m)} C(s-1, k-1) * (k-1)! * D(s-k)
         = sum_{k=1}^{min(s,m)} (s-1)! / (s-k)! * D(s-k)

    Element 1 is placed in a k-cycle: choose k-1 companions, arrange cyclically.
    """
    dp = [0] * (n + 1)
    dp[0] = 1
    for s in range(1, n + 1):
        total = 0
        falling = 1  # (s-1)! / (s-k)! for current k
        for k in range(1, min(s, m) + 1):
            if k > 1:
                falling *= (s - k + 1)
                falling //= (k - 1)
                # Actually: C(s-1,k-1)*(k-1)! = (s-1)!/(s-k)!
            # Recompute properly
            pass
        # Cleaner: direct falling factorial
        coeff = 1  # will be (s-1)!/(s-k)! = (s-1)(s-2)...(s-k+1)
        for k in range(1, min(s, m) + 1):
            if k == 1:
                coeff = 1
            else:
                coeff *= (s - k + 1)
            total += coeff * dp[s - k]
        dp[s] = total
    return dp[n]

def max_cycle_length(perm: list):
    """Find the longest cycle in a permutation."""
    n = len(perm)
    visited = [False] * n
    max_len = 0
    for i in range(n):
        if not visited[i]:
            length = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = perm[j]
                length += 1
            max_len = max(max_len, length)
    return max_len

def count_exact_brute(n: int, target: int):
    """Brute-force count of permutations with max cycle = target. Only for small n."""
    from itertools import permutations
    count = 0
    for perm in permutations(range(n)):
        if max_cycle_length(list(perm)) == target:
            count += 1
    return count

# Solve
N = 20
HALF = N // 2  # = 10

a_egf = count_perms_max_cycle_le_egf(N, HALF)
b_egf = count_perms_max_cycle_le_egf(N, HALF - 1)
ans_egf = (a_egf - b_egf) % MOD

a_dp = count_perms_max_cycle_le_dp(N, HALF)
b_dp = count_perms_max_cycle_le_dp(N, HALF - 1)
ans_dp = (a_dp - b_dp) % MOD

assert ans_egf == ans_dp, f"Method mismatch: EGF={ans_egf}, DP={ans_dp}"

# Cross-check: exact values should match
assert a_egf == a_dp, f"a mismatch: {a_egf} vs {a_dp}"
assert b_egf == b_dp, f"b mismatch: {b_egf} vs {b_dp}"

for test_n in [4, 6, 8]:
    target = test_n // 2
    a_bf = count_perms_max_cycle_le_egf(test_n, target)
    b_bf = count_perms_max_cycle_le_egf(test_n, target - 1)
    c_bf = a_bf - b_bf
    c_exact = count_exact_brute(test_n, target)
    assert c_bf == c_exact, f"n={test_n}: EGF={c_bf}, brute={c_exact}"

print(ans_egf)