Universite Paris Master Math Info Institut Galilee

213 pages

Français

Universite Paris Master Math Info Institut Galilee

cidur - Christian Lavault

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

213 pages

Français

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Niveau: Supérieur, Master
Universite Paris 13 Master Math-Info Institut Galilee Analyse de structures de donnees et d'algorithmes Polycopie ????-???? Christian Lavault

relations de recurrence

developpement asymptotique

methode generale d'analyse asymptotique des coefficients

methode de laplace

encadrements de sommes partielles

analyse en moyenne d'algorithmes

recurrences lineaires

series generatrices

approximations asymptotiques

Sujets

Méthode de Laplace

Informations

Publié par	cidur
Nombre de lectures	101
Langue	Français

Extrait

Université Paris 13 InstitutGalilée

Analyse

Master MathInfo

de structures de données etd’algorithmes

Polycopié ChristianLavault

Table

des

matières

Combinatoire et dénombrement 1.1 Permutations, arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Applications au dénombrement d’ensembles ﬁnis . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Formules d’exclusioninclusion et applications . . . . . . . . . . . . . . . . . . . . . 1.3 Manipulation de suites et de sommes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Suites, sommes et opérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Méthodes usuelles de sommation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Manipulation de sommes multiples . . . . . . . . . . . . . . . . . . . . . . . . . . .

Relations de récurrence 2.1 Rappels et généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Exemples de relations de récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Classiﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Equations de récurrence linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Récurrences linéaires homogènes à coeﬃcients constants . . . . . . . . . . . . . . . 2.2.2 Récurrences linéaires générales à coeﬃcients constants . . . . . . . . . . . . . . . . 2.2.3 Récurrences linéaires à coeﬃcients variables . . . . . . . . . . . . . . . . . . . . . . 2.3 Equations de récurrence non linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Récurrences de partition et changement de variable . . . . . . . . . . . . . . . . . . 2.3.2 Transformation du domaine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Séries génératrices et applications 3.1 Séries génératrices . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 L’anneau des séries formelles . . . . . . . . . . . . . . . 3.1.2 Développement en série au voisinage de l’origine . . . . 3.1.3 Fonctions génératrices ordinaires et exponentielles . . . 3.2 Développement en série des fractions rationnelles . . . . . . . . 3.2.1 Décomposition en éléments simples . . . . . . . . . . . . 3.2.2 Développement au voisinage de l’origine . . . . . . . . . 3.2.3 Cas de racines multiples . . . . . . . . . . . . . . . . . . 3.3 Applications aux équations de récurrence . . . . . . . . . . . . 3.3.1 Récurrences linéaires homogènes à cœﬃcients constants 3.3.2 Récurrences linéaires générales à cœﬃcients constants . 3.3.3 Récurrences linéaires à cœﬃcients variables . . . . . . . 3.3.4 Récurrences complètes . . . . . . . . . . . . . . . . . . . 3.4 Analyse en moyenne d’algorithmes . . . . . . . . . . . . . . . . 3.4.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

1 1 5 5 5 7 7 8 10

13 13 13 14 15 15 18 21 22 22 23

29 29 29 30 31 38 38 38 40 41 41 45 46 47 49 49

4.1 4.2 4.3 4.4 4.5 4.6 4.7

3.4.2

TABLEDESMATIÈRES

Utilisation des séries génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Comportements asymptotiques Fonctions dominées, négligeables, équivalentes . . . . . . . . . . . . . . . . Critères de comportement asymptotique . . . . . . . . . . . . . . . . . . . 4.2.1 Conditions suﬃsantes . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Échelle de comparaison et développement asymptotique . . . . . . Approximations asymptotiques . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Encadrements de sommes partielles . . . . . . . . . . . . . . . . . . Asymptotique des séries génératrices . . . . . . . . . . . . . . . . . . . . . 4.4.1 Approximations asymptotiques des récurrences linéaires . . . . . . 4.4.2 Calcul direct du terme asymptotique dominant . . . . . . . . . . . 4.4.3 Méthode générale pour les fractions rationnelles . . . . . . . . . . . 4.4.4 Bornes du rayon de convergence . . . . . . . . . . . . . . . . . . . 4.4.5 Méthode générale d’analyse asymptotique des coeﬃcients . . . . . Formule d’EulerMaclaurin . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Formule sommatoire d’EulerMaclaurin et applications . . . . . . . 4.5.2 Développement asymptotique des nombres harmoniques . . . . . . 4.5.3 Développement asymptotique complet de la factorielle . . . . . . . Approximations asymptotiques . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Développement asymptotique des nombres de Catalan . . . . . . . 4.6.2 Développements asymptotiques bivariés . . . . . . . . . . . . . . . Deux méthodes asymptotiques . . . . . . . . . . . . . . . . . . . . . . . . 4.7.1 Le«reboutement»ouBootstrapping. . . . . . . . . . . . . . . . 4.7.2 Méthode de Laplace – borner les queues, approcher et étendre . .

