A propos de l’associativité

Etant donné un ensemble E, on note classiquement E^{2} l’ensemble des couples d’éléments de E.

Un couple \left(a,b\right) est une structure ordonnée au sens où, si a\neq b alors les couples \left(a,b\right) et \left(b,a\right) sont différents. Par contraste, la paire \left\{ a,b\right\}, ensemble à deux éléments, est identique à la paire \left\{ b,a\right\}.

Une opération \star sur un ensemble E n’est pas autre chose qu’une application de E^{2} dans E.

A chaque couple \left(a,b\right)\in E^{2} est associé un élément de E, qui dans ce contexte est noté a\star b.

L’opération \star est dite associative lorsque :

    \[\boxed{\forall\left(a,b,c\right)\in E^{3},\thinspace\left(a\star b\right)\star c=a\star\left(b\star c\right)}\]

On peut alors se passer des parenthèses et écrire simplement a\star b\star c.

Lorsqu’une opération \star n’est pas associative, l’expression a\star b\star c 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 \star est dite commutative lorsque a\star b=b\star a, quel que soit le couple \left(a,b\right)\in E^{2}.

Cet article rassemble quelques remarques au sujet des opérations associatives.

1 – Exemples et contre-exemples immédiats

L’addition et la multiplication dans \mathbb{R} sont des opérations associatives.

Même chose pour la composition des applications. Si A est un ensemble et si E désigne l’ensemble des applications de A dans lui-même, alors étant données f, g et h dans E :

    \[\left(f\circ g\right)\circ h=f\circ\left(g\circ h\right)\]

En effet, pour tout a\in A :

    \begin{eqnarray*}\left[\left(f\circ g\right)\circ h\right]\left(a\right) & = & \left(f\circ g\right)\left(h\left(a\right)\right)\\& = & f\left(g\left(h\left(a\right)\right)\right)\\& = & f\left(\left(g\circ h\right)\left(a\right)\right)\\& = & \left[f\circ\left(g\circ h\right)\right]\left(a\right)\end{eqnarray*}

Notons \mathcal{M} l’ensemble des suites finies à termes dans un ensemble non vide \mathcal{A}. On dit que \mathcal{A} est l’alphabet et que \mathcal{M} est l’ensemble des mots sur \mathcal{A}. Dans ce contexte, une suite finie est notée simplement en juxtaposant ses termes (dans l’ordre des indices croissants).

Deux mots w_{1} et w_{2} peuvent être concaténés (càd : mis “bout à bout”) pour former le mot w_{1}w_{2}.

Par exemple si \mathcal{A}=\left\{\alpha,\beta\right\}, w_{1}=\alpha\alpha\beta et w_{2}=\beta\alpha, alors w_{1}w_{2}=\alpha\alpha\beta\beta\alpha. L’opération de concaténation ainsi définie est clairement associative.

En revanche, la soustraction dans \mathbb{R} n’est pas associative :

    \[\left(0-1\right)-2=-3\neq1=0-\left(1-2\right)\]

L’exponentiation (opération “puissance”) dans \mathbb{N} n’est pas non plus associative puisque :

    \[\left(2^{2}\right)^{3}=4^{3}=64\neq256=2^{8}=2^{\left(2^{3}\right)}\]

Il serait donc logique qu’on évite la notation a^{b^{c}} … 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 a^{b^c}

  • soit en parenthésant à gauche : \left(a^{b}\right)^{c}
  • soit en parenthésant à droite : a^{\left(b^{c}\right)}

Mais on sait bien que \left(a^{b}\right)^{c}=a^{bc}. Il est donc naturel de convenir que l’expression a^{b^{c}} désigne a^{\left(b^{c}\right)}.

Dans un espace vectoriel euclidien orienté de dimension 3, le produit vectoriel n’est pas associatif. On sait par exemple que si \left(\vec{i},\vec{\jmath},\vec{k}\right) est une base orthonormale directe, alors \left(\vec{\imath}\wedge\vec{\jmath}\right)\wedge\vec{j}=\vec{k}\wedge\vec{j}=-\vec{i} tandis que \vec{\imath}\wedge\left(\vec{\jmath}\wedge\vec{j}\right)=\vec{\imath}\wedge\vec{0}=\vec{0}.

