🎲 Напреднала Комбинаторика: Принципи и Техники за Броене

Комбинаториката в състезателното програмиране често надхвърля простото пресмятане на пермутации и комбинации. Тя изисква разбиране на фундаментални принципи, които позволяват решаването на сложни задачи с ограничения и симетрии.

1. Принцип на Включване и Изключване (PIE)

Принципът се използва за намиране на големината на обединението на краен брой крайни множества.

1.1. Формули за 2 и 3 множества

$|A \cup B| = |A| + |B| - |A \cap B|$
$|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$

1.2. Обща Формула

За $n$ множества $A_1, A_2, \dots, A_n$: $$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$$

1.3. Приложение: Проблемът за деранжиментите ($D_n$)

Деранжимент е пермутация, при която нито един елемент не е на "правилното" си място (напр. писмо $i$ не е в плик $i$). Използвайки PIE, където "лошото" свойство $P_i$ е "елемент $i$ е на позиция $i$": $$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$ Рекурсия: $D_n = (n-1)(D_{n-1} + D_{n-2})$.

1.4. Имплементация на деранжименти:

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1e9 + 7;

// Изчисляване на факториел
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % MOD;
    }
    return result;
}

// Модулно обратно
long long modinv(long long a, long long m) {
    long long result = 1, base = a, exp = m - 2;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % m;
        base = (base * base) % m;
        exp /= 2;
    }
    return result;
}

// Деранжименти чрез PIE
long long derangements_PIE(int n) {
    long long fact = factorial(n);
    long long sum = 0;
    long long fact_k = 1;

    for (int k = 0; k <= n; k++) {
        long long term = (fact * modinv(fact_k, MOD)) % MOD;
        if (k % 2 == 0) {
            sum = (sum + term) % MOD;
        } else {
            sum = (sum - term + MOD) % MOD;
        }
        fact_k = (fact_k * (k + 1)) % MOD;
    }

    return sum;
}

// Деранжименти чрез рекурсия (по-бързо)
long long derangements_DP(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;

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

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

    return dp[n];
}

int main() {
    int n = 5;
    cout << "Деранжименти на " << n << " елемента: " 
         << derangements_DP(n) << endl;
    return 0;
}

1.5. Задача: Брой пермутации с точно k фиксирани точки

long long permWithKFixed(int n, int k) {
    // C(n, k) * D(n-k)
    // Избираме k елемента да са на място, останалите n-k са деранжимент
    long long comb = binomial(n, k); // Трябва да имплементирате binomial
    long long der = derangements_DP(n - k);
    return (comb * der) % MOD;
}

2. Звезди и Черти (Stars and Bars)

Тази техника е безценна за задачи от типа "разпределяне на идентични предмети в различни кутии".

2.1. Вариант 1: Кутиите могат да бъдат празни

Броят начини да разпределим $n$ еднакви топчета в $k$ различни кутии е: $$\binom{n + k - 1}{k - 1}$$ Логика: Имаме $n$ звезди и $k-1$ черти (разделители). Общо $n+k-1$ обекта. Избираме кои $k-1$ от тях да са черти.

2.2. Вариант 2: Всяка кутия трябва да има поне 1 предмет

Броят начини е: $$\binom{n - 1}{k - 1}$$ Логика: Поставяме чертите в празните пространства между звездите. Има $n-1$ такива пространства.

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

// Биномни коефициенти с ДП
const int MAXN = 1005;
const long long MOD = 1e9 + 7;
long long C[MAXN][MAXN];

