COMBINATOIRE ANALYSE
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 :
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 :
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 :
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 :
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éjà abonné ? Se connecter
Écrit par
- Dominique FOATA : professeur à la faculté des sciences de Strasbourg.
Classification
Médias
Nombres de Stirling
Encyclopædia Universalis France
Arbre de sept sommets
Encyclopædia Universalis France
Autres références
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD et Philippe FLAJOLET
- 6 652 mots
- 3 médias
Entrent dans 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 Jean-Louis NICOLAS
- 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 Encyclopædia Universalis , Catherine GOLDSTEIN et Jean ITARD
- 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 Georges C. ANAWATI , Encyclopædia Universalis et Roshdi RASHED
- 22 273 mots
- 2 médias
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
