Lecture zen
*
Nombre de matrices symétriques à coefficients dans \(\{0,1\}\) et série entières
(Putnam, 1967).
Soit \(u_n\) le nombre de matrices \(n\times n\), symétriques à coefficients dans \(\{0,1\}\) avec exactement un \(1\) sur chaque ligne (on notera \(S_n\) cet ensemble). Avec \(u_0:=1\), montrer que \[u_{n+1}=u_n+nu_{n-1},\quad \sum_{n\geq 0}\dfrac{u_nx^n}{n!}=\exp{(x)+\dfrac{x^2}{2}}:=f(x).\]
Barre utilisateur
[ID: 2544] [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)
Nombre de matrices symétriques à coefficients dans \(\{0,1\}\) et série entières
Par Patrice Lassère le 9 novembre 2022 12:23
Par Patrice Lassère le 9 novembre 2022 12:23
Il y a une correspondance bijective entre \(S_n\) et l’ensemble des matrices \(M=((m_{ij}))\in S_{n+1}\) telles que \(m_{11}=1\). De même si \(i\geq 2\), il y aussi une correspondance bijective entre \(S_{n-1}\) et les matrices \(M\in S_{n+1}\) telles que \(m_{1i}=1\) (en effet \(M\) étant symétrique \(m_{i1}=1\), il n’y a donc que des zéros sur les autres coefficients des i-èmes lignes et colonnes : la donnée de \(M\) correspond donc à celle de la matrice \((n-1)\times(n-1)\) déduite de \(M\) en lui supprimant ses ièmes lignes et colonnes). De ces deux correspondances et puisque \(u_0=u_1=1\) on a \[u_{n+1}=u_n+nu_{n-1},\quad n\geq 1.\] Pour la seconde partie, il suffit de remarquer que \(f\) est développable en série entière \(\sum_nv_nx^n\) sur \(\mathbb R\), puis que les coefficients \(v_n\) satisfont à la même relation de récurrence que les \(u_n\) pour conclure facilement.
Documents à télécharger
Nombre de matrices symétriques à coefficients dans \(\{0,1\}\) et série entières
Télécharger
Télécharger avec les solutions et commentaires
L'exercice