void precompute_binomial() {
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

// Вариант 1: Кутиите могат да бъдат празни
long long starsAndBars1(int n, int k) {
    return C[n + k - 1][k - 1];
}

// Вариант 2: Всяка кутия трябва да има поне 1
long long starsAndBars2(int n, int k) {
    if (n < k) return 0; // Невъзможно
    return C[n - 1][k - 1];
}

// Вариант 3: Всяка кутия има min и max
long long starsAndBarsWithLimits(int n, int k, vector<int>& minVals, vector<int>& maxVals) {
    // Първо отделяме минималните стойности
    int remaining = n;
    for (int i = 0; i < k; i++) {
        remaining -= minVals[i];
    }

    if (remaining < 0) return 0;

    // Използваме PIE за максималните ограничения
    // Това е по-сложно и изисква генериране на всички подмножества
    // ... (оставено като упражнение)
    return 0; // placeholder
}

2.4. Примерна задача:

Задача: По колко начина можем да разделим $n$ еднакви бонбона между $k$ деца, ако всяко дете трябва да получи поне 2 бонбона?

Решение: 1. Даваме на всяко дете по 2 бонбона: остават $n - 2k$ бонбона 2. Разпределяме оставащите бонбони произволно: $\binom{(n-2k) + k - 1}{k-1} = \binom{n - k - 1}{k - 1}$

long long distributeCandies(int n, int k) {
    if (n < 2 * k) return 0; // Невъзможно
    return C[n - k - 1][k - 1];
}

3. Лема на Бърнсайд (Burnside's Lemma)

Използва се за броене на различни конфигурации при наличие на група от симетрии (ротации, отражения).

Формула: $$N = \frac{1}{|G|} \sum_{g \in G} |X^g|$$ Където: * $|G|$ е броят на симетриите (напр. ротация на 0, 90, 180, 270 градуса). * $|X^g|$ е броят на оцветяванията, които не се променят след прилагане на симетрията $g$.

Пример: Огърлица с $n$ мъниста и $m$ цвята (само ротации)

$|G| = n$ (всички възможни завъртания). За всяка ротация с $k$ стъпки, броят на фиксираните оцветявания е $m^{\gcd(k, n)}$. Общо: $N = \frac{1}{n} \sum_{k=0}^{n-1} m^{\gcd(k, n)}$.

Имплементация:

#include <iostream>
#include <cmath>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long m) {
    return power(a, m - 2, m);
}

// Броене на огърлици с n мъниста и m цвята (само ротации)
long long necklaceRotations(int n, int m, long long MOD) {
    long long sum = 0;
    for (int k = 0; k < n; k++) {
        long long g = gcd(k, n);
        sum = (sum + power(m, g, MOD)) % MOD;
    }
    return (sum * modinv(n, MOD)) % MOD;
}

// Огърлица с ротации И отражения (Polya enumeration)
long long necklaceWithReflections(int n, int m, long long MOD) {
    long long rotations = 0;
    for (int k = 0; k < n; k++) {
        rotations = (rotations + power(m, gcd(k, n), MOD)) % MOD;
    }

    long long reflections = 0;
    if (n % 2 == 1) {
        // n на брой оси през един връх
        reflections = (n * power(m, (n + 1) / 2, MOD)) % MOD;
    } else {
        // n/2 оси през два върха + n/2 оси между върхове
        long long axis1 = (n / 2) * power(m, n / 2 + 1, MOD) % MOD;
        long long axis2 = (n / 2) * power(m, n / 2, MOD) % MOD;
        reflections = (axis1 + axis2) % MOD;
    }

    long long total = (rotations + reflections) % MOD;
    long long groupSize = 2 * n; // n ротации + n отражения

    return (total * modinv(groupSize, MOD)) % MOD;
}

int main() {
    int n = 6; // 6 мъниста
    int m = 3; // 3 цвята
    long long MOD = 1e9 + 7;

    cout << "Огърлици (само ротации): " 
         << necklaceRotations(n, m, MOD) << endl;
    cout << "Огърлици (ротации + отражения): " 
         << necklaceWithReflections(n, m, MOD) << endl;

    return 0;
}

Друг пример: Оцветяване на куб

Куб има 24 симетрии (елементи на групата на ротациите): - 1 идентитет: всички $m^6$ оцветявания са фиксирани - 6 ротации на 90° около оси през центрове на лица: $m^3$ фиксирани - 3 ротации на 180° около същите оси: $m^4$ фиксирани - 8 ротации на 120° около диагонали: $m^2$ фиксирани - 6 ротации на 180° около оси през средите на ребра: $m^3$ фиксирани

\[N = \frac{1}{24}(m^6 + 6m^3 + 3m^4 + 8m^2 + 6m^3) = \frac{1}{24}(m^6 + 3m^4 + 12m^3 + 8m^2)\]

4. Теорема на Лукас (Lucas Theorem)

Позволява бързо пресмятане на $\binom{n}{k} \pmod p$, където $p$ е малко просто число, а $n$ и $k$ са огромни (до $10^{18}$). Ако запишем $n$ и $k$ в $p$-ична бройна система: $n = n_k p^k + \dots + n_0$ $k = k_k p^k + \dots + k_0$ То: $$\binom{n}{k} \equiv \prod_{i=0}^k \binom{n_i}{k_i} \pmod p$$

Имплементация:

const long long MOD = 1000000007; // Трябва да е просто число

// Предварително изчисляваме факториели и обратни за малки стойности
long long fact[MOD], inv_fact[MOD];

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MOD; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }

    inv_fact[MOD - 1] = power(fact[MOD - 1], MOD - 2, MOD);
    for (int i = MOD - 2; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

// Бином за малки n, k
long long binomial_small(long long n, long long k) {
    if (k > n || k < 0) return 0;
    return (fact[n] * inv_fact[k] % MOD) * inv_fact[n - k] % MOD;
}

// Теорема на Лукас
long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;
    return (binomial_small(n % p, k % p) * lucas(n / p, k / p, p)) % p;
}

