Dénombrement avec les relations


  • D

    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}

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

    2. 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


  • mtschoon

    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=82×2×2=23=8

    Tu pourrais faire un arbre pour expliciter cela


  • mtschoon

    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 32=93^2=932=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=93×3=32=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)}}$


  • mtschoon

    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 B3=5B_3=5B3=5
    Pour un ensemble à 1 élément, ce nombre est B1=1B_1=1B1=1
    Pour un ensemble à 2 éléments, ce nombre est B2=2B_2=2B2=2
    Pour un ensemble à 3 éléments, ce nombre est B3=5B_3=5B3=5

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


  • D

    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


  • mtschoon

    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


  • D

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


  • mtschoon

    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 !


  • mtschoon

    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.


  • D

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


  • mtschoon

    De rien Dut, et bon week-end aussi.


Se connecter pour répondre