(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

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