Lecture zen
*
Combinatoire et matrices
Soient \(A_0=B_0=((1))\in M_1(\mathbb R)\). Pour \(n\geq 1\) on définit les suites de matrices par \[A_n=\begin{pmatrix}A_{n-1}&A_{n-1}\\A_{n-1}&B_{n-1}\end{pmatrix},\quad \rm{et}\quad B_n=\begin{pmatrix}A_{n-1}&A_{n-1}\\A_{n-1}& 0\end{pmatrix}\in M_{2n}(\mathbb R).\] Montrer que \[S(A_n^{k-1})=S(A_k^{n-1}),\forall\,n,k\in\mathbb N^\star\] avec \(S(M)=\sum_{1\leq i,j\leq n}m_{ij}\) où \(M=((m_{ij}))\).
Barre utilisateur
[ID: 2560] [Date de publication: 9 novembre 2022 12:23] [Catégorie(s): Combinatoires et probabilités ] [ Nombre commentaires: 1] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 1 ] [Auteur(s): Patrice Lassère ]Solution(s)
Solution(s)
Combinatoire et matrices
Par Patrice Lassère le 9 novembre 2022 12:23
Par Patrice Lassère le 9 novembre 2022 12:23
L’astuce (redoutable) consiste à donner un sens combinatoire à la quantité \(S(A_n^{k-1})\). Pour cela soit \(T\) un tableau \(n\times k\) à coefficients \(0\) et \(1\) (i.e. un élément de \(M_{n,k}(0,1)\)) vérifiant la propriété suivante : il n’existe dans \(T\) aucune sous matrice \(2\times 2\) constituée uniquement de \(1\) et soit \(F_{n,k}\) le nombre de tels tableaux.
Chaque ligne d’un tableau correspond à un entier entre \(0\) et \(2^n-1\) écrit en base \(2\). \(F_{n,k}\) est donc le nombre de \(k\)-uplets d’entiers dont toute paire d’entiers consécutifs correspond à un tableau \(n\times 2\) sans sous-matrice . \(2\times 2\) constituée uniquement de \(1\).
Soient \(\overline{i_n i_{n-1}\dots i_1},\ \overline{j_nj_{n-1}\dots j_1}\) les écritures en base \(2\) de deux entiers \(i,j\in\{0,\dots,2^n-1\}\). Deux cas sont à envisager :
-Si \(i_nj_n=0\) alors \(\overline{i_n i_{n-1}\dots i_1}\) et \(\overline{j_nj_{n-1}\dots j_1}\) sont consécutifs si et seulement si \(\overline{ i_{n-1}\dots i_1}\) et \(\overline{j_{n-1}\dots j_1}\) le sont.
-Si \(i_nj_n=1\) alors \(\overline{i_n i_{n-1}\dots i_1}\) et \(\overline{j_nj_{n-1}\dots j_1}\) sont consécutifs si et seulement si \(i_{n-1}j_{n-1}=0\) et \(\overline{ i_{n-2}\dots i_1}\) et \(\overline{j_{n-2}\dots j_1}\) le sont.
Ainsi
Documents à télécharger
L'exercice