2. 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 S
pn 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 S
pn/
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 :
… pour nos abonnés, l'article se prolonge sur 8 pages…
