Un dénombrement dans M[size=9]n[/size](IR)

Bonsoir ;
Combien y'a-t-il dans Mn(IR) de matrices M à coefficients dans {0,1} et telle que M²=0 ?

Bonjour Abdelali !!
Je n'ai pas résolu ton pb !! Je pense seulement que l'on pourrait démarrer un embryon de preuve en utilisant la Base Canonique de M(IR,nXn) , les fameuses matrices Eij ( avec des zéros partout et un à la ième ligne , jème colonne ) d'autant plus que l'on connait la règle de multiplication des Eij : Eij*Ekl=Symbole de Kronecker(j,k).Eil ???? LHASSANE

PS: je vais y réfléchir un peu + ce Week-End !!!!! Bon WE à Toi!
Toute matrice M candidate est combinaison linéaire des matrices élémentaires Eij avec des coefficients 0 ou 1.

Intéressant.
On dirait de la théorie des graphes.

On compte des graphes à n sommets tels qu'il n'y ait pas de chemins de longueur 2. (des graphes orientés)
Donc on partitionne l'ensemble des sommets {1, 2, ..., n} en deux classes :
les sommets A où une flèche s'arrête et les sommets B où aucune flèche ne s'arrête.
Alors les flèches vont de B vers A, et chaque sommet de A doit être la fin d'une flèche.
Ce devrait être une somme binomiale.
\sum_k (n blib k) * qqch(n, k) ((a blib b) est le coefficient binomial)
k est le cardinal de A; il y a (n blib k) pour partitionner {1, 2, ..., n} en un ensemble à k éléments et un ensemble à (n-k) éléments; qqch(n, k) est le nombre de façons de mettre les flèches pour une telle partition :
pour chacun des k sommets de A on doit choisir à partir de quels sommets de B on fait une flèche vers ce sommet; il y a 2^{n-k}-1 façons de faire ça. (-1 parce qu'il nous faut au moins une flèche)
Donc :
\sum_k (n blib k) * (2^{n-k}-1)^k.

Il doit y avoir une erreur bête quelque part car ça n'a pas l'air d'être une bonne réponse.. quel est ton résultat?

EDIT1 :
f(1)= 1
f(2)= 3
f(3)= 13
f(4)= 87
f(5)= 841
Si tu ne connais pas la réponse mais que tu as calculé quelques valeurs on peut comparer.

EDIT2: en fait, ça a l'air d'être correct; cf. http://www.research.att.com/~njas/sequences/A001831

Bonjour ;
Oui mathman le résultat est bon mais je n'ai pas bien compris ton explication ,
( je dois avouer que la théorie des graphes ne m'est familière que par le nom ) .
J'expose alors mon raisonnement :
Une matrice M = (mij) de Mn(IR) qui est à coefficients dans {0,1}
est totalement déterminée par la donnée de la partie SM = {(i,j)£{1,..,n}² / mij=1}
En faisant appel à la décompostion canonique de M ( comme l'a présenti BOURBAKI )
on s'aperçoit que la condition M² = 0 est équivalente à dire que les deux projections de SM sont disjointes .
Ainsi le problème se ramène à dénombrer les parties de {1,..,n}² à projections disjointes
( bien entendu j'entends par projections les deux applications (i,j) ---> i et (i,j) ---> j ) ( à suivre )

On va maintenant voir combien il y'en a de telles parties :
Hormis la partie vide de {1,..,n}² qui est trivialement à projections disjointes ,
une partie non vide S de {1,..,n}² à projections disjointes peut se construire de la manière suivante ,
* on commence par choisir une partie {i1,..,ik} à k éléments de {1,..,n} (k >= 1)
* on remarque ensuite que {j£{1,..,n} / (i1,j)£S} doit être une partie non vide de {1,..,n}\{i1,..,ik}
et on en déduit le nombre cherché :
Sum_{0=<k=<n} C_{n}^{k}.(2^{n-k}-1)^k (sauf erreur bien entendu)

Une question ouverte :
Combien y'a-t-il dans Mn(IR) de matrices M à coefficients dans {0,1} et telle que M^n=0 ?

Ok.

elhor_abdelali a écrit:

Une question ouverte :
Combien y'a-t-il dans Mn(IR) de matrices M à coefficients dans {0,1} et telle que M^n=0 ?

Hmm, je ne suis pas sûr qu'il y ait une formule explicite.
Mais on peut encore aller faire un tour sur sloane..