Voir la source de Multiensemble

{{Ébauche|mathématiques}}
{{Voir homonymes|Sac (homonymie)}}

Un '''multiensemble''' (parfois appelé '''sac''', de l'anglais ''{{Langue|en|bag}}'' utilisé comme synonyme de ''{{Langue|en|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 <math>(A,m)</math> où <math>A</math> est un ensemble appelé ''support'' et <math>m</math> une fonction de <math>A</math> dans l'ensemble des [[Entier naturel|entiers naturels]], appelée ''multiplicité'' (notée  <math>m</math>). Dans le multiensemble <math>(A,m)</math>, l'élément <math>x</math> apparaît <math>m(x)</math> fois.

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

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

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

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

== Ordre multiensemble ==

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

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

Si on suppose que l'ordre sur <math>A</math> est [[Relation bien fondée|bien fondé]], alors l'ordre multiensemble ainsi défini l'est aussi<ref>{{pdf}} [http://color.inria.fr/papers/coupet06jfla.pdf Un article de Coupet-Grimal et Delobel].</ref>.

== Dénombrement des multiensembles ==
{{Voir aussi|Méthode des étoiles et des barres|Combinaison avec répétition}}
Le nombre de multiensembles de [[Nombre cardinal|cardinal]] ''{{mvar|k}}'' (la somme des multiplicités de chaque élément), avec des éléments pris dans un [[ensemble fini]] de cardinal ''{{mvar|n}}'', est parfois appelé le '''coefficient de multiensemble''' ; ce nombre est écrit par certains auteurs comme <math>\left(\!\!{n\choose k}\!\!\right)</math>, une notation qui est censée ressembler à celle des [[Coefficient binomial|coefficients binomiaux]]{{Note|texte=Elle est utilisée par exemple par [[Richard Peter Stanley]] dans {{ouvrage|lang=en|prénom=|lien auteur=|année=1997|titre=Enumerative Combinatorics|volume=1|éditeur=Cambridge University Press | url=http://www-math.mit.edu/~rstan/ec/|isbn=0-521-55309-1}}}}. 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 [[Formule du multinôme de Newton|coefficients multinomiaux]] qui apparaissent dans la [[loi multinomiale]]).

La valeur des coefficients de multiensemble peut être donnée explicitement par<math display="block">\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!},</math>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 ''{{mvar|k}}'' d'un ensemble de cardinal {{math|''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 [[Symbole de Pochhammer|puissance factorielle montante]] :<math>\left(\!\!{n \choose k}\!\!\right) = {n^{\overline{k}}\over k!},</math> pour correspondre à l'expression des coefficients binomiaux utilisant une puissance factorielle descendante :<math>{n \choose k} = {n^{\underline{k}}\over k!}.</math> 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 <math> {7 \choose 3} = \left(\!\!{5 \choose 3}\!\!\right).</math><nowiki> Cette bijection associe par exemple le sous-ensemble {1,4,5} au multiensemble {{</nowiki>''{{mvar|a}}'',''{{mvar|c}}'',''{{mvar|c}}''<nowiki>}} = (1</nowiki>''{{mvar|a}}'', 0''{{mvar|b}}'', 2''{{mvar|c}}'', 0''{{mvar|d}}'', 0''{{mvar|e}}'').

Une façon simple de [[Preuve mathématique|prouver]]  cette égalité entre coefficients de multiensemble et coefficients binomiaux consiste à représenter les multiensembles par une [[Méthode des étoiles et des barres|série d'étoiles séparés par des barres]] : le multiensemble (6 ''{{mvar|a}}'', 2 ''{{mvar|b}}'', 3 ''{{mvar|c}}'', 7 ''{{mvar|d}}'') est noté {{nowrap|<math>{{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}}  \vert {{\star}} {{\star}}  \vert {{\star}} {{\star}} {{\star}}  \vert {{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}}</math>}} et (18 ''{{mvar|b}}'') = (0 ''{{mvar|a}}'', 18 ''{{mvar|b}}'', 0 ''{{mvar|c}}'', 0 ''{{mvar|d}}'') est noté {{nowrap|<math>  \vert {{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}}{{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}}{{\star}} {{\star}} {{\star}} {{\star}} {{\star}} {{\star}} \vert \vert </math>}}.

Ce multiensemble de cardinal {{math|1=''k'' = 18}} est composé d'éléments d'un ensemble de cardinal {{math|1=''n'' = 4}}. Le nombre de caractères incluant à la fois des étoiles et des lignes verticales utilisés dans cette notation est {{math|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 {{math|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 {{math|18 + 4 − 1}}. C'est donc bien que<math>\left(\!\!{4 \choose 18}\!\!\right) ={4+18-1 \choose 18} = {4+18-1 \choose 4-1}= 1330.</math> De la relation entre les coefficients binomiaux et les coefficients de multiensemble, il s'ensuit que le nombre de multiensembles de cardinal ''{{mvar|k}}'' dans un ensemble de cardinal ''{{mvar|n}}'' peut être écrit <math>\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k}\ </math> (en utilisant la définition des [[Coefficient binomial#Élargissement du domaine de définition|coefficients binomiaux négatifs]]) ; de plus, <math>\left(\!\!{n\choose k}\!\!\right)=\left(\!\!{k+1\choose n-1}\!\!\right).</math>

=== Relation de récurrence ===
Une [[Suite définie par récurrence|relation de récurrence]] pour les coefficients de multiensemble est la suivante :<math>\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right) \quad \mbox{pour } n,k>0</math> avec <math>\left(\!\!{n \choose 0}\!\!\right) = 1,\quad n\in\N, \quad\mbox{et}\quad \left(\!\!{0 \choose k}\!\!\right) = 0,\quad k>0.</math> La récurrence ci-dessus peut être interprétée comme suit. Soit <math>[n] := {1,\dots,n}</math> l'ensemble support. Il y a toujours exactement un multiensemble (vide) de taille 0, et si {{math|1=''n'' = 0}} il n'y a pas de multiensembles plus grands, ce qui donne les conditions initiales.

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

Ainsi, <math>\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right).</math>

=== Séries génératrices ===
La [[série génératrice]] des coefficients de multiensemble est très simple : <math>\sum_{d=0}^\infty \left(\!\!{n\choose d}\!\!\right)t^d = \frac{1}{(1-t)^n}.</math> Comme les multiensembles sont en bijection avec les [[Monôme (mathématiques)|monômes]] de l'[[Polynôme formel|anneau des polynômes]] <math>k[x_1, \ldots, x_n]</math>, <math>\left(\!\!{n\choose d}\!\!\right)</math> est aussi le nombre de monômes en ''{{mvar|n}}'' indéterminées de [[Degré d'un polynôme#Extension à des polynômes à deux variables ou plus|degré]] ''{{mvar|d}}'' . Ainsi, la série ci-dessus est également la {{Lien|trad=Hilbert series and Hilbert polynomial|fr=série de Hilbert}} de cet anneau.

Comme <math>\left(\!\!{n\choose d}\!\!\right)</math> est un polynôme en ''{{mvar|n}}'', lui et la série génératrice sont en fait bien définis pour toute valeur [[Nombre complexe|complexe]] de ''{{mvar|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 ''{{mvar|α}}''  arbitraire (négatif, [[Nombre réel|réel]], ou complexe) :<math display="block">\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\N^* \text{ et } \alpha \text{ arbitraire }. </math>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 <math>\left(\!\!{\alpha\choose k}\!\!\right)</math> les coefficients binomiaux négatifs : <math>(1-X)^{-\alpha} = \sum_{k=0}^\infty \left(\!\!{\alpha\choose k}\!\!\right) X^k.</math>

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é (mathématiques)|identité]] [[Série formelle|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 <math>(1-X)^{-\alpha}(1-X)^{-\beta}=(1-X)^{-(\alpha+\beta)} \quad\text{et}\quad ((1-X)^{-\alpha})^{-\beta}=(1-X)^{-(-\alpha\beta)}\ ;</math> des formules telles que celles-ci peuvent être utilisées pour obtenir des identités pour les coefficients de multisensemble. Si ''{{mvar|α}}'' est un entier négatif ''{{mvar|n}}'', alors tous les termes avec {{math|''k'' > −''n''}} sont nuls, et la série infinie devient une somme finie.

== Notes et références ==
<references/>
== Voir aussi ==
=== Articles connexes ===
* [[Combinaison avec répétition]]
* [[Réunion disjointe]]

=== Bibliographie ===
{{Article|lang=en|auteur=Wayne D. Blizard|titre=The development of multiset theory|revue=Modern Logic|vol=1|numéro=4|année=1991|p.=319-352|url=http://projecteuclid.org/euclid.rml/1204834739}}

{{Portail|mathématiques}}

[[Catégorie:Théorie des ensembles]]
[[Catégorie:Théorie des ordres]]
[[Catégorie:Structure de données]]