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}\)\(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

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