Voici maintenant un exemple un peu plus consistant.

2 – Différence symétrique

Etant donné un ensemble E, l’ensemble des parties de E est noté \mathcal{P}\left(E\right) et le complémentaire dans E d’une partie X est noté \overline{X}.

On définit dans \mathcal{P}\left(E\right) une opération notée \triangle, en posant pour tout couple \left(A,B\right) de parties de E :

    \[\boxed{A\triangle B=\left(A\cap\overline{B}\right)\cup\left(\overline{A}\cap B\right)}\]

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

Les opérations d’union (symbole \cup) et d’intersection (symbole \cap) correspondent respectivement aux connecteurs logiques OU (inclusif) et ET. Dans cette analogie, l’opération \triangle correspond au fameux XOR, alias “ou exclusif” (en anglais : eXclusive OR).

L’illustration dynamique ci-dessous montre un ensemble E et deux sous-ensembles A,B.

En cliquant sur l’un quelconque des 8 boutons de gauche, on fait apparaître la partie correspondante (ou son complémentaire dans E si le bouton \overline{X} est activé).

Opérations Booléennes

Proposition

L’opération \Delta est associative.

Preuve (cliquer pour déplier / replier)

Soient A,B,C trois parties de E. Par définition de \triangle :

    \begin{eqnarray*}\left(A\thinspace\triangle\thinspace B\right)\thinspace\triangle\thinspace C & = & \left[\left(A\cap\overline{B}\right)\cup\left(\overline{A}\cap B\right)\right]\thinspace\triangle\thinspace C\\& = & \left(\left(\left(A\cap\overline{B}\right)\cup\left(\overline{A}\cap B\right)\right)\cap\overline{C}\right)\cup\left(\overline{\left(A\cap\overline{B}\right)\cup\left(\overline{A}\cap B\right)}\cap C\right) \end{eqnarray*}

Or (lois de Morgan et distributivité de \cap sur \cup) :

    \begin{eqnarray*} \overline{\left(A\cap\overline{B}\right)\cup\left(\overline{A}\cap B\right)} & = & \left(\overline{A}\cup B\right)\cap\left(A\cup\overline{B}\right)\\& = & \left(\overline{A}\cap A\right)\cup\left(\overline{A}\cap\overline{B}\right)\cup\left(B\cap A\right)\cup\left(B\cap\overline{B}\right)\\& = & \left(A\cap B\right)\cup\left(\overline{A}\cap\overline{B}\right) \end{eqnarray*}

et donc (toujours par distributivité de \cap sur \cup) :

\left(A\thinspace\triangle\thinspace B\right)\thinspace\triangle\thinspace C = \boxed{\left(A\cap\overline{B}\cap\overline{C}\right)\cup\left(\overline{A}\cap B\cap\overline{C}\right)\cup\left(\overline{A}\cap\overline{B}\cap C\right)\cup\left(A\cap B\cap C\right)}

On pourrait ensuite développer A\thinspace\triangle\thinspace\left(B\thinspace\triangle\thinspace C\right) 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 \left(A,B,C\right) est remplacé par \left(B,C,A\right).

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 :

    \begin{eqnarray*}\left(A\triangle B\right)\triangle C & = & \left(B\triangle C\right)\triangle A\end{eqnarray*}

Mais alors, vue la commutativité de \triangle :

    \[\left(A\triangle B\right)\triangle C=A\triangle\left(B\triangle C\right)\]

et l’associativité de \Delta est établie.

Dans la section 5, nous reviendrons sur cette question en adoptant un angle de vue différent.

3 – Invariance circulaire & Associativité

Soit E un ensemble muni d’une opération \star.

Définition

L’opération \star est dite circulairement invariante lorsque :

    \[\forall\left(a,b,c\right)\in E^{3},\thinspace\left(a\star b\right)\star c=\left(b\star c\right)\star a\]

