Semaine 22

Soit $E$ un ensemble fini de cardinal $n$.

1. 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 ?

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.

Soient $E$ un espace vectoriel de dimension $n$. Soit $f$ nilpotente. Soit $e \in E \backslash \{0\}$ et $r$ le maximum des $k \in \mathbb{N}^*$ tel que $(e, f(e), \cdots, f^{k-1}(e))$ soit libre. Montrer que $f^r(e) = 0$.

Soit $E$ un espace vectoriel de dimension $n$. Soit $F_1, \dots F_r$ des sous-espaces vectoriels de $E$.

On suppose que $\displaystyle\sum_{i=1}^r\mathrm{dim} F_i > (r-1)n$. Montrer que $\displaystyle\bigcap_{i=1}^r F_i \neq \{0\}$.

Bonus: En utilisant la solution de l'exercice, montrer que si $H_1, \dots, H_r$ sont des hyperplans, $\displaystyle\mathrm{dim} \bigcap_{i=1}^r H_i \geqslant n - r$.

On note $(F_n)_{n\in\mathbb{N}}$ la suite des nombres de Fibonacci. On souhaite montrer que pour tout $n \in \mathbb{N}$, il existe $k \in \mathbb{N}$, tel que $10^n$ divise $F_k$.

1. Montrer qu'il existe $i \neq j$ tel que $(F_i,F_{i+1})$ et $(F_j,F_{j+1})$ ont le même reste modulo $10^n$.
2. En déduire qu'en particulier, il existe $k$, $(F_k,F_{k+1})$ qui congruent tous les deux à $1$ modulo $10^n$.
3. Conclure.