Problem 928: Catalan Number Variants

Mathematical Foundation

Theorem 1 (Ratio Recurrence). The Catalan numbers satisfy $C_0 = 1$ and

Proof. Compute the ratio directly:

Simplifying: $\frac{(2n+2)(2n+1)}{(n+1)(n+1)} \cdot \frac{n+1}{n+2} = \frac{2(2n+1)}{n+2}$. $\square$

Theorem 2 (Segner Convolution Recurrence). For all $n \geq 0$:

Proof. Consider Dyck paths from $(0,0)$ to $(2(n+1), 0)$. Each such path first touches the $x$-axis at some step $2(i+1)$ (the first return). The path decomposes as: an up-step, a Dyck path of semilength $i$ (shifted up by 1), a down-step, and a Dyck path of semilength $n - i$. Since the first part has $C_i$ choices and the second has $C_{n-i}$ choices, summing over all first-return times $i = 0, \ldots, n$ gives the recurrence. $\square$

Theorem 3 (Generating Function). The ordinary generating function $C(x) = \sum_{n=0}^{\infty} C_n x^n$ satisfies the functional equation $C(x) = 1 + x\,C(x)^2$, with explicit solution

Proof. Theorem 2 states $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$, which means $\sum_{n \geq 0} C_{n+1} x^n = C(x)^2$. Multiplying by $x$: $C(x) - 1 = x \, C(x)^2$, i.e., $C(x) = 1 + x\,C(x)^2$. Solving this quadratic in $C(x)$:

The minus sign is chosen to ensure $C(0) = 1$ (by L’Hopital or series expansion). $\square$

Theorem 4 (Asymptotic Growth). As $n \to \infty$:

Proof. Using Stirling’s approximation $n! \sim \sqrt{2\pi n}\,(n/e)^n$:

Lemma 1 (Modular Inverse via Fermat). For prime $p$ and $a \not\equiv 0 \pmod{p}$: $a^{-1} \equiv a^{p-2} \pmod{p}$.

Proof. By Fermat’s little theorem, $a^{p-1} \equiv 1 \pmod{p}$, so $a \cdot a^{p-2} \equiv 1$. $\square$

Editorial

Alternative (precompute factorials). We method 1: Using ratio recurrence with modular inverses. We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

Method 1: Using ratio recurrence with modular inverses
C_{n+1} = C_n * 2*(2n+1) * inverse(n+2) mod MOD
Precompute factorials and inverse factorials mod MOD
C_k = fact[2k] * inv_fact[k+1] * inv_fact[k] mod MOD

Complexity Analysis

• Time (ratio recurrence): $O(N \log p)$, where each step requires one modular inverse via binary exponentiation in $O(\log p)$.
• Time (factorial precomputation): $O(N + \log p)$. Precomputing factorials is $O(N)$; a single modular inverse costs $O(\log p)$; the remaining inverse factorials are $O(N)$ via backward recurrence.
• Space: $O(1)$ for the ratio method; $O(N)$ for the factorial method.

Answer

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

/*
 * Problem 928: Catalan Number Variants
 *
 * Find sum_{k=0}^{1000} C_k mod 10^9+7.
 * C_n = (2n)! / ((n+1)! * n!).
 *
 * Recurrence: C_{k+1} = C_k * 2(2k+1) / (k+2).
 * Or use factorial precomputation with modular inverses.
 *
 * Generating function: C(x) = (1 - sqrt(1-4x)) / (2x).
 * Asymptotics: C_n ~ 4^n / (n^{3/2} sqrt(pi)).
 *
 * Complexity: O(N) with factorial precomputation.
 */

long long MOD = 1000000007;

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int N = 1000;
    vector<long long> fact(2*N + 2), inv_fact(2*N + 2);
    fact[0] = 1;
    for (int i = 1; i <= 2*N + 1; i++)
        fact[i] = fact[i-1] * i % MOD;
    inv_fact[2*N+1] = power(fact[2*N+1], MOD-2, MOD);
    for (int i = 2*N; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;

    long long total = 0;
    for (int k = 0; k <= N; k++) {
        // C_k = (2k)! / (k! * (k+1)!)
        long long c = fact[2*k] % MOD * inv_fact[k] % MOD * inv_fact[k+1] % MOD;
        total = (total + c) % MOD;
    }
    cout << total << endl;

    // Verify first Catalan numbers: 1, 1, 2, 5, 14, 42
    auto catalan = [&](int k) {
        return fact[2*k] % MOD * inv_fact[k] % MOD * inv_fact[k+1] % MOD;
    };
    assert(catalan(0) == 1);
    assert(catalan(1) == 1);
    assert(catalan(2) == 2);
    assert(catalan(3) == 5);
    assert(catalan(4) == 14);

    return 0;
}

"""
Problem 928: Catalan Number Variants

Compute the sum of Catalan numbers C_0 + C_1 + ... + C_N modulo 10^9+7.
Uses modular arithmetic with precomputed factorials and inverse factorials.

Key ideas:
    - Catalan number: C_n = C(2n, n) / (n+1) = (2n)! / (n! * (n+1)!).
    - Recurrence: C_{n+1} = C_n * 2(2n+1) / (n+2).
    - Asymptotic: C_n ~ 4^n / (n^{3/2} * sqrt(pi)).
    - Generating function: C(x) = (1 - sqrt(1-4x)) / (2x).

Methods:
    1. Modular arithmetic with factorial precomputation
    2. Recurrence relation (exact integers for small n)
    3. Asymptotic approximation comparison
    4. Ratio analysis C_{n+1}/C_n approaching 4
"""

import numpy as np

def solve(N=1000):
    """Compute sum of C_0..C_N mod 10^9+7."""
    MOD = 10**9 + 7
    fact = [1] * (2 * N + 2)
    for i in range(1, 2 * N + 2):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (2 * N + 2)
    inv_fact[2 * N + 1] = pow(fact[2 * N + 1], MOD - 2, MOD)
    for i in range(2 * N, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

    def catalan_mod(k):
        return fact[2 * k] * inv_fact[k] % MOD * inv_fact[k + 1] % MOD

    total = 0
    for k in range(N + 1):
        total = (total + catalan_mod(k)) % MOD
    return total

def catalan_exact(N):
    """Compute exact Catalan numbers C_0..C_N using the recurrence."""
    cats = [1]
    for k in range(1, N + 1):
        cats.append(cats[-1] * 2 * (2 * k - 1) // (k + 1))
    return cats

def catalan_asymptotic(n):
    """Asymptotic estimate: C_n ~ 4^n / (n^{3/2} * sqrt(pi))."""
    if n == 0:
        return 1.0
    return 4**n / (n**1.5 * np.sqrt(np.pi))

def catalan_ratios(cats):
    """Compute C_{n+1}/C_n for each n. Approaches 4."""
    return [cats[i + 1] / cats[i] for i in range(len(cats) - 1)]

# Solve and verify
answer = solve()

# Verify exact Catalan numbers against known values
cats = catalan_exact(20)
known = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
for i, val in enumerate(known):
    assert cats[i] == val, f"Catalan({i}) mismatch: {cats[i]} != {val}"

# Verify formula: C_n = C(2n,n)/(n+1)
from math import comb
for n in range(15):
    assert cats[n] == comb(2 * n, n) // (n + 1), f"Binomial formula mismatch at {n}"

# Verify sum of first few
assert sum(cats[:5]) == 1 + 1 + 2 + 5 + 14  # = 23

print(answer)