
Etant donné un ensemble on note classiquement
l’ensemble des couples d’éléments de
Un couple est une structure ordonnée au sens où, si
alors les couples
et
sont différents. Par contraste, la paire
, ensemble à deux éléments, est identique à la paire
.
Une opération sur un ensemble
n’est pas autre chose qu’une application de
dans
A chaque couple est associé un élément de
qui dans ce contexte est noté
L’opération est dite associative lorsque :
On peut alors se passer des parenthèses et écrire simplement
Lorsqu’une opération n’est pas associative, l’expression
est ambigüe et ne doit pas être utilisée. Le rôle des parenthèses est, précisément, d’éliminer toute ambiguïté.
Dans la formule ci-dessus, les parenthèses sont déplacées mais l’ordre des éléments n’est pas modifié ! La question de l’associativité ne doit donc pas être confondue avec celle de la commutativité. L’opération est dite commutative lorsque
quel que soit le couple
Cet article rassemble quelques remarques au sujet des opérations associatives.
1 – Exemples et contre-exemples immédiats
■ L’addition et la multiplication dans sont des opérations associatives.
■ Même chose pour la composition des applications. Si est un ensemble et si
désigne l’ensemble des applications de
dans lui-même, alors étant données
et
dans
:

■ Notons l’ensemble des suites finies à termes dans un ensemble non vide
On dit que
est l’alphabet et que
est l’ensemble des mots sur
Dans ce contexte, une suite finie est notée simplement en juxtaposant ses termes (dans l’ordre des indices croissants).
Deux mots et
peuvent être concaténés (càd : mis « bout à bout ») pour former le mot
Par exemple si
et
alors
L’opération de concaténation ainsi définie est clairement associative.
■ En revanche, la soustraction dans n’est pas associative :
■ L’exponentiation (opération « puissance ») dans n’est pas non plus associative puisque :

Il y a une raison simple à cela. On peut, a priori, hésiter entre deux interprétations de l’expression …
- soit en parenthésant à gauche :
- soit en parenthésant à droite :
Mais on sait bien que . Il est donc naturel de convenir que l’expression
désigne
■ Dans un espace vectoriel euclidien orienté de dimension 3, le produit vectoriel n’est pas associatif. On sait par exemple que si est une base orthonormale directe, alors
tandis que
Voici maintenant un exemple un peu plus consistant.
2 – Différence symétrique
Etant donné un ensemble l’ensemble des parties de
est noté
et le complémentaire dans
d’une partie
est noté
On définit dans une opération notée
, en posant pour tout couple
de parties de
:
Les opérations d’union (symbole ) et d’intersection (symbole
) correspondent respectivement aux connecteurs logiques OU (inclusif) et ET. Dans cette analogie, l’opération
correspond au fameux XOR, alias « ou exclusif » (en anglais : eXclusive OR).
Illustration dynamique
On voit ici un ensemble et deux sous-ensembles
de
.
En cliquant sur l’un quelconque des 8 boutons de gauche, on fait apparaître la partie correspondante (ou son complémentaire dans si le bouton
est activé).
Proposition
L’opération est associative.
Preuve (cliquer pour déplier / replier)
Soient trois parties de
Par définition de
:




On pourrait ensuite développer et constater qu’on parvient au même résultat.
Mais on peut être plus malin 🤓
L’expression encadrée ci-dessus est invariante par permutation circulaire : elle reste inchangée si le triplet est remplacé par
En effet, cette permutation transforme le 1er terme de cette union en le 2ème, le 2ème en le 3ème, le 3ème en le 1er; quant au 4ème, il est invariant :

Autrement dit :


Dans la section 5, nous reviendrons sur cette question en adoptant un angle de vue différent.
3 – Invariance circulaire & Associativité
Soit un ensemble muni d’une opération
Définition
L’opération est dite circulairement invariante lorsque :
On peut alors énoncer :
Proposition
Si est commutative et circulairement invariante, alors
est associative.
La justification de cette affirmation est immédiate ! Mais en dépit de sa simplicité, cette proposition a montré son utilité : elle a permis, à la section précédente, d’alléger la preuve de l’associativité de la différence symétrique. En voici une variante :
Proposition Bis
Si est circulairement invariante et admet un élément neutre,
alors est commutative et associative.
Notons l’élément neutre. Pour tout
:
c’est-à-dire
L’opération est ainsi commutative et donc associative grâce au point précédent.
Notons que, dans la proposition-bis, l’hypothèse d’invariance circulaire n’est pas suffisante à elle seule.
Voici un exemple d’une opération circulairement invariante, mais qui n’est ni commutative ni associative (le secret est l’absence d’élément neutre) :
Exemple
Munissons de l’opération définie par :




