| | Un dénombrement dans M[size=9]n[/size](IR) | |
| | Auteur | Message |
---|
elhor_abdelali Expert grade1
Nombre de messages : 488 Age : 61 Localisation : Maroc. Date d'inscription : 24/01/2006
| Sujet: Un dénombrement dans M[size=9]n[/size](IR) Ven 23 Fév 2007, 21:02 | |
| Bonsoir ; Combien y'a-t-il dans Mn(IR) de matrices M à coefficients dans {0,1} et telle que M²=0 ? | |
| | | Bison_Fûté Expert sup
Nombre de messages : 1595 Age : 64 Date d'inscription : 11/02/2007
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) Sam 24 Fév 2007, 09:47 | |
| 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. | |
| | | mathman Modérateur
Nombre de messages : 967 Age : 35 Date d'inscription : 31/10/2005
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) Sam 24 Fév 2007, 14:30 | |
| 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
Dernière édition par le Sam 24 Fév 2007, 14:33, édité 1 fois | |
| | | elhor_abdelali Expert grade1
Nombre de messages : 488 Age : 61 Localisation : Maroc. Date d'inscription : 24/01/2006
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) Sam 24 Fév 2007, 18:53 | |
| 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 = (m ij) de M n(IR) qui est à coefficients dans {0,1} est totalement déterminée par la donnée de la partie S M = {(i,j)£{1,..,n}² / m ij=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 S M 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 ) | |
| | | elhor_abdelali Expert grade1
Nombre de messages : 488 Age : 61 Localisation : Maroc. Date d'inscription : 24/01/2006
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) Sam 24 Fév 2007, 21:40 | |
| 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 {i 1,..,i k} à k éléments de {1,..,n} (k >= 1) * on remarque ensuite que {j£{1,..,n} / (i 1,j)£S} doit être une partie non vide de {1,..,n}\{i 1,..,i k} 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 ? | |
| | | mathman Modérateur
Nombre de messages : 967 Age : 35 Date d'inscription : 31/10/2005
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) Dim 25 Fév 2007, 21:45 | |
| 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.. | |
| | | Contenu sponsorisé
| Sujet: Re: Un dénombrement dans M[size=9]n[/size](IR) | |
| |
| | | | Un dénombrement dans M[size=9]n[/size](IR) | |
|
| Permission de ce forum: | Vous ne pouvez pas répondre aux sujets dans ce forum
| |
| |
| |