Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Nombre de relations binaires

Posté par
Serphone
13-04-18 à 12:36

Bonjour,

Voilà l'énoncé de l'exercice:
Soit E un ensemble de cardinal n. Combien y'a t'il de relations binaires à la fois symétriques et anti-symétriques sur E ?

Si je note Sn, le nombre de relations binaires en question, j'arrive à une relation de récurrence entre les Sn mais je n'arrive à expliciter un terme général.

Voilà mon raisonnement:
Posons Sn le nombre de relations binaires symétriques et antisymétriques pour un ensemble de cardinal n, et S0 = 1

Pour n = 1, S1 = 2, car soit x1Rx1, soit x1\not{R}x1

Pour n = 2, S2 = 5, car soit les 2 éléments sont égaux (1 possibilité), soit ils sont différents (et à ce moment on a ni x1Rx2, ni x2Rx1) et il reste 4 possibilités pour les relations restantes.

Pour n = 3, S3 = 15, car soit l'on n'a pas x3Rx3 (S2 possibilités), soit l'on a x3Rx3 et alors :
_ soit x3 est en relation avec aucun xi (S2 possibilités)
_ soit x3 est en relation x1 (S1 possibilités)
_ soit x3 est en relation x2 (S1 possibilités)
_ soit x3 est en relation x1 et x2 (S0 possibilités)
Donc au total: 5 + 5 + 2 + 2 + 1 = 15

En suivant le même raisonnement, à savoir comment passer de Sn à Sn+1 en rajoutant un élément j'obtiens la relation suivante:
S_{n+1} = S_{n} + \sum_{k=0}^{n}{\binom{n}{k}S_{k}}

Seulement je n'arrive pas à expliciter un terme général qui ne dépendrait que de n..

Déjà est-ce que je suis sur la bonne piste ? Et si oui, comment trouver ce terme général ?

Merci par avance pour votre aide.

Posté par
jsvdb
re : Nombre de relations binaires 13-04-18 à 13:06

Bonjour Serphone.
Une relation est à la fois symétrique et anti-symétrique si et seulement si son graphe est inclus dans la diagonale de E \times E, c'est -à-dire le graphe de l'égalité.
Il y a donc 2^n possibilités.

Posté par
Serphone
re : Nombre de relations binaires 13-04-18 à 13:17

Bonjour jsvdb,

Merci pour votre réponse.
Je ne suis pas sûr de très bien comprendre par contre, pouvez-vous m'expliquer un peu plus ?

Par exemple si n=3,
la relation (x1Rx1, x2Rx2, x1Rx2, x2Rx1, x3Rx3) est bien symétrique et antisymétrique sans être inclus dans (x1Rx1, x2Rx2, x3Rx3), non ?

Posté par
etniopal
re : Nombre de relations binaires 13-04-18 à 13:32

Si E = { 0 , 1 }      
{ (0,0) }  ,  { (1,1)} , { ((0,0) , (1,1) } , { (0,0) 1,0) }  ,   { (0,0) , (0,1)  }  , {0,0) , (1,1)}  me semblent être graphes de 6 relations binaires  à la fois symétriques et anti - symétriques  sur E  .

Posté par
jsvdb
re : Nombre de relations binaires 13-04-18 à 13:35

Dans ton exemple, en supposant x_1 \neq x_2, tu as mis le couple (x_1;x_2) et donc (x_2;x_1) par symétrie.
Or, par anti-symétrie, l'un des deux est de trop.
A nouveau par symétrie, l'autre ne peut alors y figurer.
Donc, seuls des couples de la forme (x;x) \in \Delta_E peuvent figurer dans la relation en question.

Inversement, si la relation n'est formée que d'une partie quelconque de ces couples, alors elle est symétrique et anti-symétrique.

Donc le nombre de relations cherchée est  \mathfrak P(\Delta_E) = \mathfrak P(E) = 2^{\sharp E} = 2^n

Posté par
Serphone
re : Nombre de relations binaires 13-04-18 à 13:36

Si on a (1,0) alors par symétrie on a (0, 1) puis par antisymétrie (0, 0) et (1, 1) non ?

Posté par
jsvdb
re : Nombre de relations binaires 13-04-18 à 13:43

bonjour etniopal

etniopal @ 13-04-2018 à 13:32

Si E = { 0 , 1 }      
{ (0,0) }  ,  { (1,1)} , { (0,0) , (1,1) } , {(0,0),(1,0) }  ,   {(0,0),(0,1)}  , {(0,0) , (1,1)}  me semblent être graphes de 6 relations binaires  à la fois symétriques et anti - symétriques  sur E  .

Clairement pas :
{(0,0)} est OK
{(1,1)} est OK
{(0,0),(1,1)} est OK
La quatrième est
{(0,0),(1,0)} est anti-symétrique et non symétrique (il manque (0,1))
{(0,0),(0,1)} même punition (il manque (1,0))
{(0,0),(1,1)} est OK mais c'est la même que la troisième.

Serphone @ 13-04-2018 à 13:36

Si on a (1,0) alors par symétrie on a (0, 1) puis par anti-symétrie (0, 0) et (1, 1) non ?

Si la relation est anti-symétrique alors, si (1,0) y figure, (0,1) ne doit pas y figurer.
Du coup, pour respecter la symétrie, il faut alors aussi enlever (1,0).

Posté par
Serphone
re : Nombre de relations binaires 13-04-18 à 13:43

Ok, merci jsvdb, j'ai compris !

Mon erreur était de ne pas voir que si (x1, x2) était dans la relation ça ne pouvait pas marcher car forcément on aurait x1 = x2 et donc pas possible puisque E a n éléments (distincts).



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !