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 :

   

En effet, pour tout :

   

■ 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 serait donc logique qu’on évite la notation … et pourtant celle-ci est utilisée ! 🤔

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 :

   

Cette opération, visiblement commutative, est appelée différence symétrique.

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).

3 – Invariance circulaire & Associativité

Soit un ensemble muni d’une opération

On peut alors énoncer :

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 :

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) :

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.

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.

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 :

   

   

En revanche, pour une opération associative, cette fantaisie n’est plus permise :

Soit et soient deux inverses de Alors :

   

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 :

   

où est le symbole de l’addition modulo 2 (c’est-à-dire : et

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 :

   

ce qui entraîne que, pour tout triplet de parties de :

   

Comme l’application :

   

est injective (c’est même une bijection : voir cet article pour les détails), on conclut que :

   

Nous avons établi d’une seconde manière l’associativité de

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 :

   

est ambigüe dès que , comme on l’a déjà souligné dans l’introduction.

Afin de lever cette ambiguïté, il faut choisir un parenthésage. Mais il en existe de nombreux !

➡ Si il en existe 2 :

   

➡ Si il en existe 5 :

   

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.

Supposons temporairement qu’on ait et posons, pour tout :

   

Prolongeons aussi la suite en posant ce qui permet de ré-écrire la formule sous la forme :

   

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

Pour tout :

   

et donc ce qui impose

Ainsi et donc Mais comme alors

En résolvant l’équation on voit que :

   

et donc ne prend pas la valeur

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é :

   

et donc, pour tout :

   

d’où, après un petit calcul sans douleur :

   

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 :

Posons, pour tout :

   

de sorte que et pour tout On vérifie aisément que d’où l’on déduit (par unicité du développement en série entière) que :

   

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 :

   

Il en résulte, en injectant ceci dans que :

   

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. 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 :

   

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

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.