Skip to content

🔢 Специални Числови Редици: Теория и Приложения

📚 Въведение

В комбинаториката и теорията на числата съществуват редици, които се появяват в стотици различни контексти. Познаването им позволява да разпознаете структурата на задачата още при прочитането ѝ. Тези редици не са просто математически любопитства - те са ключови инструменти за решаване на сложни олимпиадни задачи.

Когато видите, че първите няколко отговора на задача са \(1, 2, 5, 14, 42\), почти сигурно става въпрос за числата на Каталан. Разпознаването на такива модели може да ви спести часове размисъл и да ви насочи директно към правилния подход.

1. Числа на Каталан (Catalan Numbers)

Поредицата започва така: \(1, 1, 2, 5, 14, 42, 132, 429, 1430, \dots\) за \(n = 0, 1, 2, \dots\).

1.1. Формули

Най-популярната формула е: $\(C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)$

Рекурентната зависимост, която често се ползва в ДП: $\(C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}\)$

1.2. Класически приложения

Числата на Каталан са отговор на следните въпроси: 1. Правилни скобови изрази: Колко са начините да подредим \(n\) двойки отварящи и затварящи скоби? 2. Двоични дървета: Колко са различните двоични дървета с \(n\) възела? 3. Триангулация: По колко начина можем да разделим изпъкнал \((n+2)\)-ъгълник на триъгълници? 4. Пътища в мрежа (Dyck Paths): Колко са пътищата от \((0,0)\) до \((n,n)\) в квадратна мрежа, които не пресичат диагонала \(y=x\)?

1.3. Имплементация и изчисления

Директно пресмятане с формулата:

// Пресмятане на C_n директно
long long catalan(int n) {
    long long res = 1;
    for (int i = 0; i < n; i++) {
        res *= (2 * n - i);
        res /= (i + 1);
    }
    return res / (n + 1);
}

Динамично пресмятане с рекурсия:

const int MAXN = 100;
long long C[MAXN];

void computeCatalan(int n) {
    C[0] = C[1] = 1;
    for (int i = 2; i <= n; i++) {
        C[i] = 0;
        for (int j = 0; j < i; j++) {
            C[i] += C[j] * C[i - 1 - j];
        }
    }
}

Модулна аритметика (за големи числа):

const int MOD = 1e9 + 7;

long long modpow(long long base, long long exp, long long mod) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);  // Работи за прости модули
}

long long catalanMod(int n) {
    vector<long long> fact(2 * n + 1);
    fact[0] = 1;
    for (int i = 1; i <= 2 * n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    long long num = fact[2 * n];
    long long den = (fact[n + 1] * fact[n]) % MOD;
    return (num * modinv(den, MOD)) % MOD;
}

1.4. Практически пример: Валидни скоби

// Генериране на всички валидни скобови последователности
void generateParens(int n, int open, int close, string curr, vector<string>& result) {
    if (curr.length() == 2 * n) {
        result.push_back(curr);
        return;
    }

    if (open < n) {
        generateParens(n, open + 1, close, curr + "(", result);
    }
    if (close < open) {
        generateParens(n, open, close + 1, curr + ")", result);
    }
}

2. Числа на Фибоначи (Fibonacci)

Дефинирани чрез: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}\).

2.1. Бързо пресмятане (\(O(\log N)\))

За много големи \(N\) (\(10^{18}\)) използваме матрично повдигане на степен: $$ \begin{pmatrix} F_{n+1} \ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \ 0 \end{pmatrix} $$

2.2. Свойства

  1. Сума: \(\sum_{i=1}^n F_i = F_{n+2} - 1\).
  2. Период на Пизано: Остатъците на Фибоначи по модул \(M\) образуват цикъл.
  3. Златно сечение: Границата на \(F_{n+1}/F_n\) е \(\phi \approx 1.618\).
  4. Формула на Бине: \(F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}\) където \(\phi = \frac{1+\sqrt{5}}{2}\) и \(\psi = \frac{1-\sqrt{5}}{2}\).
  5. GCD свойство: \(\gcd(F_m, F_n) = F_{\gcd(m,n)}\).

2.3. Имплементация на матрично степенуване

struct Matrix {
    long long a[2][2];

    Matrix() {
        memset(a, 0, sizeof(a));
    }

    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    res.a[i][j] += a[i][k] * other.a[k][j];
                    res.a[i][j] %= MOD;
                }
            }
        }
        return res;
    }
};

Matrix matpow(Matrix base, long long exp) {
    Matrix res;
    res.a[0][0] = res.a[1][1] = 1;  // Identity matrix

    while (exp > 0) {
        if (exp % 2) res = res * base;
        base = base * base;
        exp /= 2;
    }
    return res;
}

long long fibonacci(long long n) {
    if (n <= 1) return n;

    Matrix base;
    base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;
    base.a[1][1] = 0;

    Matrix res = matpow(base, n);
    return res.a[0][1];
}

2.4. Приложения на Фибоначи в задачи

Пример 1: Брой начини да се изкачат N стъпала (можете да стъпвате на 1 или 2 стъпала наведнъж)

