Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur, traité Sciences fondamentales AF 200 − 1 Analyse combinatoire élémentaire par Louis COMTET Agrégé de Mathématiques Docteur ès Sciences Mathématiques Maître de conférences à l’Université de Paris-Sud ’analyse combinatoire est une branche des mathématiques qui, sur des ensembles finis, traite de problèmes de dénombrements (ou comptages), d’énumérations (ou listages) et d’estimations (encadrements et asymptotisme). Cette vision, certes assez réductrice, est cependant très riche. Dans le foison- nement des sujets dits de nature combinatoire, on a dû, dans cet article, faire un choix, et exclure certaines théories voisines, et importantes, comme celle des graphes, par exemple. Les principales applications du sujet se présentent évi- demment en calcul des probabilités et en statistique. Néanmoins, il ne faut pas dissimuler que bien des problèmes traditionnels de l’analyse, de l’algèbre et de la géométrie sont d’essence combinatoire, et évidemment, plus encore, ceux récemment posés par l’informatique. Cette science de l’Analyse combinatoire est, dit-on en France, née avec les tra- vaux de Pascal qui, confronté à des questions de probabilités dans les jeux, 1. Principes et premières applications................................................... AF 200 – 3 1.1 Principes fondateurs de la Combinatoire .................................................. — 3 1.2 Formule du crible ou principe d’inclusion et exclusion ........................... — 4 1.3 Première application : formule de Legendre............................................. — 5 1.4 Deuxième application : nombre de diviseurs d’un entier ........................ — 6 1.5 Troisième application : indicatrice d’Euler ................................................ — 7 1.6 Graphes : vocabulaire ................................................................................. — 8 1.7 Quatrième application : formule de Cayley pour le nombre d’arbres étiquetés........................................................................................ — 8 2. Combinaisons............................................................................................ — 9 2.1 Combinaisons, arrangements, permutations : définitions....................... — 9 2.2 Arrangements et permutations : leur nombre .......................................... — 10 2.3 Combinaisons : leur nombre ...................................................................... — 11 2.4 Combinaisons : les notations ..................................................................... — 12 2.5 Formule du binôme (de Newton) ou identité binomiale.......................... — 13 2.6 Coefficients binomiaux et calcul des différences...................................... — 13 2.7 Formule de Stirling...................................................................................... — 14 2.8 Coefficient binomial central........................................................................ — 16 3. Triangle de Pascal.................................................................................... — 17 3.1 Récurrence triangulaire............................................................................... — 17 3.2 Relations verticales...................................................................................... — 18 3.3 Relations horizontales................................................................................. — 19 3.4 Courbe limite de Laplace-Gauss................................................................. — 20 3.5 Arithmétique binomiale .............................................................................. — 21 3.6 Matrice de Pascal, inversion et puissances............................................... — 22 3.7 Problème des rencontres............................................................................ — 22 3.8 Surjections et nombres de Stirling de seconde espèce ........................... — 24 3.9 Sommes des puissances impaires des entiers dans ..................... — 24 Références bibliographiques ......................................................................... — 26 �1 n� , L