Vote et Chemin de Dyck

Comprendre la notion de chemins de Dyck, savoir les dénombrer et décrire la bijection avec les arbres binaires.

Sommaire :

  1. Définition d’un chemin de Dyck et dénombrement
  2. Programme de dessin de chemin de Dyck
  3. Bijection avec les arbres binaires 
  4. Application concrète 

Le chemin de Dyck est une structure combinatoire apparaissant dans de nombreuses applications informatiques et mathématiques. La triangulation des polygones, le dénombrement d’arbres binaires entiers et la description des mots correctement parenthésés étant certaines d’entre elles. Nous allons particulièrement nous intéresser à cette dernière : le parenthésage pour illustrer les mots de Dyck. 

En effet, lors de la compilation il est très important de déterminer si une expression est correctement parenthésée. Il faut qu’il y ait autant de parenthèses ouvrantes que de fermantes et qu’elles soient disposées de manière non aléatoire et cohérente. Le principe est équivalent à celui des mots de Dyck. 

Nous allons dans un premier temps définir la notion de chemin de Dyck ainsi qu’une façon de les dénombrer. Ensuite nous allons écrire un programme permettant de déterminer si une expression est correctement parenthésée puis de dessiner le chemin de Dyck qui lui est associé. Par la suite nous étudierons la bijection entre chemin de Dyck et arbre binaire. Enfin nous aborderons une application concrète des chemins de Dyck, le problème du scrutin.

Que sont les chemins de Dyck, comment peut-on les dénombrer et en quoi sont-ils équivalents à un arbre binaire ? 

1- Définition d’un chemin de Dyck et dénombrement

DÉFINITION MOT DE DYCK

Pour comprendre la notion de chemin de Dyck nous allons d’abord expliquer celle de « mot de Dyck ». En effet cette notion peut s’expliquer et s’illustrer avec des exemples tout en lettres sans représentation graphique. 

Un mot de Dyck de taille 2n (son nombre de caractères = 2n) est composé de deux caractères distincts répétés chacun n fois. Pour un mot de Dyck composé de deux caractères A et B, si on commence la lecture du mot par la gauche vers la droite et que le mot commence par le caractère A, le nombre de A est toujours supérieur ou égal au nombre de B, peu importe l’emplacement dans le parcours, sauf à la fin où ils sont forcément égaux. 

La longueur d’un mot de Dyck est nécessairement paire.

Exemple :  parcourons le mot de Dyck AABAABBABB 

Etape 1 : A|ABAABBABB dans la partie délimitée il y a 1 A et 0 B

Etape 2 : AA|BAABBABB dans la partie délimitée il y a 2 A et 0 B

Etape 3 : AAB|AABBABB dans la partie délimitée il y a 2 A et 1 B

Etape 6 : AABAAB|BABB dans la partie délimitée il y a 4 A et 2 B

Etape 9 : AABAABBAB|B dans la partie délimitée il y a 5 A et 4 B

Etape 10 : AABAABBABB| dans la partie délimitée il y a 5 A et 5 B

On remarque que le principe des mots de Dyck est exactement le même que celui des expressions correctement parenthésées. Remplaçons le caractère ‘A' par la parenthèse ouvrante ‘(‘ et le caractère ‘B’ par la parenthèse fermante ‘)’ et on obtient pour l’exemple précédent le mot suivant : « ( ( ) ( ( ) ) ( ) ) ».

Reconnaître un mot de Dyck revient à reconnaître une expression correctement parenthésée. 

Voici un programme en JAVA qui reconnaît un mot de Dyck en utilisant une pile. Lors de la lecture du mot caractère par caractère de la gauche vers la droite, on « push » un caractère ouvrant et on « pop » la pile lorsque l’on rencontre un caractère fermant.

PROGRAMME DE RECONNAISSANCE D'UN MOT DE DYCK 

Le programme suivant est en Java, la fonction analyseMot détermine si un mot donné en paramètre du constructeur CheminDyck est un mot de Dyck ou non. La fonction utilise une pile ; on y 'push' une lettre A et on la retire puis on fait une vérification à l'aide de la fonction match quand on rencontre une lettre B.

import java.util.*;

public class CheminDyck {
	
	private boolean isDyck ; // oui ou non mot de Dyck
	private final String s; // mot
	