On peut alors énoncer :

Proposition

Si \star est commutative et circulairement invariante, alors \star 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 \star est circulairement invariante et admet un élément neutre,
alors \star est commutative et associative.

Notons e l’élément neutre. Pour tout \left(a,b\right)\in E^{2} : \left(a\star b\right)\star e=\left(b\star e\right)\star a, c’est-à-dire a\star b=b\star a.

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 \mathbb{R}^{2} de l’opération définie par :

    \[ \forall\left(a,b\right)\in\mathbb{R}^{2},\thinspace\forall\left(c,d\right)\in\mathbb{R}^{2},\thinspace\left(a,b\right)\star\left(c,d\right)=\left(bc,0\right) \]

Etant donnés trois couples \left(a,b\right), \left(c,d\right) et \left(e,f\right) de réels, on a d’une part :

    \begin{eqnarray*}\left(\left(a,b\right)\star\left(c,d\right)\right)\star\left(e,f\right) & = & \left(bc,0\right)\star\left(e,f\right)\\& = & \left(0,0\right)\end{eqnarray*}

et, d’autre part :

    \begin{eqnarray*}\left(\left(c,d\right)\star\left(e,f\right)\right)\star\left(a,b\right) & = & \left(de,0\right)\star\left(a,b\right)\\& = & \left(0,0\right)\end{eqnarray*}

ce qui montre que \star est circulairement invariante.

Mais \star n’est pas commutative puisque :

    \[\left(1,0\right)\star\left(0,1\right)=\left(0,0\right)\neq\left(1,0\right)=\left(0,1\right)\star\left(1,0\right)\]

Et \star n’est pas non associative puisque :

    \[\left(\left(0,1\right)\star\left(0,1\right)\right)\star\left(1,0\right)=\left(0,0\right)\star\left(1,0\right)=\left(0,0\right)\]

tandis que :

    \[\left(0,1\right)\star\left(\left(0,1\right)\star\left(1,0\right)\right)=\left(0,1\right)\star\left(1,0\right)=\left(1,0\right)\]

4 – Associativité et Inversibilité

Lorsqu’une opération \star sur un ensemble E possède un élément neutre e, la notion d’inversibilité apparaît aussitôt.

Définition

Un élément x\in E est dit inversible s’il existe y\in E tel que :

    \[x\star y=y\star x=e\]

Un tel élément y est alors appelée un inverse de x (pour l’opération \star).

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 \mathbb{R} de l’opération \star définie par :

    \[\forall\left(x,y\right)\in\mathbb{R}^{2},\thinspace x\star y=xy+\left(x^{2}-1\right)\left(y^{2}-1\right)\]

On constate que 1 est (l’unique) élément neutre.

On trouve les (éventuels) inverses d’un réel a en résolvant l’équation x\star a=1, qui est une simple équation du second degré.

Il est facile de voir que :

  • \sqrt{3} possède deux inverses, à savoir -\sqrt{3} et {\displaystyle \frac{\sqrt{3}}{2}},
  • -1 possède un seul inverse : lui-même,
  • \frac{1}{2} 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 :

    \[\left(2\star2\right)\star0=13\star0=-168\]

    \[2\star\left(2\star0\right)=2\star\left(-3\right)=18\]

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

Proposition

Soit \star une opération associative sur E, admettant un élément neutre e.

Si x\in E est inversible, alors il existe un unique inverse pour cet élément.

Cet inverse, s’il existe, est généralement noté x^{-1}.

Soit x\in E et soient y,z deux inverses de x. Alors :

    \[ y=y\star e=y\star\left(x\star z\right)=\left(y\star x\right)\star z=e\star z=z\]

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 x est inversible tout court.

5 – Retour sur l’associativité de la différence symétrique

E désigne à nouveau un ensemble quelconque.

Définissons une opération notée + dans l’ensemble des applications de E dans \left\{ 0,1\right\} .

