Bonsoir;
Soit un entier supérieur ou égal à .
Pour toute partie de on peut définir ses deux projections c'est à dire ses images respectives par les deux applications:
et .
Combien y'a-t-il de parties de à projections disjointes ?
Salut,
tu peux donner un exemple pour n petit?
Si je prend n=5,S={1,3}*{2,4} alors qu'est ce que tu entends par projections disjointes?
Bonsoir
Cauchy > si j'ai bien compris, dans ton exemple, les deux projections sont {1,2} et {3,4}
En fait, lorsque elhor parle de projection disjointes, je pense que cela signifie que les images des deux projections sont disjointes.
Kaiser
Oui c'est exactement ça kaiser , la partie de Cauchy est un exemple de parties de à projections disjointes et si je ne me trompe il y'en a au total
Je vais peut etre dire une betise mais une partie de s'obtient comme le produit de deux parties A et B de ce qui donne parties.
Ca me parait plutot étrange qu'on en ait 841 à projections disjointes vu qu'en dénombrant par exemple les parties A*B avec A et B qui contiennent 1 on en a déja plus de 200.
Bonjour
Cauchy > je pense que ce n'est pas aussi simple que ça.
Une partie de cet ensemble n'est pas forcément un produit.
En effet, n'est pas un produit car sinon, on aurait les éléments (1,1) et (2,0) ce qui n'est pas le cas.
Kaiser
Oui en fait il y a plutot éléments.
J'ai réfléchi un peu mais j'ai des horribles formules pas vu l'astuce encore
Bonsoir Cauchy et kaiser ;
Hormis la partie vide de qui est trivialement à projections disjointes , une partie non vide de à projections disjointes peut se construire de la manière suivante:
Pour on commence par choisir une partie à éléments de (cette partie n'est en fait que l'image de par la première projection).
En suite on remarque que pour que soit à projections disjointes il faut et il suffit que pour tout
l'ensemble soit une partie non vide de
Ce raisonnement (combinatoire) conduit à la formule:
Remarque:
Ce nombre est aussi celui des matrices de qui sont à coefficients dans et telles que . (sauf erreur bien entendu)
Bonjour
Je mets quand même ce que j'avais préparé avant de me connecter, d'abord parceque à première vue on n'a pas les mêmes bornes dans la somme, mais ça doit coïncider puisque nous avons la même valeur,
mais surtout, parceque j'espérais une autre formule!
D'abord, il y a le vide.
Soit A une partie non vide vérifiant les conditions et soit k=card(p1(A)). (Donc 1kn-1)
Pour chaque a de p1(A), l'ensemble des b tels que (a,b) A est une partie non vide du complémentaire de p1(A), donc
2n-k-1 possibilités pour chaque a de p1(A) et (2n-k-1)k pour les parties qui ont la même projection que A.
Comme il y a Cnk parties dont la projection a k éléments, ma formule est:
ce qui donne bien 841 pour n=5.
Le degré de mochitude sur l'echelle de kaiser de cette formule étant très élevé et mes tentations d'amélioration ayant fait plus de mal que de bien,
j'espère que l'un de vous a obtenu une formule plus jolie, ce qui fournirait en prime une identité "remarquable".
Salut camélia
En fait, tu as trouvé le même résultat qu'elhor.
En effet, ton 1 correspond à celui d'elhor pour k=0 et le terme d'ordre n de la somme d'elhor est nulle.
Donc finalement, vous avez trouvé exactement la même chose.
Kaiser
P.S :
Salut kaiser
Je me doutais bien d'un truc comme ça! Je l'ai mis d'abord pour comprendre, et ensuite j'étais trop fière d'avoir réussi un cadre pour le laisser se perdre... (Comment fait-on du rouge?)
En , tu écrire \red{} et tu mets entre accolades ce que tu veux mettre en couleur.
Plus généralement, pour mettre de la couleur tu écris \couleur{} ou "couleur" est le nom de la couleur mais en anglais bien sûr.
Ici, ça sera \Large\red\fbox{\fbox{1+\sum_{k=1}^{n-1}C_n^k\(2^{n-k}-1)^k}}
ce qui donne
Kaiser
en fait même sans accolades ça marche aussi !
Les accolades c'est simplement pour sélectionner uniquement ce que tu veux mettre en couleur.
Kaiser
Bravo à elhor et Camélia
elhor pour ta remarque choisir M revient à choisir les qui valent 1 et alors si on note on a:
ssi ssi on somme sur le vide ssi A est à projections disjointes.
P.S:comment on fait pour passer à la ligne quand on indice une somme?
C'est moche et pas tres compréhensible vous moquez pas
Bien vu cauchy ;
Si est à coefficients dans alors :
.
Et comme la donnée de détermine totalement et vis versa on conclut qu'il y'a autant de telles matrices que de parties de à projections disjointes .
Une question ouverte :
Combien y'a-t-il dans de matrices nilpotentes à coefficients dans ?
Ok je vais essayer de réfléchir à ta question
Est-ce que t'as trouvé un contre-exemple sur le topic avec les points fixes des fonctions qui commutaient?
Bonjour, elhor, Camélia et Cauchy
J'ai trouvé, mais ça n'a pas été sans mal.
Après avoir galéré un bon moment, je me suis décidé à utiliser Maple,ce qui m'a permis d'obtenir le nombre de matrices nilpotentes pour n=3 et n=4 (respectivement 25 et 543).
Je suis allé sur l' "Encyclopedia of integer sequences" et j'ai tapé la suite 3,25,543. J'ai eu la réponse immédiate. Une seule suite convenait, définie comme le nombre de digraphes acycliques avec n sommets. Une petite recherche internet sur les digraphes acycliques m'a permis de voir qu'ils étaient en bijection avec l'ensemble des matrices nilpotentes de M_n(R), à coefficients dans {0,1}. La formule de récurrence permettant d'obtenir les a_n:
Une fois qu'on a la formule de récurrence, la démonstration est moins difficile à trouver. Je vous laisse chercher un petit peu, avant de la donner.
Pioché également sur l'Encyclopedia of integer sequences:
a_n est aussi le nombre de matrices de M_n(R) à coefficients dans {0,1}, ayant toutes ses valeurs propres positives (résultat démontré en 2004)
Un Hop!
Pour que Camélia , Cauchy et Kaiser puissent lire la contribution de perroquet (et pour tous les intéressés bien entendu)
On notera e_1,..,e_n la base canonique de R^n, A_n l'ensemble des éléments nilpotents de M_n(R), à coefficients dans {0,1}, et a_n le cardinal de A_n. Le but est de trouver une formule de récurrence permettant de calculer a_n.
Propriété
Un élément de A_n a au moins une colonnne nulle
Démonstration:
Supposons que toutes les colonnes d'un élément M de A_n soient non nulles. Alors, si x est un élément non nul de R^n dont les coordonnées sont positives, Mx est un élément non nul de R^n dont les coordonnées sont positives. On en déduit par récurrence que M^ke_1 est un vecteur non nul de R^n, dont toutes les coordonnées sont positives. En particulier, M^k n'est jamais la matrice nulle et M n'est doncpas nilpotente.
Notations
On notera E_{i,n} l'ensemble des éléments de A_n dont la i-ème colonne est nulle. A_n est donc la réunion des E_{i,n}, i appartenant à {1,...,n}. On rappelle que:
On applique donc cette formule aux ensembles E_{i,n}, et il nous faut évaluer le cardinal de . Cet ensemble est l'ensemble des éléments de A_n dont les colonnes i_1,...,i_k sont nulles. Toutes les colonnes jouent un rôle symétrique, et donc,les ensembles (avec k fixé) ont même nombre d'éléments. Pour calculer ce nombre, on étudiera le cas où les colonnes i_1,...,i_k sont les k dernières colonnes.
Un élément de A_n dont les k dernières colonnes sont nulles peut s'écrire sous la forme , où M est un élément de A_{n-k} et où N peut être choisie quelconque (on rappelle que ). N a n-k colonnes et k lignes et ses coefficients peuvent être choisis dans {0,1}. Le nombre des matrices de A_n dont les k dernières colonnes sont nulles est donc égal à , formule qui reste valable pour k=n, avec la convention a_0=0.
Voilà, c'est terminé:
Bonjour à tous! Bravo perroquet!
C'est là que l'on sent la différence de génération... je n'aurais jamais eu l'idée de taper trois nombres dans google!
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :