




		PARTITIE
	       ----------

	Orice numar intreg se poate descompune in termeni; astfel, numarul 4 se poate
descompune in 5 moduri: 4 = 3+1 = 2+2 = 2+1+1= 1+1+1+1. Daca notam cu n numarul de des-
compus si cu p[n] numarul de moduri in care se poate descompune, putem scrie: p[1]=1,
p[2]=2,p[3]=3,p[4]=5,p[5]=7,p[6]=11,etc. Sa se determine p[n], oricare n natural.

	Problema a fost abordata de Euler, apoi de matematicianul MacMahon care a cal-
culat p[100]=190569292. Mai tarziu s-au calculat si alte valori pentru p[n].
	Pentru rezolvarea problemei vom introduce notatia p[n,k] reprezentand numarul
de moduri in care se poate partitiona n, in asa fel incat fiecare partitie sa contina
cel putin un termen cu valoarea k, iar restul termenilor sa aiba valori mai mici sau
egale cu k.
	Convenim sa notam prin p[n,0] numarul total al partitiilor lui n (adica p[n]).



	  -> 1, pt. k=n
p[n,k] =  -> p(n-k,0), pentru n<=2k
	  -> p[n-k,1] + p[n-k,2] + .. + p[n-k,k] , in rest

p[n,0] = p[n,1] + p[n,2] + .. + p[n,k].


	Se observa si urmatoarea recurenta: p[n,1] = p[n,2] = p[n,3] + .. + p[n,k] =
= p[n+k,k].