	public CheminDyck (String s){
		this.s = s;
		this.isDyck = analyseMot();
	}
	
	public boolean analyseMot(){
                if (!s.contains('('+"")||!s.contains(')'+"")) {
			return false;
		}
                // si on ne trouve pas les caractères donnés en paramètre du constructeur dans s, cela faussera les résultats

		Stack<Character> pile = new Stack<Character>();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i)=='(') {
				pile.push('(');
			} else if (s.charAt(i)==')') {
				if (pile.isEmpty()) return false;
				Character c = (Character)pile.pop();
				if (!match(c.charValue(), s.charAt(i))) return false;
			}
		}
		if (pile.isEmpty()){
		 return true;
		}else {
		 return false ;
		}
	}	

	
	public boolean match(char g, char d) {
		if (g=='(') {
			return d==')';
		} else {
			return false;
		}
	}
}

DÉFINITION CHEMIN DE DYCK 

Un chemin de Dyck est donc la représentation graphique d’un mot de Dyck de taille 2n où : 

  • les traits sont sur un quadrillage de taille n par n
  • un segment vers le haut représente un caractère ouvrant ‘A’
  • un segment vers la droite représente un caractère fermant ‘B’

(ou vice-versa)

  • le chemin commence au coin inférieur gauche et finit au coin supérieur droit et ne franchit jamais la diagonale principale bas-gauche/haut-droit.
Figure 1 : Tous les chemins de Dyck possible pour un mot de taille 8

DÉNOMBREMENT

Le chemin de Dyck étant une structure combinatoire de la même manière qu’un graphe est une structure combinatoire, on peut les dénombrer. La solution est donnée par les nombres de Catalan.

Un n^e nombre de Catalan ^(^1^) correspond au nombre de mots de Dyck de longueur  2n .

2n est la longueur du mot et n*n est la dimension de la grille.

  • Combien existe t-il de chemins reliant le point de départ 'D' (en bas à gauche ) au point d'arrivée 'A' (en haut à droite) et n'étant composés que de déplacements vers le haut ou vers la droite ?

On a  2n déplacement (dont n vers le haut et n vers la droite ) Alors \begin{pmatrix}2n \\n\end{pmatrix} correspond à tous les chemins possibles reliant D à A.
Calculons maintenant le nombre de chemins qui, si on trace une diagonale reliant D à A , coupent cette diagonale: en effet, un chemin invalide, donc, qui coupe la grande diagonale, touche en au moins un point, x, la diagonale [αβ] juste en dessous. Si on considère un nouveau chemin, obtenu à partir du précédent. On garde la partie liant D à x, et on prend le symétrique de la partie liant x à A par rapport à [αβ]. Ce nouveau chemin relie alors D à A’, symétrique de A par rapport à [αβ]. On peut alors voir qu’il y a autant de mauvais chemins liant D à A que de chemins liant D à A’.

On a une succession de 2n déplacements comptant n+1 déplacements vers la droite. Il y a donc n+1 parmi 2n chemins liant D à A’, soit tout autant que de mauvais chemins liant D à A.

Alors \begin{pmatrix}2n \\n+1\end{pmatrix} correspond à tous les mauvais chemins reliant D à A.

Pour trouver combien il y a de chemin de Dyck pour un mot de taille  2n on soustrait donc les mauvais chemins à la totalité des chemins possible.

\begin{pmatrix} 2n \\n\end{pmatrix}-\begin{pmatrix}2n \\n+1\end{pmatrix}

\iff \begin{pmatrix}2n \\n \end{pmatrix} - \left ( \frac{n}{n+1} \right )\begin{pmatrix}2n \\n \end{pmatrix}

\iff \begin{pmatrix}2n \\n \end{pmatrix} \left  (\left( \frac{-n}{n+1} \right )+1)\right)

\iff \begin{pmatrix}2n\\n \end{pmatrix} \frac{1}{n+1}

\begin{pmatrix}2n\\n \end{pmatrix} \frac{1}{n+1} est donc la formule qui donne le nombre de chemin de Dyck de taille 2n .

