Abonnez-vous à Universalis pour 1 euro

COMBINATOIRE ANALYSE

Article modifié le

Fonctions génératrices

On a vu qu'on ne savait pas trouver de formule explicite donnant le nombre de surjections d'un ensemble de n éléments sur un ensemble de p éléments, mais on peut faire apparaître ces nombres comme coefficients d'une série. La fonction de deux variables f (t, u) = exp (t(exp u − 1)) se développe en série sous la forme :

le nombre de Stirling Spn apparaît, divisé par n !, comme coefficient du monôme untp. On dit que la fonction f (t, u) est la fonction génératrice des nombres Spn/n ! ; puisqu'on connaît l'expression de cette fonction génératrice, on pourra résoudre d'autres problèmes combinatoires ou trouver des fonctions génératrices d'autres nombres liés aux nombres de Stirling.

Supposons donné un anneau A commutatif et ayant un élément unité. On appelle série formelle à coefficients dans A et en une indéterminée u, une somme symbolique infinie :

où les an sont dans A (n ≥ 0). On dit que an est le coefficient de un dans cette série. La somme et le produit de deux séries formelles sont définis de manière à respecter les règles usuelles de distributivité pour le produit de deux séries infinies et le calcul sur les puissances unum = un+m (cf. anneaux et algèbres, chap. 2) : si on a deux séries :
leur somme est la série :
et leur produit est donné par :
où l'on a : cn = a0bn + a1bn-1 +...+ anb0 pour tout n ≥ 0. Si U est une telle série sans terme constant, c'est-à-dire telle que le coefficient de u0 soit nul, on appelle exponentielle de U la série :

En d'autres termes, exp U est la série formelle dont le coefficient de un est le coefficient de un dans la somme (finie) :

Une suite infinie d'indéterminées t = (t1, t2, ...) étant donnée, nous prenons pour anneau A l'anneau des polynômes à coefficients rationnels dont les indéterminées sont prises dans la suite t. Posons alors :

son terme constant est nul, on peut donc prendre son exponentielle, qu'on peut écrire :

Il est facile de voir que an est un polynôme de degré n en les n variables t1, t2, ..., tn, où n ≥ 1. Plus précisément, on a :

où la sommation est étendue à toutes les suites (m1, m2, ..., mn) de n entiers positifs satisfaisant à 1m1 + 2m2 + ... + nmn = n. Le coefficient du monôme :
dans a est donc égal à :

On peut vérifier que ce nombre est le nombre de partitions de type (m1, m2, ..., mn), c'est-à-dire de partitions de l'ensemble X = {1, 2, ..., n} en m1 + m2 + ... + mn sous-ensembles non vides, parmi lesquels m1 sont de cardinal 1, m2 de cardinal 2, ..., mn de cardinal n.

Cette interprétation nous permet de retrouver le nombre de partitions de l'ensemble X = {1, 2, ..., n} en p sous-ensembles non vides. En effet, le nombre de sous-ensembles non vides d'une partition de type (m1, m2, ..., mn) est p = m1 + m2 + ... + mn. Si donc l'on pose t1 = t2 = ... = tn = t dans l'expression (1), le coefficient de tp dans le second membre va être égal au nombre de partitions de X en p sous-ensembles non vides, soit :

Par conséquent la fonction génératrice des nombres de Stirling de seconde espèce est donnée par :

Par exemple, pour trouver le nombre de surjections d'un ensemble de n éléments sur un ensemble de p éléments (p ≤ n), on détermine le coefficient c de untp dans le développement de exp (t(exp u − 1)) et le nombre cherché est égal à cn ! p !.

La suite de cet article est accessible aux abonnés

  • Des contenus variés, complets et fiables
  • Accessible sur tous les écrans
  • Pas de publicité

Découvrez nos offres

Déjà abonné ? Se connecter

Écrit par

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Médias

Nombres de Stirling - crédits : Encyclopædia Universalis France

Nombres de Stirling

Encyclopædia Universalis France

Arbre de sept sommets - crédits : Encyclopædia Universalis France

Arbre de sept sommets

Encyclopædia Universalis France

Autres références

  • ALGORITHMIQUE

    • Écrit par et
    • 6 654 mots
    • 3 médias
    Arbre binaire - crédits : Encyclopædia Universalis France
    Entrentdans la catégorie des problèmes combinatoires, en informatique, les problèmes qui consistent à déterminer, pour une donnée d, si est satisfaite une condition :
    où : (a) S(d) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de ...

  • ERDÖS PAUL (1913-1996)

    • Écrit par
    • 945 mots

    Mathématicien brillant et hors du commun, lauréat du prix Wolf en 1983.

    Né le 26 mars 1913 à Budapest et décédé le 20 septembre 1996 à Varsovie, Paul Erdös fut un enfant prodige et, à l'âge de quatre ans, il savait déjà compter avec des nombres de trois chiffres et avait redécouvert les nombres négatifs....

  • FERMAT PIERRE DE (1601-1665)

    • Écrit par , et
    • 4 103 mots
    Dans le domaine voisin de l'analyse combinatoire, il avait, avant 1636, bien avant Pascal, donné la formule multiplicative du nombre des combinaisons :

  • ISLAM (La civilisation islamique) - Les mathématiques et les autres sciences

    • Écrit par , et
    • 22 278 mots
    • 2 médias
    L’observatoire astronomique de Constantinople - crédits : Sonia Halliday Photo Library/ Alamy/ Hemis
    L'activitécombinatoire a commencé par se manifester comme telle, mais d'une manière dispersée, chez les linguistes, d'une part, et chez les algébristes, d'autre part. Ce n'est que plus tard que se fera la liaison entre les deux courants, et que l'analyse combinatoire se présentera comme un instrument...
  • Afficher les 9 références

Voir aussi

Abonnez-vous à Universalis pour 1 euro

Rejoignez-nous

Inscrivez-vous à notre newsletter