
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é :
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 seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.