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 202 − 1 Analyse combinatoire approfondie par Louis COMTET Agrégé de mathématiques Docteur ès sciences mathématiques Maître de conférences à l’université de Paris-Sud a notion de partition d’ensemble est exactement celle de relation d’équiva- lence, bien connue de tous. Ici, dans le cas d’un ensemble N fini à n éléments, le nombre des partitions de N en k blocs (parties non vides), ou, si l’on préfère le nombre de relations d’équivalence à k classes sur N, noté S(n,k), n’est autre que le célèbre nombre de Stirling de seconde espèce. Ces nombres S(n,k) intervien- nent d’ailleurs un peu partout, en algèbre, en analyse, en probabilités, en statis- tique… Il en sera fait ici une étude particulièrement détaillée. La notion de partition d’un entier n est de nature plus théorique. C’est, si l’on peut dire, une gigantesque généralisation du fameux problème de l’échange de monnaie : de combien de manières peut-on réaliser un montant de n francs avec des pièces de 1, 2 et 5 francs ? Sans les séries entières, on n’arriverait à rien, comme Euler l’a montré. Cette théorie, dans sa généralité, touche au moins autant à l’arithmétique qu’à la combinatoire, dernier aspect qui sera seul ici retenu. Pour terminer, la notion de permutation (d’un ensemble fini) est reprise avec force détails, et donne l’occasion d’introduire des nombres combinatoirement aussi fondamentaux que les nombres de Stirling de première espèce s(n,k), les nombres eulériens A(n,k) qui comptent les permutations de par montées, les nombres tangents a2n+1, coefficients de Taylor du développement en série entière de : , 1. Partitions.................................................................................................... AF 202 – 2 1.1 Partitions d’ensemble et nombres de Stirling de seconde espèce. Définition combinatoire. Formule explicite............................................... — 2 1.2 Récurrence triangulaire, triangle de Stirling et sa géométrie.................. — 3 1.3 Définition algébrique des nombres de Stirling de seconde espèce........ — 5 1.4 Définitions analytiques des nombres de Stirling de seconde espèce..... — 6 1.5 Nombre total de partitions d’un ensemble ou nombre de Bell............... — 7 1.6 Partitions d’entiers....................................................................................... — 8 1.6.1 Partitions d’entiers : définitions et généralités................................. — 8 1.6.2 Diagrammes de Ferrer ....................................................................... — 8 1.6.3 Partitions d’entiers : fonctions génératrices..................................... — 9 1.7 Dénumérant ................................................................................................. — 9 1.7.1 Échange de monnaie avec des pièces de 1, 2, 5 francs................... — 9 1.7.2 Que dire du dénumérant en général ?.............................................. — 10 2. Permutations............................................................................................. — 11 2.1 Le groupe symétrique ................................................................................. — 11 2.2 Permutations par nombre de cycles et nombres de Stirling de première espèce................................................................... — 13 2.3 Autres propriétés des nombres de Stirling de première espèce............. — 14 2.4 Montées et nombres eulériens................................................................... — 15 2.5 Permutations alternantes............................................................................ — 18 2.6 Nombres tangents....................................................................................... — 19 L �1 n� , x ( ) tan a 2n 1 + x 2n 1 + 2n 1 + ( )! ------------------------ n 0 �∑ =