Pour tout couple \left(f,g\right) d’applications de E dans \left\{ 0,1\right\} , posons :

    \[f+g:E\rightarrow\left\{ 0,1\right\} ,\thinspace e\mapsto f\left(e\right)\oplus g\left(e\right)\]

\oplus est le symbole de l’addition modulo 2 (c’est-à-dire : 0\oplus0=1\oplus1=0 et 0\oplus1=1\oplus0=1).

Il est facile de voir que + est associative : ceci découle immédiatement du fait que \oplus est elle-même associative dans \left\{ 0,1\right\} .

Notons ensuite \mathds{1}_{A} la fonction indicatrice d’une partie A de E. C’est l’application E\rightarrow\left\{ 0,1\right\} qui à tout e\in E associe 1 si e\in A et 0 sinon.

On constate que, pour tout couple \left(A,B\right) de parties de E :

    \[\mathds{1}_{A\thinspace\triangle\thinspace B}=\mathds{1}_{A}+\mathds{1}_{B}\]

ce qui entraîne que, pour tout triplet \left(A,B,C\right) de parties de E :

    \begin{eqnarray*}\mathds{1}_{\left(A\thinspace\triangle\thinspace B\right)\thinspace\triangle\thinspace C} & = & \mathds{1}_{A\thinspace\triangle\thinspace B}+\mathds{1}_{C}\\& = & \left(\mathds{1}_{A}+\mathds{1}_{B}\right)+\mathds{1}_{C}\\& = & \mathds{1}_{A}+\left(\mathds{1}_{B}+\mathds{1}_{C}\right)\\& = & \mathds{1}_{A}+\mathds{1}_{B\thinspace\triangle\thinspace C}\\& = & \mathds{1}_{A\thinspace\triangle\thinspace\left(B\thinspace\triangle\thinspace C\right)}\end{eqnarray*}

Comme l’application :

    \[\Phi:\mathcal{P}\left(E\right)\rightarrow\left\{ 0,1\right\} ^{E},\thinspace X\mapsto\mathds{1}_{X}\]

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

    \[\left(A\thinspace\triangle\thinspace B\right)\thinspace\triangle C=A\thinspace\triangle\thinspace\left(B\thinspace\triangle\thinspace C\right)\]

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

Remarque

En fait, on peut définir une seconde opération dans \left\{ 0,1\right\} ^{E} en posant :

    \[f\times g:E\rightarrow\left\{ 0,1\right\} ,\thinspace e\mapsto f\left(e\right)\thinspace g\left(e\right)\]

Il est alors facile de voir que \left(\left\{ 0,1\right\} ^{E},+,\times\right) est un anneau commutatif et que la bijection \Phi^{-1} transporte cette structure sur \left(\mathcal{P}\left(E\right),\thinspace\triangle,\thinspace\cap\right), lequel devient à son tour un anneau commutatif.

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 \star une opération sur un ensemble E, non supposée associative.

Etant donnés un entier n\geqslant1 et des éléments x_{1},\cdots,x_{n} de E, l’expression :

    \[x_{1}\star\cdots\star x_{n}\]

est ambigüe dès que n\geqslant3, 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 n=3, il en existe 2 :

    \[\begin{array}{c}x_{1}\star\left(x_{2}\star x_{3}\right)\\\left(x_{1}\star x_{2}\right)\star x_{3}\end{array}\]

➡ Si n=4, il en existe 5 :

    \[\begin{array}{c}\left(\left(x_{1}\star x_{2}\right)\star x_{3}\right)\star x_{4}\\\left(x_{1}\star\left(x_{2}\star x_{3}\right)\right)\star x_{4}\\\left(x_{1}\star x_{2}\right)\star\left(x_{3}\star x_{4}\right)\\x_{1}\star\left(\left(x_{2}\star x_{3}\right)\star x_{4}\right)\\x_{1}\star\left(x_{2}\star\left(x_{3}\star x_{4}\right)\right)\end{array}\]

Il est naturel de se demander quel est, plus généralement, le nombre P_{n} de parenthésages — formellement différents — que l’on peut envisager pour un produit de n facteurs.

