Universite Paris Master Math Info Institut Galilee

De
Publié par

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


Publié le : vendredi 8 juin 2012
Lecture(s) : 88
Source : www-lipn.univ-paris13.fr
Nombre de pages : 213
Voir plus Voir moins
Université Paris 13 InstitutGalilée
Analyse
Master MathInfo
de structures de données etdalgorithmes
Polycopié ChristianLavault
Table
1
2
3
des
matières
Combinatoire et dénombrement 1.1 Permutations, arrangements et combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Applications au dénombrement d’ensembles finis . . . . . . . . . . . . . . . . . . . . . . . 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 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Equations de récurrence linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Récurrences linéaires homogènes à coefficients constants . . . . . . . . . . . . . . . 2.2.2 Récurrences linéaires générales à coefficients constants . . . . . . . . . . . . . . . . 2.2.3 Récurrences linéaires à coefficients 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œfficients constants 3.3.2 Récurrences linéaires générales à cœfficients constants . 3.3.3 Récurrences linéaires à cœfficients variables . . . . . . . 3.3.4 Récurrences complètes . . . . . . . . . . . . . . . . . . . 3.4 Analyse en moyenne d’algorithmes . . . . . . . . . . . . . . . . 3.4.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . .
i
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
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
ii
4
5
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 suffisantes . . . . . . . . . . . . . . . . . . . . . . . . . 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 coefficients . . . . . 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
T.D. 1 – Combinatoire et dénombrement
Correction du T.D. 1
6
T.D. 2 – Relations de récurrence
T.D. 2 – Relations de récurrence
Correction du T.D. 2
7
T.D. 3 – Séries génératrices, asymptotique
T.D. 3 – Séries génératrices, asymptotique
Correction du T.D. 3
A Intégrale de Stieljes
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
49
51 51 53 53 54 56 56 57 57 59 60 61 61 62 62 65 66 67 67 68 68 68 69
71
71
75
83
83
89
99
99
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
1
Combinatoire
et
dénombrement
Dans la suite, on étudie des outils et techniques permettant de compter (ou dedénombrer) des ensembles finiset leurs sousensembles, si possible sans énumérer tous leurs éléments.
1.1
Permutations,
arrangements et combinaisons
Définition 1.1.1Unepermutationσd’un ensemble fini 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 identifiantEet{1, . . . , n} ≡[n], une permutationσest définie 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)}(soitn1), etc. [Faire ce raisonnement par induction, i.e. par récurrence.]
Définition 1.1.3 (i)Unarrangementd’ordre k (0kn) d’un ensemble fini 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 (0kn) n d’un ensemble à n éléments. (ii)Unecombinaisond’ordre k (0kn) d’un ensemble fini E tel que|E|=nest un sous   n ensemble de E ayant k éléments. désigne le nombre de combinaisons d’ordre k (0kn) d’un   k n ensemble à n éléments ; les (0kn) sont nommés lescoefficients 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(n1)∙ ∙ ∙(nk+ 1)n, oùnest appelée lafactorielle n 0 descendantedenà l’ordrek(0knavecn= 1). Cette notation permet de simplifier les preuves de   n bien des identités sur les . k k0 On note de mêmenn(n+ 1)∙ ∙ ∙(n+k1), oùn= 1 lafactorielle montantedenà l’ordrek (0kn). (Voir l’exercice 1 du T.D. 1.)
2
COMBINATOIREETDÉNOMBREMENT
2.Les combinaisons sont non ordonnées, alors que les arrangements sont ordonnés [vérifier]. Donc, chaque combinaison d’ordrekdonne naissance àk! arrangements et [vérifier]   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 différentes ont la même   k n image, on retrouve l’identitéA=k! [vérifier]. n k   ok1 1n 3.Pour toutnN, on a 1 par définition deA),A=n= =n; n n 1     on n0 0n n 2 par convention, 0! = 1, donc,A=n=n! etA=n= = = 1 [vérifier]. n n n0 4.Comme conséquence de 3), on a enfin pour toutkn,   k n!nn n ! k k A=n= et = =. n (nk)!k k!k!(nk)!
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+k1 = k
k n k!
sans répétition sans remise
k n=n(n1)∙ ∙ ∙(nk+ 1)
  n = k
k n k!
Tab.1.1 – Arrangements et combinaisons avec/sans répétition.
Proposition 1.1.6Les coefficients binomiaux vérifient les relations de récurrence suivantes (netk entiers positifs)     n n (i) =pour0kn. k nk       n n1n1 (ii) = +pour n, k1. k k k1     n n n1 (iii) =pour n, k1. k k k1         n kn1r r+k1 k k (iv() = 1)ret, pour C, kZ,= (1). k k k k
1.1. PERMUTATIONS, ARRANGEMENTS ET COMBINAISONS
3
Démonstration : (i) La relation (i) découle immédiatement de la définition 1.1.3, des remarques 1.1.5) et du tableau 1.1.   n (ii) Pour prouver (ii), choisissonseE, où|E|=nN, et séparons les combinaisons d’ordre k kndeEen deux ensembles disjointsE1etE2:   n1 E1est l’ensemble des combinaisons deEne contenant pase:|E1|= ; k   n1 E2est l’ensemble des combinaisons deEqui contiennente:|E2|= . k1 Les deux ensemblesE1etE2étant disjoints, on a bien l’identité (ii). (iii)(iv) se démontrent par application directe de la définition 1.1.3 (remarques 1.1.5).
Remarques 1.1.7 1.(étireuredncielntdeerécgledlarèdiretàcse¿l,¿saacePedglanri¡tu¡eddialÀii), on peut   n calculer les coefficients binomiaux successifs. k 2.La définition des coefficients 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érifier] k x   sikN x k! k0 sik /N.
3.énngaléréeises,lnediétit(Àpartidrceteetédntioiii), (iii) et (iv) de la proposition 1.1.6 s’étendent naturellement à toutn=zCetkZ(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 coefficients, avec des termes supérieurs négatifs, etc.
Proposition 1.1.8(Formule du binôme) Soit A un anneau,a, bApermutables (i.e. tels queab=ba) etnN, alors n  X n n nk 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érifié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+1nk+1k nk k+1 (a+b) =a b+a b k k k=0k=0  n n1    X X n n n n n+1nk+1k nk k+1n+1 =a+a b+a b+b . 0nk k k=1k=0
Soit,
 n     X n n n n n+1n+1n+1nk k +1 (a+b) =a+ +a b+b . 0k1k n k=1
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.