Отговорът е \(F_{n+1}\) (n-тото число на Фибоначи).

Пример 2: Покриване на 2×N дъска с 1×2 плочки

Отговорът е \(F_{n+1}\).

// ДП решение за покриване на дъска
int dp[MAXN];

int tileDp(int n) {
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    }
    return dp[n];
}

Пример 3: Кодиране на Зекендорф

Всяко положително цяло число може да се представи уникално като сума от ненакъплени числа на Фибоначи (т.е. не използваме две последователни числа на Фибоначи).

vector<int> zeckendorf(int n) {
    vector<int> fibs;
    fibs.push_back(1);
    fibs.push_back(2);

    while (fibs.back() < n) {
        int sz = fibs.size();
        fibs.push_back(fibs[sz-1] + fibs[sz-2]);
    }

    vector<int> result;
    for (int i = fibs.size() - 1; i >= 0; i--) {
        if (n >= fibs[i]) {
            result.push_back(fibs[i]);
            n -= fibs[i];
        }
    }
    return result;
}

3. Числа на Стирлинг (Stirling Numbers)

3.1. Втори род \(S(n, k)\)

Броят начини да се разбие множество от \(n\) елемента на \(k\) непразни подмножества. * Рекурсия: \(S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)\). * Обяснение: Новият елемент или влиза в едно от съществуващите \(k\) подмножества, или създава ново сам.

3.2. Първи род \(c(n, k)\)

Броят на пермутациите на \(n\) елемента, които се състоят от точно \(k\) цикъла. * Рекурсия: \(c(n, k) = (n-1)c(n-1, k) + c(n-1, k-1)\).

3.3. Имплементация

// Числа на Стирлинг от втори род
long long stirling2[MAXN][MAXN];

void computeStirling2(int n) {
    stirling2[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            stirling2[i][j] = j * stirling2[i-1][j] + stirling2[i-1][j-1];
            stirling2[i][j] %= MOD;
        }
    }
}

// Числа на Стирлинг от първи род
long long stirling1[MAXN][MAXN];

void computeStirling1(int n) {
    stirling1[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            stirling1[i][j] = (i-1) * stirling1[i-1][j] + stirling1[i-1][j-1];
            stirling1[i][j] %= MOD;
        }
    }
}

3.4. Приложения

Пример: Разбиване на множество от хора на групи

Имаме \(n\) души и искаме да ги разделим на \(k\) непразни групи (без значение от реда). Отговорът е \(S(n, k)\).

4. Числа на Бел (Bell Numbers) \(B_n\)

Общият брой на всички възможни разбивания на множество от \(n\) елемента (на неопределен брой подмножества). $\(B_n = \sum_{k=0}^n S(n, k)\)$ Рекурсия: \(B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k\).

4.1. Имплементация

long long bell[MAXN];

void computeBell(int n) {
    // Използваме вече изчислените Стирлинг числа
    for (int i = 0; i <= n; i++) {
        bell[i] = 0;
        for (int j = 0; j <= i; j++) {
            bell[i] += stirling2[i][j];
            bell[i] %= MOD;
        }
    }
}

// Алтернативен метод с триъгълник на Бел
void computeBellTriangle(int n) {
    long long B[MAXN][MAXN];
    B[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        B[i][0] = B[i-1][i-1];
        for (int j = 1; j <= i; j++) {
            B[i][j] = (B[i-1][j-1] + B[i][j-1]) % MOD;
        }
    }

    for (int i = 0; i <= n; i++) {
        bell[i] = B[i][0];
    }
}

4.2. Приложение

Колко различни начина има да групираме \(n\) студента (без значение от големината на групите)?

5. Партиции на числа (Integer Partitions)

Броят начини да представим число \(n\) като сума от положителни цели числа (редът няма значение).

5.1. Формули и рекурсии

Нека \(p(n)\) е броят на партициите на \(n\), а \(p(n, k)\) е броят на партициите на \(n\) използващи числа най-много \(k\).

Рекурсия: $\(p(n, k) = p(n, k-1) + p(n-k, k)\)$

Обяснение: Или не използваме \(k\) в партицията, или го използваме поне веднъж.

5.2. Имплементация

int partition[MAXN][MAXN];

void computePartitions(int n) {
    // p(n, k) = number of partitions of n using numbers <= k
    for (int i = 0; i <= n; i++) {
        partition[0][i] = 1;  // Празна партиция
    }

    for (int num = 1; num <= n; num++) {
        for (int k = 1; k <= n; k++) {
            partition[num][k] = partition[num][k-1];
            if (num >= k) {
                partition[num][k] += partition[num - k][k];
                partition[num][k] %= MOD;
            }
        }
    }
}

// Брой на всички партиции на n
int totalPartitions(int n) {
    return partition[n][n];
}

5.3. Генериращи функции

Производящата функция за партициите е: $\(\prod_{k=1}^{\infty} \frac{1}{1-x^k}\)$

Това води до формулата на Ойлер за пентагонални числа: $\(p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + \dots\)$

5. Числа на Бернули (Bernoulli Numbers)

