Relation ordre complete

[invite47311597]

Bonjour j'ai un exo à résoudre en utilisant une récurrence , j'ai initialisé mais ait du mal à faire l'hérédité
Soit X = { C1 , C2 , ... , CN } un ensemble de n candidats
Montrer que le nombre d'ordres totaux ( relation d'ordre complète ) est n!
j'ai initialisé pour n = 3 et ait montré qu'il y avait 6 relations , 6 = 3! mais pour le montrer pour (n+1)! je ne vois pas comment je pourrai le faire pourriez vous me donner une piste vers où m'orienter svp , je sais que pour passer de n! à ( n+1 ) ! il faut multiplier par n+1 mais dans le contexte de l'exercice je ne vois pas comment je pourrai l'introduire
-----

[invite9dc7b526]

En général on ne fait pas de récurrence, on dit simplement qu'il y a n façons de choisir le premier élément, (n-1) façons de choisir le deuxième, etc. Après le prof peut trouver cet argument peu convainquant.

[syborgg]

Encore des exos a la c... Autant dire qu'on voulait faire prouver a l'eleve que le nombre de permutations d'un ensemble a n elements est n !
Pourquoi deguiser ca en ajoutant une hypothese non necessaire d'ordre total ?...

[invite47311597]

Mon prof a dit qu'il valait mieux utiliser une récurrence mais je ne vois pas comment je pourrai démarrer l'hérédité , écrire la définition de la permutation pour répondre à l'énoncé serait-il considéré comme juste malgré tout ?

[A voir en vidéo sur Futura]

[syborgg]

Mon prof a dit qu'il valait mieux utiliser une récurrence mais je ne vois pas comment je pourrai démarrer l'hérédité , écrire la définition de la permutation pour répondre à l'énoncé serait-il considéré comme juste malgré tout ?

Suppose que le resultat est vrai pour n elements. Si tu passe de n a n+1 en rajoutant un element, comment peut il se placer par rapport aux n premiers pour conserver un ordre total ?

[invite47311597]

il doit appartenir au même ensemble pour pouvoir vérifier les propriétés d'antisymétrie , de réfléxivité et de totalité non ?

[syborgg]

il doit appartenir au même ensemble pour pouvoir vérifier les propriétés d'antisymétrie , de réfléxivité et de totalité non ?

Ne pense pas en ces termes : comment se placent les un par rapport aux autres les elements d'un ensemble totalement ordonne fini ? selon une ligne, l'un apres l'autre, avec un premier et un dernier. Maintenant reprends mon conseil precedent avec cela en tete.

[invite47311597]

donc en ajoutant n+1 j'ai C1 , C2, ... Cn , C(n+1) , C(n+1 ) va être en relation avec n termes différents pour conserver un ordre total et multiplier par lui même on obtiendra n+1! est ce convainquant comme justification ?

[syborgg]

donc en ajoutant n+1 j'ai C1 , C2, ... Cn , C(n+1) , C(n+1 ) va être en relation avec n termes différents pour conserver un ordre total et multiplier par lui même on obtiendra n+1! est ce convainquant comme justification ?

Pas trop non... imagine n boules (si tu preferes n = 3 ou 4) disposees en ligne de gauche a droite (un ordre total). Sans changer l'ordre de ces n boules, tu veux rajouter une autre boule de facon a obtenir un ordre total (une autre ligne). Quels choix as tu pour disposer cette boule parmi les autres ?

[invite47311597]

je la mets à gauche de la 1ere boule ou à droite de la troisième boule

[invite23cdddab]

Oui, mais il t'en manque : Tu peux aussi mettre la nouvelle boule entre la première et la deuxième, ou entre la deuxième et la troisième


Après, personnellement, j'aurai plutôt tendance à remarquer que donner un ordre total sur N boules, c'est équivalent à les numéroter de 1 à n, ce qui est équivalent à se donner une bijection de l'ensemble des N boules dans [|1,n|]

[invite9dc7b526]

Après, personnellement, j'aurai plutôt tendance à remarquer que donner un ordre total sur N boules, c'est équivalent à les numéroter de 1 à n, ce qui est équivalent à se donner une bijection de l'ensemble des N boules dans [|1,n|]

ah tiens c'est marrant, j'aurais plutôt tendance à penser à la numérotation des N boules comme à une bijection de {1..N} vers l'ensemble des boules... bref, dans un sens comme dans l'autre ça revient à une permutation des N boules.

[invite23cdddab]

Oui, en pratique, si j'ai besoin de l'expliciter je ferai comme toi (Nombres -> Boules). Mais si, physiquement, tu me donnes des boules ordonnées, je vais attribuer à chaque boule un numéro (donc Boules -> Nombres)

Dans tout les cas, dans ma tête, quand je pense "bijection", j'ai automatiquement la bijection inverse qui vient avec, donc avoir une bijection de A vers B ou de B vers A, c'est "pareil"