Multiensemble

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

Formellement, un multiensemble est un couple ${\displaystyle (A,m)}$ où ${\displaystyle A}$ est un ensemble appelé support et ${\displaystyle m}$ une fonction de ${\displaystyle A}$ dans l'ensemble des entiers naturels, appelée multiplicité (notée ${\displaystyle m}$). Dans le multiensemble ${\displaystyle (A,m)}$, l'élément ${\displaystyle x}$ apparaît ${\displaystyle m(x)}$ fois.

Un multiensemble fini se note en utilisant des accolades doubles ${\displaystyle \{\!\!\{\ldots \}\!\!\}}$ qui encadrent les éléments, ayant une multiplicité strictement positive, répétés autant de fois que celle-ci. Ainsi ${\displaystyle \{\!\!\{a,b,a,b,b,d\}\!\!\}}$ représente le multiensemble ${\displaystyle (\{a,b,c,d\},m)}$ où ${\displaystyle m}$ est la fonction telle que ${\displaystyle m(a)=2}$, ${\displaystyle m(b)=3}$, ${\displaystyle m(c)=0}$ et ${\displaystyle m(d)=1}$.

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 ${\displaystyle \{\!\!\{a\}\!\!\}}$ peut donc représenter des multiensembles distincts, comme ${\displaystyle (\{a\},m)}$ et ${\displaystyle (\{a,b\},m')}$ (avec ${\displaystyle m(a)=m'(a)=1}$; ${\displaystyle m'(b)=0}$). 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 ${\displaystyle M}$ sur lequel on considère les multiensembles, ainsi si ${\displaystyle M}$ est donné, les multiensembles finis sont les applications ${\displaystyle M\rightarrow \mathbb {N} }$, nulles partout sauf sur un sous-ensemble fini de ${\displaystyle M}$, ainsi ${\displaystyle \{\!\!\{a\}\!\!\}}$ est défini sans ambiguïté, comme la fonction de ${\displaystyle M}$ vers ${\displaystyle \mathbb {N} }$ qui vaut ${\displaystyle 0}$ partout sauf en ${\displaystyle a}$ où elle vaut ${\displaystyle 1}$.

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

Ordre multiensemble

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

Exemple : si on ordonne les lettres dans l'ordre alphabétique (${\displaystyle a<b<c<d}$), alors ${\displaystyle \{\!\!\{a,a,c,d\}\!\!\}}$ est strictement plus petit que ${\displaystyle \{\!\!\{b,d,d\}\!\!\}}$.

Si on suppose que l'ordre sur ${\displaystyle A}$ est bien fondé, alors l'ordre multiensemble ainsi défini l'est aussi[1].

Dénombrement des multiensembles

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 ${\displaystyle \left(\!\!{n \choose k}\!\!\right)}$, 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$${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={n+k-1 \choose n-1}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},}$$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 :${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},}$ pour correspondre à l'expression des coefficients binomiaux utilisant une puissance factorielle descendante :${\displaystyle {n \choose k}={n^{\underline {k}} \over k!}.}$ 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 ${\displaystyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right).}$ 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é ${\displaystyle {\star }{\star }{\star }{\star }{\star }{\star }\vert {\star }{\star }\vert {\star }{\star }{\star }\vert {\star }{\star }{\star }{\star }{\star }{\star }{\star }}$ et (18 b) = (0 a, 18 b, 0 c, 0 d) est noté ${\displaystyle \vert {\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }{\star }\vert \vert }$.

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${\displaystyle \left(\!\!{4 \choose 18}\!\!\right)={4+18-1 \choose 18}={4+18-1 \choose 4-1}=1330.}$ 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 ${\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}\ }$ (en utilisant la définition des coefficients binomiaux négatifs) ; de plus, ${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).}$

Relation de récurrence

Une relation de récurrence pour les coefficients de multiensemble est la suivante :${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{pour }}n,k>0}$ avec ${\displaystyle \left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{et}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.}$ La récurrence ci-dessus peut être interprétée comme suit. Soit ${\displaystyle [n]:={1,\dots ,n}}$ 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 ${\displaystyle \left(\!\!{n \choose k-1}\!\!\right)}$ 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 ${\displaystyle \left(\!\!{n-1 \choose k}\!\!\right).}$

Ainsi, ${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).}$

Séries génératrices

La série génératrice des coefficients de multiensemble est très simple : ${\displaystyle \sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.}$ Comme les multiensembles sont en bijection avec les monômes de l'anneau des polynômes ${\displaystyle k[x_{1},\ldots ,x_{n}]}$, ${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$ 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 ${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$ 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

La formule par factorielle montante permet d'étendre la définition des coefficients de multiensemble à un α arbitraire (négatif, réel, ou complexe) :$${\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}=\prod _{j=1}^{k}{\frac {\alpha +j-1}{j}}\quad {\text{pour }}k\in \mathbb {N} ^{*}{\text{ et }}\alpha {\text{ arbitraire }}.}$$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 ${\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)}$ les coefficients binomiaux négatifs : ${\displaystyle (1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.}$

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 ${\displaystyle (1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{et}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )}\ ;}$ des formules telles que celles-ci peuvent être utilisées pour obtenir 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

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, 1997 (ISBN 0-521-55309-1, lire en ligne)

Voir aussi

Articles connexes

• Combinaison avec répétition
• Réunion disjointe

Bibliographie

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