Използват се главно за сумиране на степени: \(1^k + 2^k + \dots + n^k\). Формулата на Фаулхабер (Faulhaber) дава полином за тази сума, чиито коефициенти зависят от числата на Бернули.

5.1. Дефиниция и основни свойства

Числата на Бернули \(B_n\) се дефинират чрез производящата функция: $\(\frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}\)$

Първите няколко числа на Бернули: - \(B_0 = 1\) - \(B_1 = -\frac{1}{2}\) - \(B_2 = \frac{1}{6}\) - \(B_4 = -\frac{1}{30}\) - \(B_6 = \frac{1}{42}\)

Забележка: \(B_n = 0\) за всички нечетни \(n > 1\).

5.2. Формула на Фаулхабер

Сумата на \(k\)-ти степени може да се изрази като: $\(\sum_{i=1}^{n} i^k = \frac{1}{k+1} \sum_{j=0}^{k} \binom{k+1}{j} B_j n^{k+1-j}\)$

Например: - \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\) - \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\) - \(\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2\)

6. Числа на Дерангман (Derangements)

Дерангман е пермутация, при която нито един елемент не е на своята оригинална позиция. Броят дерангмани на \(n\) елемента се означава с \(!n\) или \(D_n\).

6.1. Формули

Рекурсивна формула: $\(D_n = (n-1)(D_{n-1} + D_{n-2})\)$

Формула с включване-изключване: $\(D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}\)$

Това е приблизително \(\frac{n!}{e}\) за големи \(n\).

6.2. Имплементация

long long derangement[MAXN];

void computeDerangements(int n) {
    derangement[0] = 1;
    derangement[1] = 0;

    for (int i = 2; i <= n; i++) {
        derangement[i] = (i - 1) * (derangement[i-1] + derangement[i-2]);
        derangement[i] %= MOD;
    }
}

6.3. Приложение

Проблемът със секретарките: \(n\) секретарки написват писма и плика за тях. По колко начина могат да поставят писмата в пликовете така, че нито едно писмо да не е в правилния плик?

Отговорът е \(D_n\).

6. Задачи за упражнение

  1. SPOJ SKYLINE: Сгради (Catalan).
  2. CSES Fibonacci Numbers: Матрично степенуване.
  3. Codeforces 990C: Bracket Sequences (Вариация).
  4. UVa 10601: Cubes (Комбиниране на идеи).
  5. Project Euler 15: Lattice Paths (Catalan приложение).
  6. Codeforces 414B: Mashmokh and ACM (Partitions).
  7. SPOJPARTSUM: Partition Sums (Динамично програмиране с партиции).

7. Как да разпознаете редицата

7.1. OEIS (Online Encyclopedia of Integer Sequences)

Това е най-мощният инструмент за разпознаване на числови редици. Когато решавате задача:

  1. Изчислете първите 5-10 стойности за малки входове
  2. Въведете редицата в oeis.org
  3. Проверете дали вашата редица съвпада с известна

Пример: Въвеждате 1, 2, 5, 14, 42 и намирате A000108 (числата на Каталан).

7.2. Индикатори за различните редици

Каталан (\(C_n\)): - Балансирани скоби, пътища, дървета - Бърз растеж: \(C_n \approx \frac{4^n}{n^{3/2}\sqrt{\pi}}\) - Всеки член е около 4 пъти предишния

Фибоначи (\(F_n\)): - Сумиране на предишните два члена - Растеж: \(F_n \approx \frac{\phi^n}{\sqrt{5}}\) - Всеки член е около 1.618 пъти предишния

Стирлинг (\(S(n,k)\)): - Разбиване на множества или цикли в пермутации - Триъгълна структура (подобно на треъгълника на Паскал)

Бел (\(B_n\)): - Общи партиции на множества - Много бърз растеж (по-бърз от факториал)

Партиции на числа (\(p(n)\)): - Начини да представим число като сума - По-бавен растеж от експоненциален

7.3. Съвети за олимпиадни задачи

  1. Винаги тествайте с малки входове и записвайте резултатите
  2. Търсете модел в последователността
  3. Проверявайте в OEIS преди да губите време с измисляне
  4. Обърнете внимание на ограниченията - ако \(n \leq 20\), вероятно е комбинаторика или ДП с маски
  5. Гледайте растежа - ако числата растат много бързо, може да е факториал или Каталан

🏁 Заключение

Ако забележите, че първите няколко отговора на задача са \(1, 2, 5, 14, 42\), почти сигурно е, че отговорът е число на Каталан. Винаги проверявайте вашите малки случаи в OEIS (Online Encyclopedia of Integer Sequences).

Специалните числови редици не са просто теоретични концепции - те са практични инструменти, които могат да спестят часове размисъл в състезание. Инвестирайте време да ги научите, защото те се появяват отново и отново в различни форми.

Ключови точки: - Запомнете първите няколко члена на основните редици - Научете се да ги изчислявате ефективно (особено по модул) - Винаги проверявайте в OEIS при неразпознати последователности - Разберете дълбоко приложенията - не само формулите - Практикувайте с реални задачи от състезания