Forum des amateurs de maths
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.


Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  RechercherRechercher  Dernières imagesDernières images  S'enregistrerS'enregistrer  Connexion  
Le deal à ne pas rater :
(CDAV) Foire aux vins : -20% dès 99€ d’achat
Voir le deal

 

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

Aller en bas 
3 participants
AuteurMessage
elhor_abdelali
Expert grade1
elhor_abdelali


Masculin Nombre de messages : 488
Age : 61
Localisation : Maroc.
Date d'inscription : 24/01/2006

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptyVen 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 ? farao
Revenir en haut Aller en bas
http://www.ilemaths.net/forum_superieur-4.php
Bison_Fûté
Expert sup
Bison_Fûté


Masculin Nombre de messages : 1595
Age : 64
Date d'inscription : 11/02/2007

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Re: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptySam 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.
Revenir en haut Aller en bas
mathman
Modérateur



Masculin Nombre de messages : 967
Age : 35
Date d'inscription : 31/10/2005

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Re: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptySam 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 Smile


Dernière édition par le Sam 24 Fév 2007, 14:33, édité 1 fois
Revenir en haut Aller en bas
elhor_abdelali
Expert grade1
elhor_abdelali


Masculin Nombre de messages : 488
Age : 61
Localisation : Maroc.
Date d'inscription : 24/01/2006

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Re: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptySam 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 Question ) .
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 ) farao ( à suivre )
Revenir en haut Aller en bas
http://www.ilemaths.net/forum_superieur-4.php
elhor_abdelali
Expert grade1
elhor_abdelali


Masculin Nombre de messages : 488
Age : 61
Localisation : Maroc.
Date d'inscription : 24/01/2006

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Re: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptySam 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 {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 farao (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 ? affraid
Revenir en haut Aller en bas
http://www.ilemaths.net/forum_superieur-4.php
mathman
Modérateur



Masculin Nombre de messages : 967
Age : 35
Date d'inscription : 31/10/2005

Un dénombrement dans M[size=9]n[/size](IR) Empty
MessageSujet: Re: Un dénombrement dans M[size=9]n[/size](IR)   Un dénombrement dans M[size=9]n[/size](IR) EmptyDim 25 Fév 2007, 21:45

Ok. Smile
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 ? affraid
Hmm, je ne suis pas sûr qu'il y ait une formule explicite.
Mais on peut encore aller faire un tour sur sloane..
Revenir en haut Aller en bas
Contenu sponsorisé





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

Revenir en haut Aller en bas
 
Un dénombrement dans M[size=9]n[/size](IR)
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Combinatoire-
Sauter vers: