Forum de mathématiques - Bibm@th.net

Bonjour,

[tex]3^N[/tex] pour la première affirmation, une coquille je pense ( 3 possibilités indépendantes pour chacun des N points ).

Alain

Bonjour,

Je m'intéressais juste au nombre de  relations anti-symétriques Et réflexives sur un ensemble à n éléments, pour pouvoir
ensuite dire que le nombre de relations d'ordre est justement  inférieur à ce nombre.

On décrit complètement une relation anti-symétriques ( pour les points hors-diagonales, le choix sur la diagonale est arbitraire, sauf cas de réflexivité où on aura un unique choix -> tout ) en disant que pour chaque point du produit cartésien au-dessus,
soit il est dans le graphe (mais pas son symétrique ) , soit il n'y est pas  ni son symétrique, soit il n'y est pas mais son symétrique est dedans. On a 3 choix à effectuer pour chaque point au-dessus de la diagonale, d'où la formule car l'ensemble de tous ces choix sont différents et il est en bijection avec ce qu'on cherche.
Pour chacun des points P(x,y) au-dessus de la diagonale ( pour fixer les idées, on pourrait raisonner avec dessous la diagonale ) :

Ou bien:

- non P(x,y) et non P( y, x )
- p(x, y ) et non P(y,x)
- non p(x,y) et P(y,x)

soit effectivement [tex]3^{n(n-1)/2}[/tex] configurations.

Le choix de choix points diagonaux revient à [tex]2^n[/tex], nombre de parties parmi n points, il est indépendant des autres choix.
En cas de réfléxivité imposée, on est obligé de prendre un seul choix, la diagonale pleine...

Alain

Plus précisément le nombre de relations d'ordre est inférieur à[tex]3^{n(n-1)/2}[/tex] car le choix des points diagonaux est unique (tous) avec la réfléxivité... Avec n =3 on a bien 19  plus petit que 27...
Peut-être peut-on améliorer cette majoration, mais ça ne me saute pas aux yeux..

Alain

Bonjour,

La question n'est pas facile dans le cas général ( n éléments ), à cause de la transitivité de la relation d'ordre.
Par-contre le nombre de relations anti-symétriques est plus facile à trouver en fonction de n.

Soit n le nombre d'éléments de E. On a déjà une partie à prendre sur la diagonale, donc [tex]2^n[/tex] choix de telles parties.

Ensuite il faut prendre une partie constitué d'éléments hors diagonale, avec deux choix possibles s'excluant mutuellement quand les couples sont symétriques.
Comme on a [tex]N = n(n-1)/2[/tex] couples au-dessus de la diagonale, on a encore un choix de   
[tex]\sum_{k=0}^N 2^k \binom{N}{k}[/tex]  parties possibles de couples hors diagonale ( puisque un couple exclut son symétrique ) , donc [tex]3^N[/tex] parties possibles  pour les points hors diagonale ( ce qu'on peut voir directement: un point hors diagonale est soit pas pris et son symétrique non plus, soit pris au-dessus, ou bien soit au-dessous ... donc 3 possibilités pour chaque )

Au final on a donc [tex]2^n 3^{n(n-1)/2}[/tex] relations anti-symétriques sur un ensemble à n éléments.

Une relation d'ordre étant toujours anti-symétrique, leur quantité pour n éléments est toujours majorée par celui-ci.

Pour revenir au dénombrement de relations d'ordre le mieux est peut-être de raisonner par niveaux comme dans les diagrammes de Hasse
le système étant le suivant:

- au même niveau aucun élément n'est relié à un autre.
- un élément d'un niveau donné est toujours relié à au moins 1 élément d'un niveau inférieur (si niveau inférieur il y a of course)

Cette démarche permet de dénombrer les diagrammes possibles sans en oublier. mais c'est assez pénible.

Alain

Bonjour,

En fait j'en ai sauté 6 autres, j'ai regardé la question trop rapidement, à savoir les cas où les relations partant ou arrivant d'un point ( ou sur ...) ne sont pas dans le même sens,
donc en tout ça en fait 19, à savoir ( sans expliciter la réfléxivité) :
La diagonale seule (1),  les relations types a->b ->c et permutations (6), les relations types b -> c et permutations (6), enfin celles du type
c -> a, c -> b ( cas d'un minimum sans maximum) (3 avec les permutations )  , et  c <- a, c <- b ( cas d'un maximum sans minimum) (3 avec les permutations ).
Cette fois ça doit être bon...

Désolé
Alain

Bonjour,

J'aimerais de l'aide a propos de cet exercice :

Trouver toutes les relations d'ordre sur l'ensemble $E=\{a,b,c\}$.

En fait j'ai donné 12 graphes dont les propriétés de l'ordre sont vérifiées et chaque graphe contient au moins le diagonale  de $E \times E.$