De ce contează?
Ai patru bile identice și vrei să le împarți în grămezi. Poți face o grămadă de 4, sau 3 și 1, sau 2 și 2, sau 2 și 1 și 1, sau patru grămezi de câte una. Cinci moduri — și niciunul nu se repetă, fiindcă bilele sunt identice: „3 și 1" e aceeași împărțire ca „1 și 3". Numărul acestor împărțiri se cheamă numărul de partiții al lui 4.
Intuiția
O partiție a lui n este o scriere a lui n ca sumă de numere naturale pozitive, în care ordinea nu contează. Pentru n = 4 avem 5 partiții: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
Truc-ul ca să nu numeri de două ori aceeași sumă: scrie întotdeauna părțile descrescător. Atunci fiecare grămadă are o singură formă, iar întrebarea devine: „de la cea mai mare parte în jos, ce termen pun primul?". Vom număra cu un plafon: p(n, k) = câte partiții ale lui n folosesc părți de cel mult k.