Liste (mathématiques)

Une liste, en mathématiques, est une collection d'éléments rangés dans un ordre précis. Plus formellement^[1],

Soit ${\displaystyle X}$ un ensemble. On définit les produits cartésiens de ${\displaystyle X}$ par récurrence par ${\displaystyle X^{0}=\{\emptyset \}{\text{(la liste vide)}};\,X^{1}=X;\,X^{n+1}=X\times X^{n},n>0}$

Alors ${\displaystyle ListX\doteq \cup _{n\geq 0}X^{n}}$ est l'ensemble de toutes les listes finies d'éléments de ${\displaystyle X}$.

On écrit aussi ${\displaystyle X^{*}}$au lieu de ${\displaystyle ListX}$, en utilisant l'étoile de Kleene.

On note ${\displaystyle L=(x_{1},x_{2},...,x_{k})}$ la liste L contenant les éléments de ${\displaystyle x_{i}}$ où ${\displaystyle i\in [1;k]}$; l'ordre d'apparition des éléments est ${\displaystyle x_{1},...,x_{k}}$.

La notion de liste, ou encore de mot, est donc équivalente à celle d'uplet.

Ainsi, on a les propriétés suivantes :

• Pour une liste L, tout élément ${\displaystyle x}$ possède un unique indice ${\displaystyle k\in \mathbb {N} }$ qui correspond à sa place dans la liste (k-ième terme)
• 2 listes sont égales si elles ont exactement les mêmes éléments, rangés dans le même ordre, i.e. ${\displaystyle (1,2,3)\neq (1,3,2)\quad {\text{et}}\quad (1,2,4)\neq (1,2,3)}$
• 2 listes ont le même cardinal si elles ont le même nombres d'éléments.