Les nombres de Catalan (combinatoire) : nombres de parenth\303\250sages bien balanc\303\251s.
CN := binomial(2*n,n)/(n+1) ;
interface(elisiondigitsthreshold=100,
elisiondigitsbefore=10,
elisiondigitsafter=10) :
Calcul par du Maple de base : mauvais exposant de complexit\303\251 !
ti := time() :
eval(CN, n=50000) ;
time() - ti ;
ti := time() :
eval(CN, n=100000) ;
time() - ti ;
ti := time() :
eval(CN, n=200000) ;
time() - ti ;
Calcul par le scindage binaire : quasi-optimal !
with(gfun) :
with(NumGfun) :
rapport := normal(eval(CN, n=n+1)/CN, expanded) ;
rec[Catalan] := { C(n+1)=rapport*C(n), C(0)=1 } ;
ti := time() :
nth_term(rec[Catalan], C(n), 50000) ;
time() - ti ;
ti := time() :
nth_term(rec[Catalan], C(n), 100000) ;
time() - ti ;
ti := time() :
nth_term(rec[Catalan], C(n), 200000) ;
time() - ti ;
ti := time() :
nth_term(rec[Catalan], C(n), 400000) ;
time() - ti ;