Mais n’est pas commutative puisque :

4 – Associativité et Inversibilité
Lorsqu’une opération sur un ensemble
possède un élément neutre
la notion d’inversibilité apparaît aussitôt.
Définition
Un élément est dit inversible s’il existe
tel que :



On notera l’emploi de l’article indéfini : un inverse car il n’y a aucune garantie d’unicité a priori.
Voici un exemple montrant que certains éléments peuvent posséder plusieurs inverses, tandis que d’autres n’en possèdent qu’un seul, ou même aucun.
Exemple
Munissons de l’opération
définie par :
On trouve les (éventuels) inverses d’un réel en résolvant l’équation
qui est une simple équation du second degré.
Il est facile de voir que :
possède deux inverses, à savoir
et
,
possède un seul inverse : lui-même,
ne possède pas d’inverse.
Cette « bizarrerie » est rendue possible par le fait que, dans cet exemple, l’opération n’est pas associative, ce qu’on peut constater directement :
Proposition
Soit une opération associative sur
admettant un élément neutre
Si est inversible, alors il existe un unique inverse pour cet élément.
Cet inverse, s’il existe, est généralement noté
Soit et soient
deux inverses de
Alors :
Remarque
Ce simple calcul prouve un résultat un peu meilleur. Si un élément possède inverse à gauche et un inverse à droite, alors ces deux-là sont égaux et donc est inversible tout court.
5 – Retour sur l’associativité de la différence symétrique
désigne à nouveau un ensemble quelconque.
Définissons une opération notée dans l’ensemble des applications de
dans
Pour tout couple d’applications de
dans
posons :



Il est facile de voir que est associative : ceci découle immédiatement du fait que
est elle-même associative dans
Notons ensuite la fonction indicatrice d’une partie
de
. C’est l’application
qui à tout
associe 1 si
et 0 sinon.
On constate que, pour tout couple de parties de
:


Nous avons établi d’une seconde manière l’associativité de
Remarque
En fait, on peut définir une seconde opération dans en posant :



Point de terminologie : un tel anneau, dont chaque élément est idempotent (égal son carré) est appelé un anneau de Boole.
6 – Nombre de parenthésages d’un produit
Soit une opération sur un ensemble
non supposée associative.
Etant donnés un entier et des éléments
de
l’expression :