On peut répondre à cette question en raisonnant par récurrence.

Trivialement : P_{1}=P_{2}=1.

Etant donnés n\geqslant3 et des éléments x_{1},\cdots,x_{n}, le calcul de x_{1}\star\cdots\star x_{n} ne peut être envisagé qu’après avoir mis en évidence deux facteurs, disons x_{1}\star\cdots\star x_{k} et x_{k+1}\star\cdots\star x_{n} (pour un certain entier k\in\left\llbracket 1,n-1\right\rrbracket ), lesquels doivent à leur tour être parenthésés. Le premier facteur peut être parenthésé de P_{k} façons et le second peut l’être de P_{n-k} façons.

On voit ainsi (après vérification directe pour n=2) que :

    \[\boxed{\forall n\geqslant2,\thinspace P_{n}=\sum_{k=1}^{n-1}P_{k}P_{n-k}}\qquad\left(\heartsuit\right)\]

Il est facile de programmer (ci-dessous en Python) le calcul des premiers termes de la suite \left(P_{n}\right)_{n\geqslant1}. 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 n\geqslant2 et renvoie la liste \left[P_{1},\cdots,P_{n}\right]

Les entiers P_{n} pour 1\leqslant n\leqslant30 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 P_{n} lorsque n\to+\infty. C’est l’objet de la section 7.

Avant cela, voici comment on peut énumérer les P_n parenthésages pour un n 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 P_n 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 \left(P_{n}\right)_{n\geqslant1} 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 {\displaystyle \sum_{n\geqslant1}P_{n}t^{n}} et de trouver une relation (typiquement une équation fonctionnelle ou différentielle) vérifiée par sa somme. Notons R son rayon de convergence.

Il n’est pas évident que R>0.

On pourrait l’établir au préalable au moyen d’une majoration adéquate de P_{n}, mais nous allons prendre l’ennemi à revers 😉

Supposons temporairement qu’on ait R>0 et posons, pour tout t\in\left]-R,R\right[ :

    \[f\left(t\right)=\sum_{n=1}^{\infty}P_{n}t^{n}\]

Prolongeons aussi la suite en posant P_{0}=0, ce qui permet de ré-écrire la formule \left(\heartsuit\right) sous la forme :

    \[\forall n\geqslant2,\thinspace P_{n}=\sum_{k=0}^{n}P_{k}P_{n-k}\]

Attention : cette relation n’est pas valable pour n=1. En effet : P_{1}=1 alors que P_{0}P_{1}+P_{1}P_{0}=0.

Pour tout t\in\left]-R,R\right[ :

    \begin{eqnarray*}f\left(t\right)-t & = & \sum_{n=2}^{\infty}P_{n}t^{n}\\& = & \sum_{n=2}^{\infty}\left(\sum_{k=0}^{n}P_{k}P_{n-k}\right)t^{n}\\& = & \sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}P_{k}P_{n-k}\right)t^{n}\\& = & f\left(t\right)^{2}\end{eqnarray*}

et donc t=f\left(t\right)-f\left(t\right)^{2}, ce qui impose t\leqslant\frac{1}{4}.

Ainsi \left]-R,R\right[\subset\left]-\infty,\frac{1}{4}\right] et donc R\leqslant\frac{1}{4}. Mais comme \left|t\right|<R, alors t<\frac{1}{4}.

En résolvant l’équation x^{2}-x+t=0, on voit que :

    \begin{eqnarray*}f\left(t\right) & = & \frac{1}{2}\left(1-\sqrt{1-4t}\right)<\frac{1}{2}\\& \text{ou bien}\\f\left(t\right) & = & \frac{1}{2}\left(1+\sqrt{1-4t}\right)>\frac{1}{2} \end{eqnarray*}

et donc f ne prend pas la valeur \frac{1}{2}.

