Nombre de Wedderburn-Etherington

En mathématiques, et notamment en combinatoire, les nombres de Wedderburn-Etherington forment une suite d'entiers dénombrant certains arbres binaires et des parenthésages commutatifs. Les problèmes combinatoires résolus par ces nombres sont proches de ceux résolus par les nombres de Catalan.

Ces nombres ont reçu le nom des mathématiciens Joseph Wedderburn (1882-1948) et Ivor M. H. Etherington (1908-1994).

Les dix premiers termes sont :

$n$	1	2	3	4	5	6	7	8	9	10
$a_n$	1	1	1	2	3	6	11	23	46	98

Ils forment la suite d'entiers Modèle:OEIS2C de l'OEIS.

Interprétations combinatoires

Schémas des $a_6=6$ arbres binaires à 6 feuilles et des 6 arbres faiblement binaires à 5 nœuds.

Le n-ième nombre de Wedderburn-Etherington est le nombre d'arbres binaires stricts enracinés à $n$ feuilles (chaque nœud interne possède deux fils), deux arbres étant considérés comme identiques dès que l'on peut passer de l'un à l'autre par des symétries par rapport à des axes verticaux issus des nœuds (sans ces identifications, on obtiendrait les nombres de Catalan). C'est aussi le nombre d'arbres (faiblement) binaires (chaque nœud interne possède un ou deux fils) ayant $n-1$ nœuds, avec les mêmes identifications que précédemment).

$a_n$ est aussi le nombre de façons d'interpréter $x^n$ pour une loi de composition interne notée multiplicativement non associative, mais commutative. Par exemple, pour $n=4$, $x^4$ possède deux interprétations : $x^2.x^2$ et $(x^2.x)x=(x.x^2)x=x(x.x^2)=x(x^2.x)$ (sans commutativité, il y a $C_3=5$ interprétations).

Relation de récurrence

Partant de $a_1=1$, les nombres de Wedderburn–Etherington peuvent être calculés à l'aide de la relation de récurrence :

$a_n=\frac{1}{2}\sum _{i=1}^{n-1}{a}_i{a}_{n-i}(+\frac{1}{2}{a}_{n/2}$ si $n$ est pair).

En termes d'interprétation de ces nombres comme comptant des arbres binaires enracinés à $n$ feuilles, la sommation dans la récurrence compte les différentes manières de partitionner ces feuilles en deux sous-ensembles, et de former un sous-arbre ayant chaque sous-ensemble comme feuilles. La formule pour les valeurs paires de $n$ est légèrement plus compliquée que la formule pour les valeurs impaires afin d'éviter de compter deux fois les arbres avec le même nombre de feuilles dans les deux sous-arbres.

Notons que la relation $a_n=\sum _{i=1}^{n-1}{a}_i{a}_{n-i}$ donnerait les nombres de Catalan : $a_n=C_{n-1}$.

Série génératrice

Soit

$a(x)=a_{1}x+\cdots +a_n{x}^n+\cdots =x+x^2+x^3+2x^4+\cdots$

la série génératrice des nombres de Wedderburn–Etherington. Elle satisfait à l'équation suivante :

$a(x)=x+\frac{1}{2}{a}^2(x)+\frac{1}{2}a(x^2)$.

Voir aussi

• Nombre de Catalan
• Nombre de Schröder-Hipparque