Un multiensemble (parfois appelé sac, de l'anglais bag utilisé comme synonyme de multiset) est une sorte d'ensemble dans lequel chaque élément peut apparaître plusieurs fois. C'est une généralisation de la notion d'ensemble : un ensemble ordinaire est un multiensemble dans lequel chaque élément apparaît au plus une seule fois ; ce qu'impose, pour les ensembles usuels, l'axiome d'extensionnalité.

On nomme multiplicité d'un élément donné le nombre de fois où il apparaît. Un multiensemble est fini si la somme des multiplicités de ses éléments est finie, ou plus simplement s'il n'a qu'un nombre fini d'éléments (les multiplicités étant toujours finies).

Définition formelle

modifier

Formellement, un multiensemble est un couple    est un ensemble appelé support et   une fonction de   dans l'ensemble des entiers naturels, appelée multiplicité (notée  ). Dans le multiensemble  , l'élément   apparaît   fois.

Un multiensemble fini se note en utilisant des accolades doubles   qui encadrent les éléments, ayant une multiplicité strictement positive, répétés autant de fois que celle-ci. Ainsi   représente le multiensemble    est la fonction telle que  ,  ,   et  .

On peut également voir un multiensemble comme une liste commutative, c'est-à-dire dont on peut permuter les éléments, autrement dit comme un élément du monoïde commutatif libre sur A.

Une expression   peut donc représenter des multiensembles distincts, comme   et   (avec  ;  ). On peut contourner cette difficulté en introduisant une relation d'égalité ad hoc, ou mieux en exigeant que la multiplicité d'un élément du support soit non nulle. Pour éviter cette ambiguïté, on prend comme référence un ensemble de base   sur lequel on considère les multiensembles, ainsi si   est donné, les multiensembles finis sont les applications  , nulles partout sauf sur un sous-ensemble fini de  , ainsi   est défini sans ambiguïté, comme la fonction de   vers   qui vaut   partout sauf en   où elle vaut  .

Le cardinal d'un multiensemble est la somme des multiplicités de ses éléments.

Ordre multiensemble

modifier

Si on munit   d'un ordre  , il est possible de définir un ordre entre les multiensembles de support   que l'on appelle ordre multiensemble :   est supérieur à   pour l'ordre multiensemble si   peut s'obtenir à partir de   en remplaçant chaque élément de   par un nombre quelconque d'éléments plus petits.

Exemple : si on ordonne les lettres dans l'ordre alphabétique ( ), alors   est strictement plus petit que  .

Si on suppose que l'ordre sur   est bien fondé, alors l'ordre multiensemble ainsi défini l'est aussi[1].

Dénombrement des multiensembles

modifier

Le nombre de multiensembles de cardinal k (la somme des multiplicités de chaque élément), avec des éléments pris dans un ensemble fini de cardinal n, est parfois appelé le coefficient de multiensemble ; ce nombre est écrit par certains auteurs comme  , une notation qui est censée ressembler à celle des coefficients binomiaux[2]. Tout comme la loi binomiale implique des coefficients binomiaux, il existe une loi binomiale négative dans laquelle les coefficients de multiensemble apparaissent (ces coefficients ne doivent pas être confondus avec les coefficients multinomiaux qui apparaissent dans la loi multinomiale).

La valeur des coefficients de multiensemble peut être donnée explicitement par

 
où la deuxième expression est un coefficient binomial ; de nombreux auteurs évitent en fait une notation distincte et écrivent simplement des coefficients binomiaux. Ainsi, le nombre de tels multiensembles est le même que le nombre de sous-ensembles de cardinal k d'un ensemble de cardinal n + k − 1. L'analogie avec les coefficients binomiaux peut être soulignée en écrivant le numérateur dans l'expression ci-dessus comme une puissance factorielle montante :  pour correspondre à l'expression des coefficients binomiaux utilisant une puissance factorielle descendante :  La figure de droite montre une bijection entre les sous-ensembles à 3 éléments d'un ensemble à 7 éléments et les multiensembles de cardinal 3 provenant d'un ensemble à 5 éléments, ce qui illustre que   Cette bijection associe par exemple le sous-ensemble {1,4,5} au multiensemble {{a,c,c}} = (1a, 0b, 2c, 0d, 0e).

Une façon simple de prouver cette égalité entre coefficients de multiensemble et coefficients binomiaux consiste à représenter les multiensembles par une série d'étoiles séparés par des barres : le multiensemble (6 a, 2 b, 3 c, 7 d) est noté   et (18 b) = (0 a, 18 b, 0 c, 0 d) est noté  .

Ce multiensemble de cardinal k = 18 est composé d'éléments d'un ensemble de cardinal n = 4. Le nombre de caractères incluant à la fois des étoiles et des lignes verticales utilisés dans cette notation est 18 + 4 − 1. Le nombre de lignes verticales est 4 − 1. Le nombre de multiensembles de cardinal 18 est alors le nombre de façons d'arranger les 4 − 1 lignes verticales parmi les 18 + 4 − 1 caractères, et est donc le nombre de sous-ensembles de cardinal 4 − 1 d'un ensemble de cardinal 18 + 4 − 1. C'est donc bien que  De la relation entre les coefficients binomiaux et les coefficients de multiensemble, il s'ensuit que le nombre de multiensembles de cardinal k dans un ensemble de cardinal n peut être écrit   (en utilisant la définition des coefficients binomiaux négatifs) ; de plus,  

Relation de récurrence

modifier

Une relation de récurrence pour les coefficients de multiensemble est la suivante :  avec   La récurrence ci-dessus peut être interprétée comme suit. Soit   l'ensemble support. Il y a toujours exactement un multiensemble (vide) de taille 0, et si n = 0 il n'y a pas de multiensembles plus grands, ce qui donne les conditions initiales.

Dans le cas où n, k > 0. Un multiensemble de cardinal k formé d'éléments de [n] pourrait ou non contenir un quelconque élément m. S'il apparaît, alors en enlevant m une fois, il reste un multiensemble de cardinal k − 1 d'éléments de [n], et chaque multiensemble de cette forme peut apparaître, ce qui donne un total de   possibilités. Si m n'apparaît pas, alors le multiensemble original est égal à un multiensemble de cardinal k formé d'éléments de l'ensemble [n] - m, que l'on peut identifier à [n − 1] ; il en existe donc  

Ainsi,  

Séries génératrices

modifier

La série génératrice des coefficients de multiensemble est très simple :   Comme les multiensembles sont en bijection avec les monômes de l'anneau des polynômes  ,   est aussi le nombre de monômes en n indéterminées de degré d . Ainsi, la série ci-dessus est également la série de Hilbert (en) de cet anneau.

Comme   est un polynôme en n, lui et la série génératrice sont en fait bien définis pour toute valeur complexe de n.

Généralisation et lien avec la série binomiale négative

modifier

La formule par factorielle montante permet d'étendre la définition des coefficients de multiensemble à un α arbitraire (négatif, réel, ou complexe) :

 
Avec cette définition, on obtient une généralisation de la formule binomiale négative (avec l'une des variables fixée à 1), ce qui justifie de noter   les coefficients binomiaux négatifs :  

Cette série de Taylor converge pour tous les nombres complexes α et X avec |X | < 1. Elle peut aussi être interprétée comme une identité formelle en X, et elle peut effectivement servir de définition des puissances arbitraires de séries ayant un coefficient constant égal à 1 ;'avec cette définition, toutes les identités attendues pour l'exponentiation sont valides, notamment   des formules telles que celles-ci peuvent être utilisées pour obtenirr des identités pour les coefficients de multisensemble. Si α est un entier négatif n, alors tous les termes avec k > −n sont nuls, et la série infinie devient une somme finie.

Notes et références

modifier
  1. [PDF] Un article de Coupet-Grimal et Delobel.
  2. Elle est utilisée par exemple par Richard Peter Stanley dans (en) Enumerative Combinatorics, vol. 1, Cambridge University Press, (ISBN 0-521-55309-1, lire en ligne)

Voir aussi

modifier

Articles connexes

modifier

Bibliographie

modifier

(en) Wayne D. Blizard, « The development of multiset theory », Modern Logic, vol. 1, no 4,‎ , p. 319-352 (lire en ligne)