Comme f est continue sur \left]-R,R\right[ et vu que f\left(0\right)=0, le théorème des valeurs intermédiaires montre que f ne prend pas de valeurs supérieures à \frac{1}{2}. Il est donc nécessaire que :

    \[\forall t\in\left]-R,R\right[,\thinspace f\left(t\right)=\frac{1}{2}\left(1-\sqrt{1-4t}\right)\]

Maintenant, il est classique que pour \alpha\in\mathbb{R} fixé :

    \[\forall t\in\left]-1,1\right[,\thinspace\left(1+t\right)^{\alpha}=\sum_{n=0}^{\infty}\binom{\alpha}{n}t^{n}\]

et donc, pour tout t\in\left]-\frac{1}{4},\frac{1}{4}\right[ :

    \[\sqrt{1-4t}=\sum_{n=0}^{\infty}\binom{{\scriptstyle {1/2}}}{n}\left(-4t\right)^{n}\]

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

    \[f\left(t\right)=\sum_{n=1}^{\infty}\frac{1}{n}\binom{2n-2}{n-1}t^{n}\]

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 n\geqslant1 :

    \[P_{n}=\frac{1}{n}\binom{2n-2}{n-1}}\qquad\left(\spadesuit\right)\]


Posons, pour tout t\in\left]-\frac{1}{4},\frac{1}{4}\right[ :

    \[g\left(t\right)=\frac{1}{2}\left(1-\sqrt{1-4t}\right)=\sum_{n=0}^{\infty}a_{n}t^{n}\]

de sorte que a_{0}=0 et {\displaystyle a_{n}=\frac{1}{n}\binom{2n-2}{n-1},} pour tout n\geqslant1. On vérifie aisément que g\left(t\right)-t=g\left(t\right)^{2}, d’où l’on déduit (par unicité du développement en série entière) que :

    \[\forall n\geqslant2,\thinspace a_{n}=\sum_{k=0}^{n}a_{k}a_{n-k}\]

Comme a_{1}=1, il en résulte que les suites \left(a_{n}\right)_{n\geqslant1} et \left(P_{n}\right)_{n\geqslant1} sont confondues (elles vérifient la même “condition initiale” et la même formule de récurrence) et la formule (\spadesuit) est démontrée.

Pour finir, la formule de Stirling (voir cet article pour une preuve) dit que, lorsque n\rightarrow+\infty :

    \[n!\sim\left(\frac{n}{e}\right)^{n}\sqrt{2\pi n}\]

Il en résulte, en injectant ceci dans \left(\spadesuit\right), que :

    \[ \boxed{P{n}\sim\frac{4^{n-1}}{n^{3/2}\sqrt{\pi}}}\]

Si l’on note Q_{n} cet équivalent alors Q_{30}\simeq0,989\times10^{15}, à comparer à P_{30}\simeq1,002\times10^{15}.

Il serait injuste de terminer cette section sans signaler que les entiers \left(P_{n}\right)_{n\geqslant1} 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).

Eugène CATALAN (1814 – 1894)

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 E de cardinal n\geqslant1.

Pour commencer, vu qu’une opération sur E est une application de E^{2} dans E, il existe en tout :

    \[\boxed{n^{n^{2}}\text{ opérations sur }E}\]

Comme cela a été signalé à la section 1 :

il faut comprendre que n^{n^{2}} désigne n^{\left(n^{2}\right)}.

Cet entier prend rapidement des valeurs énormes.

Par exemple, sur un ensemble à 4 éléments, on peut définir 4^{16} c’est-à-dire 4 294 967 296 opérations !!

Et sur un ensemble à 10 éléments, le nombre d’opérations passe à 10^{100} (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é \mathcal{P} que peut éventuellement posséder une opération sur E. Le nombre d’opérations sur E possédant cette propriété sera noté N_{n}\left(\mathcal{P}\right).

Le calcul de N_{n}\left(\mathcal{P}\right) est plus ou moins aisé, selon la nature de \mathcal{P}.

Je vous propose d’obtenir une formule explicite pour N_{n}\left(\mathcal{P}\right) dans chacun des cas suivants :

  • \mathcal{P} = commutativité
  • \mathcal{P} = 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.

Partager cet article
  •  
  •  
  •  
  •