Dénombrement des relations binaires

[invitea0643401]

Bonjour, dans mon cours j'ai:
E un ensemble fini de cardinal n non-nul.
Une relation binaire est bien (x,y)E E², xRy ?
Mon cours dit que l'on peut en définir 2^(n²) ...
Je ne comprends pas car j'aurai tendance à penser qu'il y en a 2*(n²).
Pourriez vous m'expliquer?

Il s'en suit après le dénombrement des relations binaires réflexives et symétriques dont les formules respectives sont 2^(n(n-1)) et 2^(n(n+1)/2). Seulement là encore je ne vois ...

Pour faire mes relations binaires je dois faire un tableau avec une colonne et une ligne pour chaque élement, les cases du tableau équivaudraient à des relations binaires dans ce cas non ?

Merci par avance.
-----

[Médiat]

Bonjour, dans mon cours j'ai:
E un ensemble fini de cardinal n non-nul.
Une relation binaire est bien (x,y)E E², xRy ?
Mon cours dit que l'on peut en définir 2^(n²) ...
Je ne comprends pas car j'aurai tendance à penser qu'il y en a 2*(n²).
Pourriez vous m'expliquer?

Bonjour

une relation binaire sur E est un sous-ensemble de E², or le nombre de sous ensembles d'un ensemble de cardinal p est ; comme le cardinal de E est n, celui de E² est n², le nombre de sous ensembles est bien

[invitea0643401]

D'accord, merci pour cette démonstration on ne peut plus claire ( et beaucoup plus claire que mes tableaux à 2F ) ...

[invitea0643401]

Réflexivité: xE E, xRx ?
Symétrie: (x,y)E E², xRy => yRx ?

Une idée de démonstration ?

[A voir en vidéo sur Futura]

[Médiat]

Réflexivité: xE E, xRx ?

Oui, donc pour fabriquer un sous ensemble de E² qui soit une relation réflexive, il faut prendre tous les couples de la forme (x, x), ce que l'on appelle la diagonale et qui contient évidemment autant d'élément que E, c'est à dire n, bien sur, il n'y a qu'une seule façon de prendre tous les éléments de la diagonale, mais il faut ajouter à ce sous-ensemble, tous ceux que l'on peut fabriquer avec le reste, reste dont le cardinal est n² - n, on peut donc fabriquer tels sous-ensembles.
Pour la symétrie, le procédé est le même, il faut se demander comment fabriquer un sous ensemble qui respecte les contraintes ...

[invitea0643401]

Merci beaucoup, je commence à comprendre la méthode seulement, sur mon cours j'ai noté 2^(n²-n). Ais-je mal noté ?

[Médiat]

Merci beaucoup, je commence à comprendre la méthode seulement, sur mon cours j'ai noté 2^(n²-n). Ais-je mal noté ?

Non c'est moi :

dont le cardinal est n² - n,

Ca c'est bon !

on peut donc fabriquer tels sous-ensembles.

[invitea0643401]

Merci, pour les relations symétriques, il faut prendre les n² combinaisons possibles et les diviser par 2 pour ne pas compter les symétriques mais je ne vois pas d'où vients le n/2 ... Pourriez-vous m'expliquer ?

[Médiat]

Merci, pour les relations symétriques, il faut prendre les n² combinaisons possibles et les diviser par 2 pour ne pas compter les symétriques mais je ne vois pas d'où vients le n/2 ... Pourriez-vous m'expliquer ?

Est-ce qu'il faut vraiment diviser par deux la diagonale ?

[invitea0643401]

Et bien au final je doit trouver 2^(n(n+1)/2) donc il y a bien du n/2 ...

[Médiat]

Et bien au final je doit trouver 2^(n(n+1)/2) donc il y a bien du n/2 ...

Le résultat annoncé est correct, mais ne vous demandez pas comment arriver à ce résultat, demandez vous comment compter ces relations (je vous ai déjà presque donné la solution (comptez ce qui peut être divisé par 2 et divisez par 2, comptez ce qui ne peut pas être divisé par deux et ajoutez le sans diviser bien sur)).

[invitea0643401]

Je viens de réfléchir un petit peu avec vos indications (merci du temps que vous m'accordez) et je m'y prenais mal en fait je crois qu'il faudrait plutôt dire que l'on doit prendre les n²-n relations qui excluent la diagonale et les diviser par 2 pour ne pas compter les symétriques et y ajouter n sans le diviser par 2 car les couples de type (x,x) sont leurs propres symétriques...
Est-ce celà ?

[Médiat]

Je viens de réfléchir un petit peu avec vos indications (merci du temps que vous m'accordez) et je m'y prenais mal en fait je crois qu'il faudrait plutôt dire que l'on doit prendre les n²-n couples qui excluent la diagonale et les diviser par 2 pour ne pas compter les symétriques et y ajouter n sans le diviser par 2 car les couples de type (x,x) sont leurs propres symétriques...
Est-ce celà ?

_ _

Juste une correction (en gras)

[invitea0643401]

Merci beaucoup de votre aide, j'ai noté pour mon erreur de vocabulaire (mon prof sera content car il ne jure que par la rigueur !). Bonne soirée et je vous souhaite de beaux horizons mathématiques pour l'année 2010 !

[invitec05d082d]

attentionn ce n'est pas n^2-1 mais c'est n^2-n