int main() {
    precompute_factorials();

    long long n = 1000000000000LL;
    long long k = 500000000000LL;

    cout << "C(" << n << ", " << k << ") mod " << MOD 
         << " = " << lucas(n, k, MOD) << endl;

    return 0;
}

Приложение: Проверка дали бином е четно/нечетно

За $p = 2$, теоремата на Лукас дава бърз начин да проверим дали $\binom{n}{k}$ е четно: $\binom{n}{k}$ е нечетно тогава и само тогава, когато $(k \& n) = k$ (всички битове на $k$ присъстват в $n$).

5. Формула на Кейли (Cayley's Formula)

Броят на различните номерирани дървета с $n$ върха е $n^{n-2}$. Свързана е с Редиците на Прюфер (Prufer Sequences) – всеки низ от $n-2$ числа в диапазона $[1, n]$ кодира уникално дърво.

5.1. Доказателство чрез Prufer кодиране:

// Превръщане на дърво в Prufer последователност
vector<int> treeToPrufer(int n, vector<pair<int,int>>& edges) {
    vector<int> degree(n + 1, 0);
    vector<set<int>> adj(n + 1);

    for (auto [u, v] : edges) {
        adj[u].insert(v);
        adj[v].insert(u);
        degree[u]++;
        degree[v]++;
    }

    vector<int> prufer;
    for (int i = 0; i < n - 2; i++) {
        // Намираме листа с най-малък номер
        for (int leaf = 1; leaf <= n; leaf++) {
            if (degree[leaf] == 1) {
                int neighbor = *adj[leaf].begin();
                prufer.push_back(neighbor);

                // Премахваме ребро
                degree[leaf]--;
                degree[neighbor]--;
                adj[leaf].erase(neighbor);
                adj[neighbor].erase(leaf);
                break;
            }
        }
    }

    return prufer;
}

// Превръщане на Prufer последователност в дърво
vector<pair<int,int>> pruferToTree(vector<int>& prufer) {
    int n = prufer.size() + 2;
    vector<int> degree(n + 1, 1);

    for (int node : prufer) {
        degree[node]++;
    }

    vector<pair<int,int>> edges;
    for (int i : prufer) {
        // Намираме най-малкото листо
        for (int leaf = 1; leaf <= n; leaf++) {
            if (degree[leaf] == 1) {
                edges.push_back({i, leaf});
                degree[i]--;
                degree[leaf]--;
                break;
            }
        }
    }

    // Свързваме последните две листа
    for (int u = 1; u <= n; u++) {
        if (degree[u] == 1) {
            for (int v = u + 1; v <= n; v++) {
                if (degree[v] == 1) {
                    edges.push_back({u, v});
                    break;
                }
            }
            break;
        }
    }

    return edges;
}

5.2. Обобщение на формулата на Кейли:

Броят на гори с $n$ върха и $k$ компоненти (дървета) е: $k \cdot n^{n-k-1}$

5.3. Приложение: Брой начини да свържем градове

Задача: Имаме $n$ града. Колко начина има да ги свържем с $n-1$ пътя, така че всеки град да е достъпен от всеки друг?

Отговор: $n^{n-2}$ (формула на Кейли)

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

CSES Distributing Apples: Stars and Bars.
Codeforces 451E: PIE с големи ограничения (изисква Lucas или хитро броене).
CSES Christmas Party: Деранжименти.
UVa 10294: Necklace (Burnside).
SPOJ ADACABAA: Binomial coefficients modulo composite (Lucas).
Codeforces 711D: Colored Tree (Burnside + Prufer).

7. Каталанови числа

Каталановите числа $C_n$ имат множество приложения:

\[C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\]

Рекурсия:

\[C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}\]

