Dénombrement avec les relations

Bonjour, on refait le partiel de l'année dernière principalement l’exercice sur le dénombrement avec des questions jamais abordées. Nous sommes en groupe pour travailler sur l'examen mais là chacun y va de sa solution mais au final on ne sait pas quelle est la bonne réponse.

Soit X={a,b,c}

Combien y a-t-il de fonctions de X vers {0,1}?
--> formule 2^(card X)²=512
Combien de relations binaires sur X?

3)Combien de relations d’équivalence sur X?
Je fais le schéma avec la réflexion, la transition et la symétrie.
--> selon moi il n'y a qu'une possibilité mais je ne sais pas justifié comment

Merci à vous, bonne journée

Rebonjour Dut,

1) Combien y a-t-il de fonctions de X vers {0,1 ?
Ta réponse à la 1) n'est pas bonne, car ce n'est pas la bonne formule.

Je t'indique d'abord la formule que tu aurais dû utiliser

Recherche du nombre de fonctions (que j'appelle "applications"car tout élément d X a une image) de X vers F
Card X = n
Card F = p
Ce nombre est $\fbox{p^n}$
Ici, n=3 et p=2, d'où $n^p=\fbox{2^3=8}$
Vu que ce total est faible, tu pourrais expliciter facilement ces fonctions.

Remarque : au lieu d'appliquer une formule, je te conseille plutôt de raisonner directement.
L'image de a peut être 0 ou 1 : 2 possibilités
Lorsque l'image de a est choisie, il y a 2 possibilités pour b (0 ou 1)
Lorsque l'image de a et de b sont choisies, il y a 2 possibilités pour c (0 ou 1)

Total : $2×2×2=23=82\times 2 \times 2=2^3=8$

Tu pourrais faire un arbre pour expliciter cela

Combien de relations binaires sur X ?

Il faut d'abord chercher combien il y a de couples (x,y) d'éléments de X : il y en a $3^2=9$

explication :
x peut prendre la valeur a ou b ou c : 3 possibilités
Lorsque la valeur de x est choisie, y peut prendre la valeur a ou b ou c : 3 possibilités
Total $3×3=32=93\times 3=3^2=9$

Il tu veux les énumérer, ces couples sont
(a,a) (a,b), (a,c) (b,a) (b,b) (b,c )(c,a )(c,b) (c,c)

Pour chacun de ces couples (x,y)
xRy est vraie ou xRy est fausse : il y a 2 possibilités

On peut détailler
Pour (a,a) : aRa vraie ou fausse : 2 possibilités
Pour (a,b) : aRb vraie ou fausse: 2 possibilités
...
...
Pour Pour (c,c) : cRc vraie ou fausse : 2 possibilités

Total $2\times 2 \times 2\times 2\times 2\times2 \times2 \times2\times 2=\fbox{2^9=512}$ (valeur modifiée)

Remarque :
Si tu veuxs une formule générale avec card X=n
le nombre de relations binaires sur X est $\fbox{2^{(n^2)}}$

3) Combien de relations d’équivalence sur X?

J'utilise les connaissances vues dans l'exercice précédent relatif aux relations d'équivalence.

Une relation d'équivalence R sur X définie une partition de X (composée des classes d'équivalence)

Le nombre de relations d'équivalence sur X est donc le nombre de partitions de X

Rappel de la définition précise d'une partition :
aucune partie n'est vide, les parties sont disjointes deux à deux, leur réunion est X

Les partitions de X sont :
{{a,b,c}}
{{a},{b,c} , {{b}{c,a}} , {{c},{a,b}}
{{a},{b},{c}}

Total : 5

Il y a donc 5 relations d'équivalence possibles sur X

Remarque : Si tu voulais une formule générale, je te dirais que cela est très particulier.
Il s'agit du nombre de Bell (tu peux faire des recherche sur le web)
Le nombre de partitions sur un ensemble de 3 éléments se note $B_3=5$
Pour un ensemble à 1 élément, ce nombre est $B_1=1$
Pour un ensemble à 2 éléments, ce nombre est $B_2=2$
Pour un ensemble à 3 éléments, ce nombre est $B_3=5$

Ces nombres peuvent se calculer de proche en proche avec une relation de récurrence fort compliquée

Bonsoir Mtschoon,
Merci énormément pour cette explication.
Il me semble qu'il y a une erreur pour le b) 2^9 = 512

Pour le c) le nombre de Bell est fort intéressant. J'ai juste un peu de mal à comprendre:
Les partitions de X sont :
{{a,b,c}}
{{a},{b,c}} , {{b}{c,a}} , {{c},{a,b}}
{{a},{b},{c}}

