Triunghiul numerelor de partiții

Referitor la partițiile numerelor întregi^⁠(d), studiate în teoria numerelor și combinatorică, semnificația numerelor $p_{k}(n)$ este atât numărul de partiții ale lui $n$ în exact $k$ părți (adică sume de $k$ întregi pozitivi egale cu $n$), cât și numărul de partiții ale lui $n$ în părți de dimensiune maximă exact $k$. Aceste două tipuri de partiții sunt bijective unul cu celălalt, printr-o reflexie diagonală a tablourilor lui Young^⁠(d) asociate numerelor. Numerele de partiții pot fi aranjate într-un triunghi, triunghiul numerelor de partiții, în care rândul $n$ conține numerele de partiții $p_{1}(n),p_{2}(n),\dots ,p_{n}(n)$:

k n	1	2	3	4	5	6	7	8	9
1	1
2	1	1
3	1	1	1
4	1	2	1	1
5	1	2	2	1	1
6	1	3	3	2	1	1
7	1	3	4	3	2	1	1
8	1	4	5	5	3	2	1	1
9	1	4	7	6	5	3	2	1	1

Relația de recurență

Analog cu triunghiul lui Pascal, aceste numere pot fi calculate folosind relația de recurență:

$p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k).$

Drept cazuri particulare, $p_{1}(1)=1,$ iar orice valoare din partea dreaptă a recurenței care ar fi în afara triunghiului poate fi luată zero. Această ecuație poate fi explicată notând că fiecare partiție a $n$ din $k$ părți, enumerate de $p_{k}(n),$ poate fi formată fie prin adăugarea unei părți de mărimea 1 la o partiție de $n-1$ în $k-1$ părți, enumerate de $p_{k-1}(n-1),$ sau prin creșterea cu câte 1 parte a fiecărei partiții de $n-k$ din $k$ părți, enumerate de $p_{k}(n-k).$

Sumele rândurilor și diagonalelor

În triunghiul numerelor de partiții, suma numerelor din rândul $n$este numărul de partiții^⁠(d) $p(n)$. Aceste numere formează succesiunea:

1, 2, 3, 5, 7, 11, 15, 22, ...

omițând valoarea inițială $p(0)=1$ a numerelor partițiilor.

Fiecare diagonală de la stânga sus la dreapta jos este, începând de la un anumit rând, constantă, părțile constante ale acestor diagonale extinzându-se aproximativ de la jumătatea fiecărui rând până la capătul său. Valorile acestor constante sunt, din nou, numerele de partiții 1, 1, 2, 3, 5, 7, ... .