Приложения:

Брой валидни скобови последователности с $n$ двойки скоби
Брой двоични дървета с $n$ вътрешни възела
Брой начини да триангулираме многоъгълник с $n+2$ върха
Брой пътища в решетка от $(0,0)$ до $(n,n)$, които не пресичат диагонала

vector<long long> catalan(int n, long long MOD) {
    vector<long long> C(n + 1);
    C[0] = 1;

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

    return C;
}

// По-ефективна версия с биномни коефициенти
long long catalan_fast(int n, long long MOD) {
    long long binom = binomial(2 * n, n); // C(2n, n)
    return (binom * modinv(n + 1, MOD)) % MOD;
}

8. Числа на Стирлинг

Числа на Стирлинг от първи род $S_1(n, k)$:

Броят начини да разделим $n$ елемента в $k$ цикъла.

Числа на Стирлинг от втори род $S_2(n, k)$:

Броят начини да разделим $n$ елемента в $k$ непразни подмножества.

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

long long stirling2[MAXN][MAXN];

void compute_stirling2(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]) % MOD;
        }
    }
}

Приложение на Стирлинг:

Броят на сюрективните функции от множество с $n$ елемента към множество с $k$ елемента е: $k! \cdot S_2(n, k)$

🏁 Заключение

Напредналата комбинаторика често се свежда до това да разпознаете кой принцип да приложите. PIE е за задачи с "поне едно" или "нито едно", Stars and Bars е за разпределяне на ресурси, а Burnside е за симетрия. Практикувайте с различни задачи, за да развиете интуиция.

🎲 Напреднала Комбинаторика: Принципи и Техники за Броене

1. Принцип на Включване и Изключване (PIE)

1.1. Формули за 2 и 3 множества

1.2. Обща Формула

1.3. Приложение: Проблемът за деранжиментите (\(D_n\))

1.4. Имплементация на деранжименти:

1.5. Задача: Брой пермутации с точно k фиксирани точки

2. Звезди и Черти (Stars and Bars)

2.1. Вариант 1: Кутиите могат да бъдат празни

2.2. Вариант 2: Всяка кутия трябва да има поне 1 предмет

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

2.4. Примерна задача:

3. Лема на Бърнсайд (Burnside's Lemma)

Пример: Огърлица с \(n\) мъниста и \(m\) цвята (само ротации)

Имплементация:

Друг пример: Оцветяване на куб

4. Теорема на Лукас (Lucas Theorem)

Имплементация:

Приложение: Проверка дали бином е четно/нечетно

5. Формула на Кейли (Cayley's Formula)

5.1. Доказателство чрез Prufer кодиране:

5.2. Обобщение на формулата на Кейли:

5.3. Приложение: Брой начини да свържем градове

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

7. Каталанови числа

Рекурсия:

Приложения:

8. Числа на Стирлинг

Числа на Стирлинг от първи род \(S_1(n, k)\):

Числа на Стирлинг от втори род \(S_2(n, k)\):

Приложение на Стирлинг:

🏁 Заключение