Semaine 3

Soit \(n \in \mathbb{N}^*\), on construit des murs à l'aide de \(n\) briques posées au sol ou sur une autre brique.
Calculer \(u_n\) le nombre de tels murs à \(n\) briques.

On nomme mots bien parenthésés ou mots de Dyck les mots composés sur un alphabet constitués des deux lettres "(" et ")", où chaque parenthèse ouvrante est refermé, et chaque parenthèse fermante est ouverte précédemment. On considère l'ensemble des fonctions \(f : [\![0, 2n+1]\!] \to \mathbb{N}\), telles que \(\forall\ x,y,\, |x-y| = 1,\, |f(x) - f(y)| = 1\). Construire une bijection entre cet ensemble de fonctions et les mots bien parenthésés.

Deux candidats s'affrontent lors d'une élection. Le gagnant l'emporte avec \(a\) voix, le perdant obtient \(b\) voix. On représente le dépouillement à l'aide d'une ligne brisée joignant les points \((0,0)\) et \((a+b,a-b)\). L'ordonnée du point d'abscisse \(k\) représente l'écart entre les candidats après le dépouillement du \(k\) -ième bulletin.

1. Dénombrer les dépouillements possibles.
2. Montrer que le nombre de lignes brisées joignant \((1,1)\) à \((a+b,a-b)\) en passant par l'axe des abscisses est le même que celui des lignes brisées joignant \((1,-1)\) à \((a+b,a-b)\).
3. Combien y a-t-il de dénombrements différents au cours duquel le gagnant n'a jamais moins (ou autant) de voix que le perdant.

Soit \(E\) un ensemble fini de cardinal \(n\). Soit \(w_n\) le nombre de relations d'équivalence sur \(E\). Montrer que les entiers \(w_n\) vérifient la relation de récurrence \(\displaystyle w_{n+1} = \sum_{k=0}^n \binom{n}{k} w_k\).

Soit \(n\) droites du plan \(\mathbb{R}^2\), dont aucune paire n'est deux à deux parallèles. Combien y a-t-il de triangles formés par ces droites ?

Soit \(n \in \mathbb{N}^*\). Montrer que, \[ \sum_{k \text{ pair}} \binom{n}{k} = \sum_{k \text{ impair}} \binom{n}{k} \]