Afin de lever cette ambiguïté, il faut choisir un parenthésage. Et de nombreuses possibilités se présentent …
➡ Si il existe 2 parenthésages possibles :
➡ Si il en existe 5 :
Il est naturel de se demander quel est, plus généralement, le nombre de parenthésages — formellement différents — que l’on peut envisager pour un produit de
facteurs.
On peut répondre à cette question en raisonnant par récurrence.
Trivialement :
Etant donnés et des éléments
le calcul de
ne peut être envisagé qu’après avoir mis en évidence deux facteurs, disons
et
(pour un certain entier
, lesquels doivent à leur tour être parenthésés. Le premier facteur peut être parenthésé de
façons et le second peut l’être de
façons.
On voit ainsi (après vérification directe pour ) que :
Il est facile de programmer (ci-dessous en Python) le calcul des premiers termes de la suite . Ces entiers sont stockés dans une liste, au fur et à mesure de l’avancement du calcul :
def calculP(nmax):
if (nmax < 2):
print ('Entrer un entier n > 1')
else:
p = [1,1]
for n in range (3, nmax + 1):
s = 0
for k in range (1,n):
s += p[k-1] * p[n-k-1]
p.append(s)
return p
La fonction calculP accepte un entier et renvoie la liste
Les entiers pour
ont été calculés de cette façon :

Le moins qu’on puisse dire, c’est que cette suite grimpe rapidement !
Afin de quantifier cette impression de croissance rapide, il nous faut trouver une estimation asymptotique de lorsque
. C’est l’objet de la section 7.
Avant cela, voici comment on peut énumérer les parenthésages pour un
donné :
def car(n):
return chr(64+n)
def aux(n, start):
if (n == 1):
return [car(start)]
elif (n == 2):
return [car(start) + car(start+1)]
else:
res = []
for k in range(1,n):
g = aux (k, start)
d = aux (n-k, start+k)
for i in range(len(g)):
for j in range(len(d)):
gi = g[i]
dj = d[j]
if (len(gi) == 1):
if (len(dj) > 1):
res.append(g[i]+'('+d[j]+')')
else:
res.append(g[i]+d[j])
else:
if (len(dj) > 1):
res.append('('+g[i]+')('+d[j]+')')
else:
res.append('('+g[i]+')'+d[j])
return res
def enumP (n):
if (n > 10):
print ('trop grand, désolé ...')
else:
sol = aux (n, 1)
for i in range(len(sol)):
print (sol[i])
La fonction enumP, appliqué à un entier (au maximum 10 pour ne pas que ça devienne délirant), affiche ligne par ligne les parenthésages. Par exemple :
>>> enumP(5)
A(B(C(DE)))
A(B((CD)E))
A((BC)(DE))
A((B(CD))E)
A(((BC)D)E)
(AB)(C(DE))
(AB)((CD)E)
(A(BC))(DE)
((AB)C)(DE)
(A(B(CD)))E
(A((BC)D))E
((AB)(CD))E
((A(BC))D)E
(((AB)C)D)E
7 – La suite
démasquée
Nous allons utiliser la puissante technique de la fonction génératrice.
L’idée est d’introduire la série entière et de trouver une relation (typiquement une équation fonctionnelle ou différentielle) vérifiée par sa somme. Notons
son rayon de convergence.

Il n’est pas évident que
On pourrait l’établir au préalable au moyen d’une majoration adéquate de mais nous allons prendre l’ennemi à revers 😉
Supposons temporairement qu’on ait et posons, pour tout
:


Attention : cette relation n’est pas valable pour En effet :
alors que
Pour tout :


Ainsi et donc
Mais comme
alors
En résolvant l’équation on voit que :


Comme est continue sur
et vu que
le théorème des valeurs intermédiaires montre que
ne prend pas de valeurs supérieures à
Il est donc nécessaire que :
Maintenant, il est classique que pour fixé :
![Rendered by QuickLaTeX.com t\in\left]-\frac{1}{4},\frac{1}{4}\right[](https://math-os.com/wp-content/ql-cache/quicklatex.com-dd7be94693aa587225a4345aa88c7ebd_l3.png)
Ce raisonnement par condition nécessaire (voir cet article pour la signification de cette expression) nous a mis sur les rails. Nous savons maintenant ce qu’il nous faut prouver :
Proposition
Pour tout :
Posons, pour tout :




Comme il en résulte que les suites
et
sont confondues (elles vérifient la même « condition initiale » et la même formule de récurrence) et la formule
est démontrée.
Pour finir, la formule de Stirling (voir cet article pour une preuve) dit que, lorsque :

Si l’on note cet équivalent alors
à comparer à
Il serait injuste de terminer cette section sans signaler que les entiers constituent un classique des questions de combinatoire, puisqu’il s’agit (à un décalage d’indice près) des nombres de Catalan (une célèbre conjecture de Catalan a été évoquée dans cet article).

8 – Combien d’opérations associatives ?
Une question classique de combinatoire consiste à dénombrer les opérations sur un ensemble fini, qui satisfont une condition spécifique donnée. On considère donc un ensemble de cardinal
Pour commencer, vu qu’une opération sur est une application de
dans
il existe en tout :

Comme cela a été signalé à la section 1 :
il faut comprendre que désigne
Cet entier prend rapidement des valeurs énormes.
Par exemple, sur un ensemble à 4 éléments, on peut définir c’est-à-dire 4 294 967 296 opérations !!
Et sur un ensemble à 10 éléments, le nombre d’opérations passe à (un 1 suivi de cent zéros) … ce qui est tout bonnement impossible à se représenter concrètement (voir quand même cet article pour une interprétation amusante d’un autre entier colossal : la factorielle de 52).
Intéressons-nous maintenant à une propriété que peut éventuellement posséder une opération sur
Le nombre d’opérations sur
possédant cette propriété sera noté
Le calcul de est plus ou moins aisé, selon la nature de
Je vous propose d’obtenir une formule explicite pour dans chacun des cas suivants :
= commutativité
= posséder un élément neutre
Si vous trouvez la réponse à l’une au moins de ces deux questions, n’hésitez pas à m’en faire part et votre contribution pourra être mise en ligne, en annexe à cet article.
Le titre de cette section soulève, quant à lui, une question nettement moins commode … en effet, aucune formule explicite n’a été trouvée à ce jour pour le nombre d’opérations associatives sur un ensemble fini. Parmi les travaux de recherche récents consacrés à cette question, on peut citer la thèse de Andreas Distler, soutenue en 2010 à l’université de Saint-Andrews.
Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.
Bonjour Monsieur,
Je vous remercie pour votre réponse très détaillée !
C’est bien compris pour l’unicité du neutre, lorsqu’il y a existence et pour une opération donnée.
Je comprends aussi (désormais !) le raisonnement qui passe en revue tous les éléments comme neutre potentiel.
Je vous souhaite une bonne journée,
A bientôt
Bonjour Monsieur,
Merci pour cet article instructif et détaillé.
Pour les questions de fin : je tente ma chance 😊
Considérons un tableau carré de n lignes et n colonnes. Afin que cela soit plus clair, on peut ajouter une colonne (qui n’appartient pas au tableau !) à gauche de la première colonne avec dans celle-ci tous les éléments de l’ensemble E à n éléments -donc distincts- (notons les : X1, …, Xn, notons de plus * une loi de composition interne sur E). Procédons de façon analogue en ajoutant une ligne au-dessus de la première ligne avec les éléments de E. Il est alors facile de poser et visualiser que l’élément de la ligne i et de la colonne j du tableau est Xi*Xj.
0) Pour une loi donnée, chaque « case » du tableau peut donner lieu à n possibilités, on retrouve donc le fait qu’il y n^(n^2) lois possibles sur E, puisque le tableau comporte n^2 cases ;
1) Nous cherchons désormais à dénombrer les lois commutatives sur E. Raisonnons de nouveau à l’aide du tableau, celui-ci est composé d’une diagonale, d’un triangle inférieur et d’un triangle supérieur. La commutativité signifie que la connaissance d’un des deux triangles détermine l’autre triangle. De ce fait l’exposant sera cette fois-ci le cardinal de la diagonale auquel on ajoute celui d’un triangle (ce qui donne le cardinal d’un triangle un peu plus grand). Le nombre de lois commutatives sur E est donc n^(n(n+1)/2) ;
2) Nous cherchons le nombre de lois sur E possédant un unique élément neutre. Fixons Xn comme étant l’élément neutre. Ainsi la dernière ligne (et la dernière colonne) est la liste des éléments de E, quelle que soit la loi possédant un élément neutre. Nous sommes ramenés à un tableau carré de taille n-1, mais avec toujours n possibilités pour chaque case, le nombre cherché est donc n^((n-1)^2).
->on suppose implicitement que toutes ces lois possédant un élément neutre ont le même élément neutre (ce qui est peut-être faux). J’ai l’impression que ce n’est pas un problème dans le cadre de ce dénombrement ?
2)bis S’il existe k éléments neutres distincts (est-ce possible?), nous sommes ramenés à un tableau carré de taille n-k, le nombre cherché est donc dans ce cas n^((n-k)^2)
3) Ce n’était pas demandé, mais puisque ça ne coûte pas cher 😊, nous voyons aisément en combinant les raisonnements précédents, que le nombre de lois commutatives sur E possédant un unique élément neutre est n^(n(n-1)/2).
Bien à vous.
Bonjour et désolé pour le délai de réponse.
Ce qui vous expliquez dans votre préambule est correct. Pour le formuler un peu différemment : une opération sur un ensemble
de cardinal
n’étant rien d’autre qu’une application de
dans
, il existe au total
opérations, d’après la formule générale donnant le nombre d’applications d’un ensemble fini
vers un ensemble fini
, à savoir
.
Ok aussi pour votre 1er point, que je reformule à ma façon (mais sans rien ajouter à votre preuve … simple variante de rédaction). Enumérons les éléments de
en posant
et notons
(ce qui correspond très exactement à votre triangle supérieur, diagonale comprise). Se donner une opération commutative sur
revient à se donner une application de
vers
. Il existe donc
telles opérations.
et
sont neutres, alors
, la première égalité découlant du fait que
est neutre et la seconde du fait que
est neutre. Bref, soit il n’existe pas de neutre, soit il en existe un seul. A partir de là, on va dénombrer dans un premier temps les opérations pour lesquelles un élément
particulier est neutre. Notons
leur nombre, qui ne dépend pas de la valeur de
. Le nombre d’opérations possédant un neutre sera alors donné par
. Enfin, se donner une opération pour laquelle
est neutre revient à se donner une application de
dans
, donc
. Finalement, il existe
opérations possédant un neutre.
Concernant le dénombrement des opérations possédant un neutre, une petite erreur s’est glissée dans votre raisonnement. Il ne peut en effet pas exister plus d’un élément neutre, car si
On termine avec les opérations commutatives possédant un neutre. Un raisonnement similaire montre qu’il en existe
.