je n'arrive pas à faire le lien entre la reflexion, la transition, et la symétrie.

Merci beaucoup
Bonne soirée

Bonsoir Dut,

Tout à fait exact pour 512.

Pour les partitions de X :

Il y a :

Une partition composée d'une seule partie :
c'est {X} c'est à dire{{a,b,c}}

Trois Partitions composées de 2 parties :
ce sont {{a},{b,c}} , {{b}{c,a}} , {{c},{a,b}}

Une partition composée de trois parties
c'est {{a},{b},{c}}

Total : 5 partitions.

Il faut que tu approfondisses l'exercice précédent pour comprendre le lien entre relation d'équivalence, classes d'équivalence et partition :
Une relation d'équivalence R (réflexive, symétrique, transitive) définie une partition composée des classes d'équivalence de la relation R.
Il y a donc autant de relations d'équivalences possibles sur X que de partitions possibles sur X

Merci beaucoup Mtschoon j'ai compris.
Bonne journée

Bonjour Dut,

Je te mets une illustration pour ces 5 cas, qui sont, je dirais, des cas "limites" (et qui peuvent être perturbants)

Soit R relation d'équivalence sur X
Il faut avoir bien assimilé la notion de classe d'équivalence pour comprendre.

1er cas : la partition liée à R est {{a},{b},{c}}
on a, dans ce cas, exclusivement aRa vraie, bRb vraie, cRc vraie

Tu peux vérifier que les 3 propriétés (réflexivité, symétrie, transitivité) sont bien réalisées
réflexivité :
pour tout u de X on a bien uRu vraie
ici, pour u=a, u=b, u=c, on a bien uRu vraie
symétrie:
pour tout u et tout v de X tels que uRv est vraie, alors vRu est vraie
ici, pour u=a et v=a, on a bien uRv vraie alors vRu vraie
(idem pour u=b et u=c, et idem pour u=c et v=c)
transitivité :
pour tout u, tout v, tout w de X tels que uRv est vraie et vRw est vraie, alors uRw est vraie
ici, pour u=a v=a w=a on a bien uRv vraie vRw vraie alors uRw vraie
(idem pour u=b v=b w=b et idem pour u=c v=c w=c)

2ème cas : la partition liée à R est {{a},{b,c}
on a, dans ce cas, exclusivement :
aRa, bRb, cRc, cRb, bRc
tu peux encore vérifier les 3 propriétés

3ème cas : la partition liée à R est {{b}{c,a}}
on a, dans ce cas, exclusivement :
bRb, cRc, aRa, aRc, cRa
tu peux encore vérifier les 3 propriétés

4ème cas : la partition liée à R est {{c},{a,b}}
on a, dans ce cas, exclusivement :
cRc, aRa, bRb, aRb, bRa
tu peux encore vérifier les 3 propriétés

5ème cas : la partition liée à R est {{a,b,c}}
on a, dans ce cas, exclusivement :
aRa ,bRb ,cRc, aRb, bRa, aRc ,cRa, bRc, cRb
tu peux encore vérifier les 3 propriétés

Je pense que lorsque tu disais qu'il avait qu'une seule relation d'équivalence dans X c'est de ce 5ème cas dont tu parlais car il est moins trivial.

Bonne réflexion sur tout ça !

Pour concrétiser, je te mets un énoncé qui illustre les 5 relations d'équivalence sur X={a,b,c}

Supposons que les lettres de X soient écrites en couleur.
uRv : u et v sont de même couleur
R est une relation d'équivalence sur X car le 3 propriétés utiles sont exactes

Hypothèse : a rouge, b bleu, c vert :
c'est le 1er cas de l'explication

Hypothèse : a rouge, b bleu, c bleu :
c'est le 2ème cas de l'explication

Hypothèse : b rouge, a bleu, c bleu :
c'est le 3ème cas de l'explication

Hypothèse : c rouge, a bleu, b bleu :
c'est le 4ème cas de l'explication

Hypothèse : a rouge, b rouge, c rouge :
c'est le 5ème cas de l'explication

Je pense que le tour de la question est effectué.

Bon travail.

Merci beaucoup Mtschoon pour toutes ces explications. Bon week-end

De rien Dut, et bon week-end aussi.