T.D. 1 – Combinatoire et dénombrement

Correction du T.D. 1

T.D. 2 – Relations de récurrence

Correction du T.D. 2

T.D. 3 – Séries génératrices, asymptotique

Correction du T.D. 3

A Intégrale de Stieljes

. . . . . . . . . . . . . . . . . . . . . .

51 51 53 53 54 56 56 57 57 59 60 61 61 62 62 65 66 67 67 68 68 68 69

113

141

B Nombres et fonctions spéciaux 143 B.1 Les nombres de Stirling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 B.1.1 Les nombres de Stirling de première espèce . . . . . . . . . . . . . . . . . . . . . . 143 B.1.2 Les nombres de Stirling de seconde espèce . . . . . . . . . . . . . . . . . . . . . . . 143 B.1.3 les nombres de Stirling de seconde espèce . . . . . . . . . . . . . . . . . . . . . . . 143

B.2 B.3 B.4 B.5 B.6

TABLEDESMATIÈRES

B.1.4 Les nombres de Bell . . . . . . . . . . . B.1.5 Les nombres eulériens . . . . . . . . . . Les nombres et polynômes de Bernoulli . . . . La fonction Gamma . . . . . . . . . . . . . . . B.3.1 Développement asymptotique de Γ(z) . B.3.2 La fonction Gamma tronquéeγ(z, r) . . La fonction zêta de Riemann . . . . . . . . . . B.4.1 Les nombres harmoniques . . . . . . . . B.4.2 Généralisation à la fonctionζ(s) . . . . B.4.3 Développement asymptotique deζ(s) . Les séries de Dirichlet . . . . . . . . . . . . . . Les fonctions arithmétiques . . . . . . . . . . . B.6.1 La fonction totient d’Eulerφ(n) . . . .

C Examens, Devoirs – énoncés et corrigés

Bibliographie

. . . . . . . . . . . . .

iii

143 143 143 143 144 144 144 144 144 144 144 144 144

145

205

Chapitre

Combinatoire

dénombrement

Dans la suite, on étudie des outils et techniques permettant de compter (ou dedénombrer) des ensembles ﬁniset leurs sousensembles, si possible sans énumérer tous leurs éléments.

1.1

Permutations,

arrangements et combinaisons

Déﬁnition 1.1.1Unepermutationσd’un ensemble ﬁni E est une bijection de E dans E. L’ensemble des permutations d’un ensemble ànéléments est notéSnet|Sn|=n!

Remarques 1.1.2 1.En identiﬁantEet{1, . . . , n} ≡[n], une permutationσest déﬁnie par une bijection [n]←→[n] qui détermine un ordre total dansEdonné par la suiteσ(1),σ. .,(2), . σ(n). 2.On peut montrer que|Sn|=n! par induction, en décomptant le nombre de choix possibles pour σ(1) dans [n] (soitn), puis,σ(1) étant donné dans [n], le nombre de choix possibles pourσ(2) dans [n]\ {σ(1)}(soitn−1), etc. [Faire ce raisonnement par induction, i.e. par récurrence.]

Déﬁnition 1.1.3 (i)Unarrangementd’ordre k (0≤k≤n) d’un ensemble ﬁni E tel que|E|=nest un sousensemble k totalement ordonné de E ayant k éléments.Adésigne le nombre d’arrangements d’ordre k (0≤k≤n) n d’un ensemble à n éléments. (ii)Unecombinaisond’ordre k (0≤k≤n) d’un ensemble ﬁni E tel que|E|=nest un sous   n ensemble de E ayant k éléments. désigne le nombre de combinaisons d’ordre k (0≤k≤n) d’un   k n ensemble à n éléments ; les (0≤k≤n) sont nommés lescoeﬃcients binomiaux. k

Exemple 1.1.4SoitE={a, b, c}. – (a, b, c),(a, c, b),(b, a, c),(b, c, a),(c, a, b),(c, b, a), sont les 3! = 6 permutations deE. 2 – (a, b),(b, a),(a, c),(c, a),(b, c),(c, b) sont lesA= 6 arrangements d’ordre 2 deE.   3 3 –{a, b},{a, c},{b, c}= 3 combinaisons d’ordre 2 desont les E. 2

Remarques 1.1.5 k k k 1.Le plus souvent, on noteA=n(n−1)∙ ∙ ∙(n−k+ 1)≡n, oùnest appelée lafactorielle n 0 descendantedenà l’ordrek(0≤k≤navecn= 1). Cette notation permet de simpliﬁer les preuves de   n bien des identités sur les . k k0 On note de mêmen≡n(n+ 1)∙ ∙ ∙(n+k−1), oùn= 1 lafactorielle montantedenà l’ordrek (0≤k≤n). (Voir l’exercice 1 du T.D. 1.)

