TD : Entiers - dénombrement

Exercice 1

> sum(k^2,k=1..n);

> factor(");

> sum(k^3,k=1..n);

> factor(");

Exercices 2 et 3

> seq(3^(2*n+1)+2^(n+2) mod 7,n=0..30);

> seq(2^(2*n)+15*n-1 mod 9,n=0..30);

Exercice 4

> sum(sum(i*j,j=i..n),i=1..n);

> factor(");

> sum(sum((i+j)^2,j=i..n),i=1..n);

> factor(");

Exercice 6

> irem(1789,10),iquo(1789,10);

> phi:=n->if n<=9 then n else irem(n,10)+phi(iquo(n,10)) fi;

> phi(1515);

> N:=4444^4444:

> evalf(ln(N)/ln(10));

La représentation décimale de N possède donc 16211 chiffres...

> phi(N);

Error, (in phi) too many levels of recursion

Pas très surprenant : on va la refaire en itératif...

> phi2:=proc(n)
local reste,compt;
reste:=n;
compt:=0;
while reste>0 do
compt:=compt+irem(reste,10);
reste:=iquo(reste,10) od;
RETURN(compt+reste)
end:

> phi2(1515);

> phi2(N);

> phi2(");

> phi2(");

Exercice 9

> ni:=product(365-i,i=0..44);

> evalf(ni/365^45);

> 1-";

C'est la probabilité pour qu'au moins deux personnes parmi 45 aient même date anniversaire...

> limit((n^2)!/(n^2-2*n)!/(n^2)^(2*n),n=infinity);

> evalf(");

> limit((n^2)!/(n^2-3*n)!/(n^2)^(3*n),n=infinity);

> evalf(");

Permutations : exercices 11 et 14

Générons l'ensemble des permutations

> insere:=(l,it,pos)->[seq(l[j],j=1..pos-1),it,seq(l[j],j=pos..nops(l))];

Warning, `j` in call to `seq` is not local

Warning, `j` in call to `seq` is not local

> insere([12,3,5],2,1);

> insere([12,3,5],2,2);

> insere([12,3,5],2,3);

> insere([12,3,5],2,4);

> permut:=proc(n)
local prec,res;
if n=1 then RETURN([[1]]) fi;
prec:=permut(n-1);
res:=NULL;
for k from n to 1 by -1 do
for l from 1 to (n-1)! do res:=res,insere(prec[l],n,k) od od;
RETURN([res])
end;

Warning, `k` is implicitly declared local

Warning, `l` is implicitly declared local

> permut(4);

> nops(");

Nombre moyen de points fixes (exo 14)

> points_fixes:=proc(l)
local k,r;
r:=0;
for k from 1 to nops(l) do if l[k]=k then r:=r+1 fi od;
RETURN(r);
end;

> points_fixes([2,1,3,4]);

> total_points_fixes:=proc(n)
local l,r;
l:=permut(n);
r:=0;
for k from 1 to n! do r:=r+points_fixes(l[k]) od;
RETURN(r)
end;

Warning, `k` is implicitly declared local

> total_points_fixes(5);

> seq(total_points_fixes(n),n=1..7);

> seq(k!,k=0..7);

Nombre moyen de dérangements (exo 11)

> nb_derangements:=proc(n)
local l,r;
l:=permut(n);
r:=0;
for k from 1 to n! do if points_fixes(l[k])=0 then r:=r+1 fi od;
RETURN(r)
end;

Warning, `k` is implicitly declared local

> nb_derangements(5);

> seq(nb_derangements(i)/i!,i=1..7);

> evalf(");

> evalf(exp(-1));

Exercice 15

> sum((-1)^k*binomial(n,k),k=0..n);

> sum(k*binomial(n,k),k=0..n);

> sum((-1)^(k+1)*k*binomial(n,k),k=0..n);

> sum(k*(k-1)*binomial(n,k),k=0..n);

Exercice 16

> sum(k^2*binomial(n,k),k=0..n);

> factor(");

Exercice 17

> sum(binomial(p+i,p),i=0..k);

> convert(",GAMMA);

> convert(binomial(p+k+1,p+1),GAMMA);

> simplify("-"");

Il s'agit d'une suite "hyper-géométrique" : on dispose d'algorithmes pour "calculer" de telles sommes.

Cela dit, pour le 18, je n'ai pas réussi à m'en sortir.

Exercice 19

> Q:=n->add((-1)^k*binomial(2^n-k,k),k=0..2^n):

Warning, `k` in call to `add` is not local

> seq(Q(n),n=0..10);

> R:=p->add((-1)^k*binomial(p-k,k),k=0..p):

Warning, `k` in call to `add` is not local

> seq(R(p),p=0..30);