Numărul de partiții ale unui număr natural

de Iulian Oleniuc | 03/01/2020 | Algoritmică și structuri de date, Matematică

La mulți ani 2020! Acum câteva zile (în deceniul trecut) am dat o simulare pe InfoArena la care a picat problema Crescător2. Problema cerea numărul de șiruri crescătoare cu suma elementelor mai mică sau egală cu $S$ Asta înseamnă practic numărul de partiții neordonate ale numerelor naturale nenule mai mici sau egale cu $S$ În timpul simulării am luat 40 de puncte cu o dinamică în $O(n^2)$ însă upsolving-ul mi-a luat câteva ore bune, pentru că soluția oficială folosea un truc legat de $\sqrt{n}$ iar mie nu-mi plac trucurile legate de radical :yey: Așa că am făcut research pe net pentru a găsi (și mai ales a înțelege) o recurență liniară, research în care am învățat câte ceva despre matematici discrete, funcții generatoare și numere pentagonale. În acest articol voi împărtăși cu voi ce am învățat :smile:

Ce sunt partițiile unui număr natural?

Numim partiție a lui $n \in \mathbb{N}$ o secvență de numere naturale nenule $P = \langle p_1, p_2, \ldots, p_k \rangle$ cu proprietatea că $p_1 + p_2 + \cdots + p_k = n$ Dacă secvența $P$ este ordonată, partiția este ordonată, iar în caz contrar, neordonată.

De exemplu, partițiile ordonate ale lui $4$ sunt:

(1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3), (2, 1, 1), (2, 2), (3, 1), (4)

Însă, partițiile neordonate ale lui $4$ sunt:

[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]

Așadar, partițiile ordonate $(1, 1, 2)$ și $(1, 2, 1)$ sunt diferite, pe când partițiile neordonate $[1, 1, 2]$ și $[1, 2, 1]$ sunt egale.

Prin convenție, numărul de partiții ale lui $0$ este $1$ Convenția este justificată, deoarece putem considera că mulțimea vidă este o partiție a lui $0$ suma elementelor ei fiind $0$

Numărul de partiții ordonate

Problema asta e partea simplă a articolului, pentru că s-a dovedit a fi mult mai ușor să numeri partițiile ordonate decât pe cele neordonate. Să vedem mai întâi cum putem număra partițiile în funcție de lungimea lor. Fie $p(n, k)$ numărul de partiții ordonate ale lui $n$ de lungime $k$ Pentru a ne ușura munca, vom reduce problema la una mai ușor de abordat:

Să se determine numărul modurilor de a împărți un șir de lungime $n$ în $k$ secvențe de lungimi nenule. De exemplu, șirul xxxxx poate fi împărțit în $3$ secvențe astfel:
x x xxx
x xx xx
x xxx x
xx x xx
xx xx x
xxx x x

Este clar că o astfel de împărțire a unui șir este de fapt o partiție a lui $n$ în care lungimea fiecărei secvențe reprezintă valoarea unui element din partiție.

Practic, trebuie să găsim numărul de moduri de a alege cele $k - 1$ puncte de split, adică acele poziții pe care se termină fiecare secvență, mai puțin ultima (pentru că ea are poziția de sfârșit fixată). Aceste poziții iau valori din mulțimea $\{1, 2, \ldots, n - 1\}$ Cum ele trebuie să fie distincte, se observă ușor că soluția e dată de $C_{n - 1}^{k - 1}$

Acum, dacă vrem să calculăm numărul total de partiții ordonate ale lui $n$ nu avem decât să însumăm niște combinări. Mai exact, dacă notăm cu $p(n)$ numărul tuturor partițiilor ordonate ale lui $n$ obținem:

p(n) = C_{n - 1}^0 + C_{n - 1}^1 + \cdots + C_{n - 1}^{n - 1} = 2^{n - 1}

Numărul de partiții neordonate de lungime dată

Păstrăm notațiile precedente, doar că de data asta se vor referi la partiții neordonate. Din nou, vom număra mai întâi partițiile după lungimea lor. Pentru a calcula $p(n, k)$ vom folosi programare dinamică astfel:

Se observă că putem obține o partiție de lungime $k$ a lui $n$ în două moduri. Fie luăm o partiție de lungime $k - 1$ a lui $n - 1$ și adăugăm elementul $1$ la începutul ei, fie luăm o partiție de lungime $k$ a lui $n - k$ și incrementăm toate elementele acesteia. De exemplu, partiția $[1, 2, 2]$ se obține adăugându-l pe $1$ la începutul lui $[2, 2]$ pe când $[2, 2]$ se obține incrementând elementele lui $[1, 1]$ Astfel, orice partiție se poate obține pornind de la mulțimea vidă, aplicând asupra acesteia, pe rând, mai multe operații de aceste două feluri. De pildă, pentru a-l obține pe $[3, 4, 4]$ procedăm astfel:

\varnothing \xrightarrow{+1} [1] \xrightarrow{+1} [1, 1] \xrightarrow{++} [2, 2] \xrightarrow{+1} [1, 2, 2] \xrightarrow{++} [2, 3, 3] \xrightarrow{++} [3, 4, 4]

Așadar, recurența dinamicii noastre este următoarea:

p(n, k) = \begin{cases} p(n - 1, k - 1) + p(n - k, k) & \text{pentru } n \ge 1, k \ge 1\\ 0 & \text{pentru } n \ge 1, k = 0\\ 1 & \text{pentru } n = 0, k = 0 \end{cases}