COMBINATOIREETDÉNOMBREMENT

2.Les combinaisons sont non ordonnées, alors que les arrangements sont ordonnés [vériﬁer]. Donc, chaque combinaison d’ordrekdonne naissance àk! arrangements et [vériﬁer]   n k k A=n=k!. n k

Un arrangement d’ordrekest caractérisé par une injectionϕ: [k]−→[n] et une combinaison d’ordre kest caractérisée parl’imaged’une injection [k]−→[n]. Commek! injections diﬀérentes ont la même   k n image, on retrouve l’identitéA=k! [vériﬁer]. n k   ok1 1n 3.Pour toutn∈N, on a 1 par déﬁnition deA),A=n= =n; n n 1     on n0 0n n 2 par convention, 0! = 1, donc,A=n=n! etA=n= = = 1 [vériﬁer]. n n n0 4.Comme conséquence de 3), on a enﬁn pour toutk≤n,   k n!nn n ! k k A=n= et = =. n (n−k)!k k!k!(n−k)!

On peut résumer simplement les notions précédentes dans le tableau 1.1, où la mention ¡¡ avec/sans remise ¿¿ renvoie à un modèle d’urnes utilisé en combinatoire des probabilités.

avec ordre

sans ordre

avec répétition avec remise

k n

  n+k−1 = k

k n k!

sans répétition sans remise

k n=n(n−1)∙ ∙ ∙(n−k+ 1)

  n = k

k n k!

Tab.1.1 – Arrangements et combinaisons avec/sans répétition.

Proposition 1.1.6Les coeﬃcients binomiaux vériﬁent les relations de récurrence suivantes (netk entiers positifs)     n n (i) =pour0≤k≤n. k n−k       n n−1n−1 (ii) = +pour n, k≥1. k k k−1     n n n−1 (iii) =pour n, k≥1. k k k−1         n k−n−1−r r+k−1 k k (iv() = −1)ret, pour ∈C, k∈Z,= (−1). k k k k

1.1. PERMUTATIONS, ARRANGEMENTS ET COMBINAISONS

Démonstration : (i) La relation (i) découle immédiatement de la déﬁnition 1.1.3, des remarques 1.1.5) et du tableau 1.1.   n (ii) Pour prouver (ii), choisissonse∈E, où|E|=n∈N, et séparons les combinaisons d’ordre k k≤ndeEen deux ensembles disjointsE1etE2:   n−1 •E1est l’ensemble des combinaisons deEne contenant pase:|E1|= ; k   n−1 •E2est l’ensemble des combinaisons deEqui contiennente:|E2|= . k−1 Les deux ensemblesE1etE2étant disjoints, on a bien l’identité (ii). (iii)(iv) se démontrent par application directe de la déﬁnition 1.1.3 (remarques 1.1.5).

Remarques 1.1.7 1.(étireurednc’ielntdeerécgledlarèdiretà’cse¿l,¿saacePedglanri¡tu¡eddia’lÀii), on peut   n calculer les coeﬃcients binomiaux successifs. k 2.La déﬁnition des coeﬃcients binomiaux se généralise à toute valeur réelle ou complexe den(notée x) et tout entierk, positif ou négatif (voir l’exercice 1 du T.D. 1.), sous la forme [vériﬁer]  k x    sik∈N x k! ≡ k  0 sik /∈N.

3.énngaléréeises,lnediétit(Àpartidrceteetédnﬁtioiii), (iii) et (iv) de la proposition 1.1.6 s’étendent naturellement à toutn=z∈Cetk∈Z(aveck6= 0 pour (iii)). (Voir l’exercice 1 du T.D. 1.) 4.Avec la formule du binôme de la proposition 1.1.8 qui suit, les quatre identités de la proposition 1.1.6 sont fondamentales ; elles permettent de démontrer la plupart des relations binomiales — avec sommation et/ou produit des coeﬃcients, avec des termes supérieurs négatifs, etc.

Proposition 1.1.8(Formule du binôme) Soit A un anneau,a, b∈Apermutables (i.e. tels queab=ba) etn∈N, alors n  X n n n−k k (a+b) =.a b k k=0

Démonstration :Par induction surn. On pose(B)≡baseet(I)≡étape inductive.       0 0 1 1 (B)Sin= 0, (a+b) = = 1. Sin= 1,a+b=a+b. 0 0 1 (I)Supposons la formule vériﬁée à l’ordren >1, entier quelconque (hypothèse de récurrence). n+1n Alors, en utilisant l’égalité (a+b() = a+b) (a+b), on obtient n n  X X n n n+1n−k+1k n−k k+1 (a+b) =a b+a b k k k=0k=0  n n−1    X X n n n n n+1n−k+1k n−k k+1n+1 =a+a b+a b+b . 0nk k k=1k=0

Soit,