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

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

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 SS Asta înseamnă practic numărul de partiții neordonate ale numerelor naturale nenule mai mici sau egale cu SS În timpul simulării am luat 40 de puncte cu o dinamică în O(n2)O(n^2) însă upsolving-ul mi-a luat câteva ore bune, pentru că soluția oficială folosea un truc legat de n\sqrt{n} iar mie nu-mi plac trucurile legate de radical 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

Ce sunt partițiile unui număr natural?

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

De exemplu, partițiile ordonate ale lui 44 sunt:

(1,1,1,1),(1,1,2),(1,2,1),(1,3),(2,1,1),(2,2),(3,1),(4)(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 44 sunt:

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

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

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

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)p(n, k) numărul de partiții ordonate ale lui nn de lungime kk 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 nn în kk secvențe de lungimi nenule. De exemplu, șirul xxxxx poate fi împărțit în 33 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 nn î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 k1k - 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,,n1}\{1, 2, \ldots, n - 1\} Cum ele trebuie să fie distincte, se observă ușor că soluția e dată de Cn1k1C_{n - 1}^{k - 1}

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

p(n)=Cn10+Cn11++Cn1n1=2n1p(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)p(n, k) vom folosi programare dinamică astfel:

Se observă că putem obține o partiție de lungime kk a lui nn în două moduri. Fie luăm o partiție de lungime k1k - 1 a lui n1n - 1 și adăugăm elementul 11 la începutul ei, fie luăm o partiție de lungime kk a lui nkn - k și incrementăm toate elementele acesteia. De exemplu, partiția [1,2,2][1, 2, 2] se obține adăugându-l pe 11 la începutul lui [2,2][2, 2] pe când [2,2][2, 2] se obține incrementând elementele lui [1,1][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][3, 4, 4] procedăm astfel:

+1[1]+1[1,1]++[2,2]+1[1,2,2]++[2,3,3]++[3,4,4]\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)={p(n1,k1)+p(nk,k)pentru n1,k10pentru n1,k=01pentru n=0,k=0p(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)p(n, k) este, evident, O(n2)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)=p(n,1)+p(n,2)++p(n,n) pentru n1p(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(n2)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 (an)n0(a_n)_{n \ge 0} este o funcție ce poate fi scrisă ca o serie de forma:

n=0anxn\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 ff

k=1i=0xki=(1+x1+x2+x3+)(1+x2+x4+x6+)(1+x3+x6+x9+)\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 xnx^n va fi practic o partiție a lui nn De ce? Ei bine, exponentul nn provine dintr-o expresie de forma a11+a22+a33+a_1 1 + a_2 2 + a_3 3 + \cdots Aici, aia_i reprezintă practic frecvența lui ii în cadrul partiției. De exemplu, 11+32+03+24+05+06+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][1, 2, 2, 2, 4, 4] Deci, coeficientul lui nn în seria noastră va fi într-adevăr p(n)p(n)

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

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

De unde:

(n=0p(n)xn)(n=1(1xn))=1\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ă:

n=1(1xn)=k=(1)kxk(3k1)/2=1x1x2+x5+x7x12x15+\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 22 în 22 iar exponenții sunt dați de șirul numerelor pentagonale generalizate, adică numerele de forma g(k)=k(3k1)/2g(k) = k (3k - 1) / 2 unde kk ia pe rând valorile +1,1,+2,2,+1, -1, +2, -2, \ldots

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

n=0(p(n)+g(k)n(1)kp(ng(k)))xn=1\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)={g(k)n(1)k+1p(ng(k))pentru n11pentru n=0p(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)++p(n)p(1) + p(2) + \cdots + p(n) Mai întâi am precalculat numerele pentagonale până la nn iar apoi am calculat dinamica mergând la fiecare pas până la cel mai apropiat număr pentagonal de ii

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(nn)O(n \sqrt{n}) pentru că numărul pentagonal maxim până la care se iterează la fiecare pas este aproximativ g(2n/3)g(\sqrt{2 n / 3}) Asta se înmulțește cu 22 deoarece pentru fiecare kk luăm în considerare și g(+k)g(+k) și g(k)g(-k) Așadar, constanta din spatele complexității este de aproximativ 22/3=1.632 \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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii