• Arbres binaires, completes ou elagues; sommets internes et externe. On a coutume de prendre comme notion de taille le nombre de sommets internes, car cela determine le reste. Exercice(*): Le prouver, par exemple en comptant les aretes selon sources et destination. La famille des arbres binaires est specifiable par une grammaire quadratique; la serie generatrice est donc du second degre; d'ou par binome de Newton (avec exposant fractionnaire 1/2, ca marche!) l'expression classique des nombres de Catalan. Historiquement la methode (via les recurrences) remonte a Euler (1753) et c'est grosso modo la premiere intervention des series generatices en enumeration combinatoire. Voir aussi Catalan vers 1850. De toutes facons, on sait tout cela grace au cours de tronc commun de M. Pocchiola. L'asymptotique resulte de Stirling (4^n/sqrt{pi*n^3)), mais on verra plus tard qu'elle se lit aussi analytiquement a partir de la singularite placee en 1/4 et de son type en racine-carree.
• Arbres generaux. Ici, tous les degres sont permis. La taille est le nombre total de sommets. [Discussion: pourquoi pas ne compter que les sommets internes? Reponse: sinon, le probleme de denombrement devient trivial; donc il n'y a pas lieu de separer les feuilles des autres.] On a cette fois-ci une specification "homographique". Mais on retrouve facilement a decalage pres des indices la serie generatrice et les nombres de Catalan. Miracle? Non, car une bijection bien connue, la "rotation" (liens fils-aine et frere-cadet) montre que ceci etait attendu.
  Flash culturel sur la hauteur: si on avait itere', on aurait obtenu une fraction continue. Les reduites sont des fractions rationnelles qui donnent le denombrement d'arbres de hauteur <=h; De Bruijn, Knuth et Rice en 1972 en ont d'ailleurs tire' la hauteur moyenne d'un arbre de Catalan, qui vaut ~sqrt(pi*n). Question: et les arbres binaires? Reponse: Flajolet et Odlyzko montrent en 1980-1982 que c'est asymptotiquement 2*sqrt(pi*n). Je signale que c'est equivalent a analyser l'iteration de Mandelbrot dans le creux de la cardioide. La connexion combinatoire/algebre/analyse frappe encore! Autre question: mais on sait que les arbres binaires de recherche (ABR) ont profondeur ou hauteur logarithmique (Devroye 1986); et alors? Reponse: le modele des ABR est induit par les permutations; c'est un modele non uniforme comme on le voit des n=3. Ce dernier probleme est en fait un probleme de permutations aleatoires.
  
• Triangulations. Une triangulation d'un (n+2)-gone comporte n triangles. Le triangle qui contient l'arete (1,2) peut etre pris comme racine. On a lors une decomposition de type binaire, c-a-d quadratique. Crac, on retombe sur les nombres de Catalan (Le calcul peut se mener de deux manieres tres voisines selon qu'on autorise ou non la triangulation vide). Ceci montre aussi une evidente bijection avec les arbres binaires. C'est la en fait que se situe la decouverte par Euler en 1753 des nombres de Catalan et l'invention des series generatrices de denombrement (pour resoudre des problemes exprimes par des recurrences, a cette epoque).
  • Exercice: La compagnie MacroHard propose pour 100,000$ l'utilisation d'un brevet qui permet de representer en 1.753*n bits une triangulation de taille n, alors que votre representation par tripletes utilise O(n*log(n)) bits. Que faites-vous? Reponse: demander 50,000$ d'augmentation a votre patron et intenter un proces pour fraude contre cette ignominieuse compagnie. :-)
    En effet: un ensemble S de cardinalite s se represente en log2(s) bits. C'est necessaire et suffisant. Ici on doit utiliser au moins 2*n+o(n) bits, d'apres l'asymptotique des nombres de Catalan. On observe que si l'on voit une triangulation comme un arbre binaire, alors, on dispose d'un code par chemins dits de Dyck (cf. le cours de combinatoire), cas particulier des codes de Lukasiewicz [avec un L barre'], appele's plus tard "notation polonaise" prefixe (par faineantise). Le code obtenu de la sorte est donc a la fois compact (asymptotiquement optimal) et "naturel" (facile a exploiter).
    A ce propos, on discute enfin brievement le denombrement de termes selon diverses proprietes algebriques (c'est utile a l'analyse d'algorithmes en calcul formel, cf M. Soria et J-M. Steyaert qui ont beaucoup contribue' a la theorie), et on ajourne la seance sur ces entrefaits.

Cours 3 [6 Janvier 1999]

On revient a la philosophie de base. le dictionnaire nous donne un mecanisme de traduction qui partant d'une specification fournit une serie generatrice. On peut ainsi traduire des classes entieres de problemes combinatoires. Il est alors legitime de se poser la question: Quelles sont les classes de fonctions obtenues? Comment peut-on les traiter? C'est-a-dire, en extraire les coefficients, les analyser asymptotiquement. L'etude deja faite des "denumerants" donne une idee de ce que peut etre une telle approche. Aujourd'hui, on va voir deux cas importants: les langages reguliers et les familles simples d'arbres.
• Langages reguliers. Un alphabet (fini) etant fixe', on appelle langage un ensemble de mots sur cet alphabet. Rappelons que les mots se composent par l'operation de concatenation (qui s'etend aux langages). L'operation "etoile" (*) [de Kleene] signifie une repetition d'un mot (ou des mots d'un langage) un nombre fini de fois: X*=1+X+X.X+X.X.X+etc.
  Definition. La classe des langages reguliers est la plus petite classe qui contient le mot vide, les langages composes d'une lettre, et qui est close par Union, Produit de concatenation, et Operation etoile. Une expression reguliere denote un tel langage.
  On observe qu'on est tres proche d'un sous langage de notre langage combinatoire de base, avec Union, Produit cartesien, et Sequence. Si les operations sur mots et langages sont non-ambigues, il y a equivalence. Donc la traduction en serie generatrice s'applique.
  Exemple. R = (a.b*)* est une expression nom ambigue qui denote tous les mots commencants par la lettre a. De meme, S = b*.R donne tous les mots. (on voit cela en "scandant" selon les apparitions de la lettre a!) Tout se tient et on retrouve la serie generatrice 1/(1-2z) de tous les mots! Par contre T = (a*.b*)* est ambigue. L'application aveugle des regles ne nous conduit meme plus a une serie entiere!
  En tout cas, si un langage admet une description par expression reguliere non ambigue, on sait en denombrer les elements: cette serie est une fraction rationnelle de forme particuliere obtenue par composition de sommes, produits et quasi-inverses a partir de la variable z et de 1.

  Les monotonies sont une illustration. On s'interesse depuis longtemps aux grandes sequences de chance ou de malchance dans les jeux de hasard. Soit L[k] le langage des mots qui ont moins de k lettres b consecutives. Alors L[k]=(ab<k).(ab<k)*, d'apres la scansion qui precede. ici, b<k=1+b+bb+...+b^{k-1}. D'ou la serie generatrice (1-z^k)/(1-2z+z^(k+1)).
  Knuth (1978) a etudie' ces fraction rationnelles dont les poles dominants s'accumulent en 1/2. Il a montre' notamment ainsi que la longueur de la plus grande monotonie a une esperance log2(n)+O(1). Ceci est en accord une propriete' vue dans le cours de Steyaert: Presque tous les mots contiennent tous les blocs (facteurs) de taille (1-epsilon)*log2(n). On a un problemem plus specifique mais des resultats plus precis. Par exemple, un mot de longueur 100 contient avec une bonne probabilite' une a ou b-monotonie de longueur 7. Des statisticiens se sont amuses a verifier cette proprie'te' contre-intuitive en isolant avec succes des suites reellement aleatoires de suites pseudoaleatoires inventees par des humains.

  Automates. Que faire face a des expressions ambigues? Un theoreme classique est a la base de la theorie des langages reguliers.

  Theoreme de Kleene-Rabin-Scott. Il y a equivalence de pouvoir descriptif entre: (i) les expressions regulieres; (ii) les automates finis non deterministes; (iii) les automates finis deterministes.
  Ceci entraine alors:
  Theoreme de Chomsky-Schutzenberger. La serie generatrice de tout langage regulier est une fraction rationnelle.
  Preuve: On construit un automate fini deterministe qui reconnait le langage. On a alors un systeme lineaire qui relie le systeme des langages Lj compose's des mots conduisant de l'etat j d'un automate deterministe a l'un des etats finals. La structure de cet automate est transparente, avec une matrice de transition qui correspond aux transitions du graphe de l'automate.

  Exemple. Voir le poly pour la construction a la main d'un automate qui reconnait un motif comme abb.
  Complement de cours (pas fait). Donner le nombre moyen d'occurrences d'un motif w de longueur k dans un mot aleatoire de longueur n. Reponse: (2-2^{1-m})n en examinant l'expression A*wA* qui est ambigue vis-a-vis des mots contenant w, mais "compte" exactement les occurrences.

• Arbres. On considere un (multi)ensemble Omega d'entiers contenant 0. Un Omega-arbre est un arbre dont les degres (sortants) des sommets sont dans Omega. On retrouve les arbres binaires, les arbres generaux, et bien d'autres! L'equation de base pour la serie generatrice est: Y(z)=z phi(Y(z)), ou` phi est associe a Omega (c'en est une sorte de serie "caracteristique").
  Donc les Omega-arbres consuisent a des series definies implicitement. On utilise alors le theoreme d'inversion de Lagrange (Voir la formule en (F1) ci-dessous.)
  Theoreme de Lagrange. Inverser une serie (comme phi) se relie a developper certaines puissances de la serie et en extraire les coefficients.
  Ceci donne une formule pour le nombre de Omega-arbres de taille n. On observe que ceci donne une formule de sommation (r-1)-uple si Omega comporte r elements. Par exemple une sommation simple pour les arbres unaiare-binaires, ce qui definit les nombres de Motzkin. On denombre aussi les arbres kaires selon la taille, ce qui generalise les nombres de Catalan.
  Exercice. Les nombres de Motzkin Mn croissent en a peu pres 3^n. Dans un sens (majoration), on a 3^n/n par Lagrange. (on a aussi la majoration directe en 3^n par les codes "polonais", c-a-d de Lukasiewicz.) Dans l'autre sens, on doit se servir du fait que la serie M(z) a rayon d'analyticite' egal a 1/3 exactement. Or, pour une fonction analytique a l'origine: Rayon d'analyticite' et rayon de convergence coincident! donc on a pour tout epsilon: Mn>(3-eps)^n infiniment souvent.
  Qui suis-je? Autre exemple le probleme de Schroeder (1843) des parenthesages generalises. On a n variables. De combien de facon peut-on les parentheser? Ici, une parenthese peut enclore un nombre arbitraire d'elements j>=2. Figure. Les 11 parenthesages de 4 lettres.
  Voir sur les pages de Richard Stanley du MIT cette interessante etude qui montre que ces nombres
  1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049
  remontent en fait a Hipparque de Rhodes (180BC, 125BC), lequel connaissait deja la valeur 103049. Figure: Un arbre de Schroeder est un arbre general dont les sommets internes ont degre au moins 2. La taille est le nombre de feuilles.
  L'equation symbolique est S=z+S^2/(1-S). L'exemple montre qu'il faut faire attention a ce que l'on compte (les feuilles, ici). Comparer a l'equation T=z*(1+T^2/(1-T)) qui compterait les memes objets mais selon une autre notion de taille (= le nombre total de sommets).

• Fonctions analytiques. La preuve la plus simple du theoreme de Lagrange repose sur un calcul d'integrale dans le plan complexe exprimant les coefficients d'une fonction par une integrale de Cauchy. (il suffit alors d'un simple changement de variable qui prend la fonction inconnue comme variable de base!) On fait un bref "rappel" a cette occasion. Ca ne sera pas perdu car ces notions sont a la bse de l'analyse asymptotique des structures combinatoires...

  Definition. Soit D un ouvert simplement connexe du plan. Une fonction de C dans C est dite

  • Analytique: elle se developpe en serie convergente en tout point.
  • Holomorphe ou Complexe differentiable: elle est derivable en tout point, c-a-d, (f(z+h)-f(z))/h existe et est independant de h.
  • "Conservative": son integrale le long de tout lacet est nulle. (Cette terminologie inventee dans le feu de l'action est non standard!)
  Le theoreme de base de la theorie affirme l'equivalence de ces notions. On a aussi le theoreme des residus qui se specialise a la formule integrale des coefficients.

• Formules. La formule d'inversion de Lagrange (F1) et la formule integrale des coefficients de Cauchy (F2) [ou` gamma est une boucle autour de l'origine dans le domaine d'analycite' de f.)

Cours 4 [13 Janvier 1999]

On passe maintenant a des objets combinatoires un peu plus riches, les structures etiquetees. Imaginons des boules de billard (americain!) numerotees par des entiers distincts 1,2,3... et agencees selon certaines regles. Un jeu de regles definit une classe de structures combinatoires etiquetees. (Plus serieusement, on considere des graphes dont les sommets sont numerotes par des entiers distincts.) La taille est le nombre de petites boules, comme d'habitude. Le denombrement se fait alors par series generatrices exponentielles, (EGF) ce qui signifie qu'on utilise z^n/n! comme base des series generatrices.


Exemples.

• Les permutations, si on les ecrit lineairement correspondent aux graphes lineaires etiquetes. L'egf vaut 1/(1-z).
• Les urnes correspondent aux graphes totalement deconnectes, ou encore aux graphes lineaires avec la contrainte supplementaire que les etiquettes sont tries croissantes. L'egf vaut exp(z).
• Les arbres (planaires, enracines) peuvent etre revus sous l'angle etiquete. Combien y en a t-il? On observe que l'arbre planaire est rigidement implante' dans la plan. On a un parcours canonique (par ex., ordre prefixe). Donc, dans ce cas tres particulier, le nombre d'objets etiquetes vaut n! multiplie par le nombre d'objets correspondant non etiquetes.
  Si on s'interesse aux arbres non planaires, toujours etiquetes, Cayley (du theoreme de Cayley-Hamilton) a montre que le nombre est n^(n-1). On aura l'occasion de revenir la dessus.
• Les graphes etiquetes: Il y en a 2^(n*(n-1)/2) car on est libre du choix de chacune des n(n-1)/2 aretes potentielles. La serie generatrice meme exponentielle a rayon de convergence nul. Ca n'empeche pas de faire des calculs algebriques de series. On montre par exemple a partir de ces manipulations que presque tout graphe est connexe. Notons que le modele des graphes uniformes est un cas particulier du modele fameux G[n,p] ou l'on choisit chaque arete avec probabilite' p: prendre p=1/2. On est bien au dela du seuil de connectivite' (p=log(n)/n): voir les autres cours du DEA...
• Les permutations circulaires sont comptees par (n-1)!. On esquisse la preuve qui est une correspondance multivoque: perm-circ <- -> perm laquelle est uniforme (il y a n ecritures lineaires d'une meme perm circ.)
• Surjections et partitions d'ensembles. Il y a k^n applications de [1..n] dans [1..k]. Combien sont surjectives? On s'esaye en exercice a denombrer les surjections. Pour k=1, 2, 3, on trouve 1^n, 2^n-2, 3^n-3*2^n+3 On pourrait pousser le raisonnement, mais ca se complique: c'est le principe dit "d'inclusion-exclusion". Par serie generatrice exponentielle, on observe que le produit de series exponentielles correspond sur les coefficients a une convolution binomiale (ou multinomiale). ceci donne un truc pour etablir que l'EGF des k-surjections vaut (e^z-1)^k On retrouve les resulats precedents et les coefficients des puissances (k-j)^n sont des binomiaux. On se prepare a la suite en observant qu'une k-surjection est determinee par la donnees de k urnes non-vides ainsi que d'une maniere de repartir les etiquettes entre ces urnes.

  Partitions d'ensembles. De combien de facons partionner n objets en k classes non vides? Par exemple S[3,5]=25. Cela definit les nombres de Stirling de 2eme espece (ou "Stirling partition numbers"). (La notice biographique de Stirling, l'homme de sa formule, est ici.) On observe que le nombre de k-partitions est au nombre de k-surjections dans le rapport 1/k!, comme on aurait dit au XVIIIeme siecle. Donc, on sait faire.

  Surjections et partitions ou k n'est plus fixe s'obtiennent en sommant les EGF correspondant a chaque cas k. On peut exploiter ces resultats en sommant et en developpant les coefficients. On obtient les nombres de Bell, sommes de nombres de Stirling, pour les partitions d'ensembles.

  Courez-voir ici ce qu'est une partition d'ensemble!
  

  1
  2
  3
  4
  5
  6
  7
  8
  	1	2	3	4	5	6	7	8

• Alignements et cycles dans les permutations. Les permutations circulaires sont en nombre (n-1)!. Combien de perms ont k cycles? (C'est Knuth qui a propose' pour epargner les arbres qu'on dise "perm" au lieu de "permutation"; ca n'a pas eu un succes fou!) On suit une demarche analogue: on introduit les alignements (terminologie maison) ou les cycles sont ranges les uns a la suite des autres dans les tiroirs d'une armoire. En vertu du raisonnement precedent, les k-alignements se comptent par EGF par une puissance k-eme de l'EGF des permutaions circulaires.
  On divise ensuite par k! pour obtenir le denombrement des permutatiosn a k cycles. Ca donne lieu aux nombre de Stirling de 1ere espece (ou Stirling cycle numbers). On peut calculer leur serie generatrice double qui s'avere valoir tout simplement (1-z)^(-u). On retrouve alors le denombrement des maxima vu au cours #1. On en deduit qu'une perm aleatoire de taille n a en moyenne H_n [nombre harmonique: 1+1/2+...+1/n] cycles.
  Exercice: Trouver une correspondance directe entre cycles et maxima.(Foata). Suggestion: definir la notion de leader de cycle et lister les decompositions en cycles de maniere adequate. [Si on s'y est bien pris, les leaders deviennent des maxima ou records.]

• Le produit etiquete'. Voir le poly. Tout repose sur le produit etiquete (ou "partitionnel", Foata 1975). L'idee est que le produit cartesien usuel donne lieu a des objets (des paires) qui ne sont pas bien etiquetees; par exemple, on a 1 qui apparait en deux endroits, c'est mal! Alors, on se casse pas le trognon, et on decide tout simplement de re-etiqueter de maniere coherente et de toutes les facons possibles. On definit ensuite Sequences, Cycles, et Ensembles.
  Theoreme fondamental. Union (disjointe), produit (etiquete), sequence, cycles, et ensemble se traduisent en EGF par +, x, 1/(1-.), log1/(1-.), exp(.). On a un dictionnaire plus simple que dans le cas non-etiquete'.
  Pour les k-sequences, k-cycles, k-ensembles de A, la traduction est A^k, A^k/k, A^k/k!.
  
  Question: pourquoi les problemes de denombrement etiquete versus non-etiquete' sont-ils distincts? Reponse: a chaque structure non etiquete'e correspond entre 1 et n! structures etiquetees. Ca depend des "symetries" des objets. En general, c'est pas trivial, c-a-d, ce nombre de symetries depend de l'onjet et est variable. Seulement dans certains cas simples (arbres planaires) a-t-on une relation "uniforme" et les deux problemes etiquete-non etiquete sont equivalents. Pompeusement, on peut parler de groupes d'automorphismes, blabla.

  On a donc un nouveau dictionnaire et on en discute l'applicabilite'. On conclut par quelques exemples faits sous forme d'exercices commentes:

  • Graphe connexes; leur serie generatrice est le log de la serie generatrice de tous les graphes. On peut meme extraire de l'information asymptotique de la traduction de cette formule sur les coefficients, ce, malgre le caractere divergent des series. (Il existe en fait une analyse des series divergentes bien qu'Abel ait declare' que c'etait une invention du diable!) Qui suis-je?
  • Derangements: il y a a peu pres n!*exp(-1) derangements, c-a-d, permutations sans points fixes. Au XiXeme siecle: n personnes vont a l'opera et laissent leur chapeau au vestiaire. En sortant du spectacle, chacun prend un chapeau au hasard. Quelle est la probabilite' que personne n'ait alors son chapeau sur la tete? Reponse: Environ, 0.3678794412 = exp(-1).

    Exercice. Justifier les assertions du fragment de texte suivant (ref: Frank Ruskey):

    The number of derangements of length n, d(n) can be computed using the following well-known recurrence relation, n > 2:

    d(n) = (n-1) d(n-1) + (n-1) d(n-2)

    The recurrence relation above can be manipulated so that it takes on the form

    d(n) = n d(n-1) + (-1)ⁿ

    The d(n) numbers are sometimes called the subfactorial or rencontres numbers. The values of d(n) for n=0,1,2,...,10 are 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961. This is sequence A000166(M1937) in Sloane's database of integer sequences.

  • Combien y-a-t-il d'arbres non planaires de hauteur <=2? Reponse une tour de 2 exponentielles. En hauteur quelconque on retrouve l'equation fameuse T=z*e^T qui se resout (se developpe en fait) par Lagrange et donne le resultat de Cayley: le nombre d'arbres [enracines, non planaires, etiquetes] vaut n^(n-1).
  On s'arrete la`. Tout le monde est un peu perplexe. La pratique devrait nous eclairer, j'espere.

Cours 5 [20 Janvier 1999]

• Fin des denombrements etiquetes. On pratique sur pas mal d'exemples. Voir le chapitre II du poly.
• Series generatrices doubles. L'idee est que les schemas combinatoires permettent de prendre en compte de la meme maniere des parametres pourvu qu'ils soient herites additivement vis a vis des constructions qui sont en jeu. L'interet de tout cela est de realiser des analyses en moyenne de ces parametres. Voir le chapitre III du poly.

Cours 6 [3 Fevrier 1999]

• Fonctions analytiques et asymptotique complexe. Dig-ding-dong. Vous avez pris place a bord du chapitre IV du poly! Ce qu'il suffit de retenir, c'est qu'il y a trois notions essentiellement equivalentes:
  • une fonction analytique se developpe au voisinage de tout point en serie entiere (serie de puissances comme on dit plus suggestivement chez les anglais) convergeant localement.
  • une fonction C-differentiable est simplement telle que la limite (f(x+h)-f(x))/h existe en tout point (independante de la facon dont h->0 bien sur!)
  • une fonction "conservative" est d'integrale (curviligne) nulle le long de toute boucle.
  Le THEOREME 0 de la theorie affirme l'equivalence de ces trois notions pour un ouvert simplement connexe (=l'interieur d'une courbe simple). On parle aussi de fonctions holomorphes, terminologie equivalente a la derivabilite'. Ca vient du grec et ca veut dire "forme" (morphe) "totale, complete" (holos): C'est tout un monde mais il ne faut pas s'en faire un. :-) Fig. Une fonction analytique est localement une similitude.
  (Ici transformation par exp(z) de la grille de coins -1-i, +1+i.)
  La notion essentielle pour nous est celle de singularite', c-a-d, un point sur le bord d'un domaine de definition d'une fonction au dela duquel on ne peut pas prolonger la fonction. Par exemple, il suffit que f(z) devienne infinie ou cesse d'etre derivable pour avoir une singularite.
  Exemple. log(1/(1-z)) et sqrt(1-z) sont singulieres en z=1, exp(z) n'a pas du tout de singularites. Fig. Une fonction avec deux singularites (trace du module)
  Les fonctions analytiques possedent de merveilleuses proprietes de cloture: on peut leur faire subir +, -, x, / (a condition de se limiter a des regions ou le denominatuer ne s'annule pas); on peut les deriver et les integer (dans des domaines sans trous!); on peut enfin les composer a loisir et meme les inverser, en faisant juste attention que z=h(y) s'inverse a condition que la derivee h'(y) ne s'annule pas. (Penser au classique theoreme des fonctions implicites!)
• Les fonctions meromorphes, c'est ce qu'on obtient quand on veut reparer les fonctions analytiques a cause des zeros des denominateurs. C'est tout bete, on a un developpement avec juste quelques termes en puissances negatives. Noter que meromorphe vient du grec, on s'en doutait: "forme" ("morphe, on sait deja) "partielle" ("mero") [ce qui, pense Sebastien Desreux qui a fait du Grec a peut-etre a voir avec le merou? :-)]
  Le residu, c'est juste le coefficient de la puissance (z-z0) d'exposant -1.
• On a le
  • Theoreme des residus: Si on integre une fonction meromorphe le long d'un coutour ferme (simple, etc), le tout vaut 2*i*pi (i=sqrt(-1) et pi=3.14) fois la somme des residus des poles a l'interieur.
  Preuve. On fait un peu de chirurgie et on examine ce qu'il se passe autour d'un pole. Les termes en z^m et z^(-m) ont tous des primitives de variation nulle le long d'une boucle, sauf pour ce pauvre z^(-1) qui donne 2*i*pi. Fin de la preuve.

  On commence alors a voir pourquoi on parle de tout ca. On veut acceder aux coefficients de series generatrices (de denombrement, mais peu importe!). Le theoreme des residus implique quais immedaitement que

  • Formule integrale des coefficients. le coeff de z^n dans f(z) vaut 1/(2*i*pi) [encore lui] fois l'integrale de f(z)/z^(n+1) prise le long d'un contour simple autour de l'origine orinete dans le bon sens (+).
  On n'a pas oublie' (?) que c'est grace a ce theoreme qu'on montre le plus facilement du monde en trois ou quatre lignes le theoreme d'inversion de Lagrange.: inverser et developper se ramene a multiplier et developper!

  Philosophiquement, ces deux theoremes dus a Cauchy sont fondamentaux. Il ramenent une caracteristqiue globale d'un objet analytique (son integrale sur un contour) a une caracteristique locale (le residu en un point). On peut aller pecher ailleurs les infos! L'\exemple du calcul de int(1/(1+z^2),z=-infty..+infty) illustre ce propos: on a juste besoin de developper un coup en z=+i. Exercice: calculer l'integrale avec z^8 qui remplace z^2. Meme Maple sait faire... et il le fait comme cela.

  On continue et on montre deux choses:

  • Le "rayon de singularite'" (on part de 0 en faisant des ronds et on s'arrete quand ca coince) et rayon de convergence coincident,
  • Donc on connait l'ordre de grandeur exponentiel des coefficients d'une serie. C'est R^(-n) ou R est la distance de l'origine a la singularite la plus proche. Estimer les coefficients d'une fonction/serie, c'est dans un permier temps, partir a la chasse aux singularites, notamment celles qui sont les plus proches de l'origine et qu'on appelle aussi "dominantes".
  En plus, une variante due a Pringsheim nous aide: pour une serie a coefficients positifs, l'une des singularites dominantes est situee sur l'axe reel positif.

  Sur cette base, on part donc a la chasse aux singularites et on on trouve en exercice l'ordre exponentiel des coefficients lies aux denombrements suivants:

  • les compositions d'entiers (tout se tient);
  • les derangements et leurs generalises (tous les cycles de longueur >m);
  • les surjections;
  • les alignements;
  • les arbres unaires-binaires (0-1-2) dits de Motzkin (par fonctions implicites ou par la formule close de la serie generatrice en sqrt((1+z)(1-3z))); pour les arbres 0-1-2 ou on aura une equation algebrique a resoudre.
  Certains de ces exemples peuvent s'ameliorer: on peut appliquer une technique de soustraction de singularites.
  • On maitrise bien les fractions rationnelles avec un dictionnaire:
    • Pole en a ==> contribution en a^(-n);
    • multiplicite=k ==> polynome de degre k-1 en n.
  • Si on soustrait d'une fonction meromorphe la "partie singuliere" qui collecte les contributions aux poles [c'est une fracton rationnelle], ce qui reste est analytique loin et donc a des coefficients tout petits. On a donc le meme genre de resultat que dans le cas des fractions rationnelles; c'est juste qu'on a un terme d'erreur en O(R^(-n)) si on a soustrait tous les poles jusqu'a |z|=R.
  On reprend quelques exemples dont les surjections.

  On se prepare a la fois suivante: presque toutes les fonctions obtenues par les methodes symboliques ont des singularites qui s'analysent et on peut effectivement en trouver l'asymptotique des coefficients. On annonce les deux theoremes principaux qui viendront, apres avoir defini la fonction Gamma:

  • coeff[z^n](1-z)^(-a) est asymptotique a n^(a-1)/Gamma(a);
  • Si f(z) est un grand-O de (1-z)^(-a) alors son coefficient est un grand-O de n^(a-1). (Il y a toutefois une petite condition de Camembert!)
  Ceci generalise ce qu'on a vu des fonctions meromorphes a une tres large classe de fonctions... Cliquer sur l'image pour une conference de presentation du sujet!