^(^1^) : "En mathématiques, et plus particulièrement en combinatoire, les nombres de Catalan forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement, impliquant souvent des objets définis de façon récursive. Ils sont nommés ainsi en l'honneur du mathématicien belge Eugène Charles Catalan (1814-1894).
Le nombre de Catalan d'indice n, appelé n-ième nombre de Catalan, est défini par C_n =\begin{pmatrix}2n\\n \end{pmatrix} \frac{1}{n+1} = \frac {(2n)!}{(n+1)!n!} .
Les dix premiers nombres de Catalan (pour n de 0 à 9) sont : 1, 1, 2, 5, 14, 42, 132, 429, 1 430 et 4 862 . "

2- Programme de dessin de Chemin de Dyck

  • Télécharger le fichier .zip suivant
  • Compiler les fichiers et exécuter DessinDyck.java

3- Bijection avec les arbres binaires

Figure 2 : Chemin de Dyck, mot bien parenthésé et arbre binaire associé

Pour dessiner l’arbre binaire complet (2n arêtes) correspondant à un chemin de Dyck donné, il faut procéder comme suit : (on se base sur l’exemple donné en figure 2)

  • un segment vers le haut (qui correspond à un caractère ouvrant) représente dans l’arbre un fils gauche
  • un segment vers la droite (qui correspond à un caractère fermant) représente dans l’arbre un fils droit
Figure 3 : Arbre binaire et les parenthèses correspondant à ses fils

Pour trouver le mot de Dyck correspondant à un arbre binaire complet il faut faire un parcours préfixe de l’arbre. 

La racine est un caractère vide et on lui ajoute un caractère ouvrant lors de la découverte d’un fils gauche et un caractère fermant lors de la découverte d’un fils droit. 

On peut passer d'un arbre binaire complet (2n arêtes) à un chemin ou mot de Dyck et vice versa car ils ont les mêmes caractéristiques.

4- Application concrète

On va maintenant aborder le problème du scrutin dans le cas d’un vote entre deux candidats qui se termine en une égalité de bulletins.

Imaginons que lors du deuxième tour d’une élection, Alice et Bob terminent à égalité, pourtant au long de l’élection, Alice était en tête. Qu’elle est la probabilité qu’une telle situation se produise ?

La situation donnée est la suivante : à la fin du dépouillement des votes entre deux concurrents, on a une égalité totale de votes alors que l'un des concurrents était toujours en tête (autrement dit le second concurrent n'était jamais en tête). On cherche donc la probabilité P de la situation suivante : un des candidats est toujours en tête lors du dépouillement et arrive à ex aequo avec le second concurrent.

On remarque immédiatement que cette situation s'apparente à un chemin de Dyck : si Alice est le caractère ouvrant A et Bob est le caractère fermant B et que le dépouillement est la chaîne de caractère, alors cette chaîne de caractère est un mot de Dyck. Alice est en tête tout au long du vote et en effet il y a toujours plus ou autant de A que de B lors du parcours du mot.

On note p le nombre de vote obtenu par le gagnant et q le nombre de vote obtenu par le perdant. Dans notre problème les deux concurrents arrivent ex aequo, on a donc p=q . On parle d’un vote à 2p bulletins. 

La probabilité P d'une telle situation est naturellement donnée par le nombre de chemin de Dyck de taille 2p :

\begin{pmatrix}2p\\p \end{pmatrix} \frac{1}{p+1}

On peut également partir de la probabilité donnée par le problème du scrutin au sens large où la probabilité recherchée est celle où le vainqueur est toujours en tête lors du dépouillement, ou à égalité avec le perdant.

Elle est donnée par la formule \frac{p-q+1}{p+1}\begin{pmatrix}p+q\\p\end{pmatrix}

Or en remplaçant q par p puisqu'il n'y a pas de perdant on trouve facilement la formule \begin{pmatrix}2p\\p \end{pmatrix} \frac{1}{p+1} .

En conclusion on remarque que les chemins de Dyck sont une structure combinatoire très utile pour les problèmes mathématiques ou informatiques par exemple mais les nombres de Catalan qui permettent de dénombrer les chemins de Dyck donnent la solution du dénombrement d'un nombre important de structures combinatoires. Parmi elles on note entre autres (en plus des chemins de Dyck et des arbres binaires) les triangulations d'un polygone, les arbres planaires et les partitions non croisées.

Bibliographie

3 Cliquer pour recommander cet article