Complexitatea pentru calcularea lui $p(n, k)$ este, evident, $O(n^2)$ Nu putem optimiza nimic, și probabil nu există o soluție mai bună. Putem folosi această dinamică și pentru a calcula $p(n)$

p(n) = p(n, 1) + p(n, 2) + \cdots + p(n, n) \text{ pentru } n \ge 1

Însă, pentru cerința asta există o soluție mai bună decât cea în $O(n^2)$ ce se bazează pe recurența liniară despre care vorbeam la începutul articolului.

Numărul total de partiții neordonate

În primul rând, trebuie să definim noțiunea de funcție generatoare. Funcția generatoare a unui șir $(a_n)_{n \ge 0}$ este o funcție ce poate fi scrisă ca o serie de forma:

\sum_{n = 0}^\infty a_n x^n

O serie este un șir infinit între elementele căruia se pune semnul $+$

Vom demonstra mai întâi că următoarea funcție este funcția generatoare a șirului $f$

\prod_{k = 1}^\infty \sum_{i = 0}^\infty x^{ki} = (1 + x^1 + x^2 + x^3 + \cdots)(1 + x^2 + x^4 + x^6 + \cdots)(1 + x^3 + x^6 + x^9 + \cdots) \cdots

Dacă desfacem parantezele, înainte să grupăm termenii asemenea, fiecare coeficient al lui $x^n$ va fi practic o partiție a lui $n$ De ce? Ei bine, exponentul $n$ provine dintr-o expresie de forma $a_1 1 + a_2 2 + a_3 3 + \cdots$ Aici, $a_i$ reprezintă practic frecvența lui $i$ în cadrul partiției. De exemplu, $1 \cdot 1 + 3 \cdot 2 + 0 \cdot 3 + 2 \cdot 4 + 0 \cdot 5 + 0 \cdot 6 + \cdots$ este partiția $[1, 2, 2, 2, 4, 4]$ Deci, coeficientul lui $n$ în seria noastră va fi într-adevăr $p(n)$

Aici începe partea interesantă. Acum trebuie să calculăm eficient coeficienții seriei de mai sus. Observăm că fiecare paranteză $k$ este suma unei progresii geometrice de rație $x^k$ Evident, dacă $x \gt 1$ progresia e divergentă. Dar dacă nu, aceasta converge la $(1-x^k)^{-1}$ Înlocuim seriile cu limitele lor și obținem:

\sum_{n = 0}^\infty p(n) x^n = \prod_{k = 1}^\infty \frac{1}{(1 - x^k)}

De unde:

\left ( \sum_{n = 0}^\infty p(n) x^n \right ) \left ( \prod_{n = 1}^\infty (1 - x^n) \right ) = 1

Aici aplicăm Teorema numerelor pentagonale, formulată de Euler, care ne spune că:

\prod_{n = 1}^\infty (1 - x^n) = \sum_{k = -\infty}^\infty (-1)^k x^{k (3k - 1) / 2} = 1 - x^1 - x^2 + x^5 + x^7 - x^{12} - x^{15} + \cdots

Semnele alternează din $2$ în $2$ iar exponenții sunt dați de șirul numerelor pentagonale generalizate, adică numerele de forma $g(k) = k (3k - 1) / 2$ unde $k$ ia pe rând valorile $+1, -1, +2, -2, \ldots$

Ne întoarcem la ecuația noastră și obținem:

\sum_{n = 0}^\infty \left ( p(n) + \sum_{g(k) \le n} (-1)^k p(n - g(k)) \right ) x^n = 1

Egalăm coeficienții termenilor de grad egal din cele două polinoame și obținem în sfârșit recurența de care avem nevoie:

p(n) = \begin{cases} \sum_{g(k) \le n} (-1)^{k + 1} p(n - g(k)) & \text{pentru } n \ge 1\\ 1 & \text{pentru } n = 0 \end{cases}

Implementare

Mai jos aveți sursa mea la problema Crescător2 de pe InfoArena, care, după cum am spus și la început, cere determinarea sumei $p(1) + p(2) + \cdots + p(n)$ Mai întâi am precalculat numerele pentagonale până la $n$ iar apoi am calculat dinamica mergând la fiecare pas până la cel mai apropiat număr pentagonal de $i$

Problema Crescător2
#include <bits/stdc++.h>
using namespace std;

ifstream fin("crescator2.in");
ofstream fout("crescator2.out");

const int MOD = 700001;

inline void add(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub(int& x, int y) { x -= y; if (x <    0) x += MOD; }

int main() {
    int n; fin >> n;
    vector<int> pent(n);
    for (int i = 0, j = 1; i < n; i++, j = -j + (j <= 0))
        pent[i] = (3 * j * j - j) / 2;

    vector<int> dp(n + 1);
    dp[0] = 1;
    int sol = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; pent[j] <= i; j++)
            if (j & 2)
                sub(dp[i], dp[i - pent[j]]);
            else
                add(dp[i], dp[i - pent[j]]);
        add(sol, dp[i]);
    }
    fout << sol << '\n';
    return 0;
}

Complexitate

Complexitatea soluției este $O(n \sqrt{n})$ pentru că numărul pentagonal maxim până la care se iterează la fiecare pas este aproximativ $g(\sqrt{2 n / 3})$ Asta se înmulțește cu $2$ deoarece pentru fiecare $k$ luăm în considerare și $g(+k)$ și $g(-k)$ Așadar, constanta din spatele complexității este de aproximativ $2 \cdot \sqrt{2 / 3} = 1.63$

Sfârșit! Dacă aveți vreo întrebare despre partițiile unui număr natural, o puteți lăsa mai jos, într-un comentariu :smile: