Surjections d'un ens. à n+2 éléments sur un ens. à n éléments

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: Non inscrit

Bonjour,

Je bloque sur une question de niveau 1ère année de 1er cycle : si quelqu'un avait la gentillesse de me dire où est-ce que je me plante misérablement...

On se donne un ensemble E de cardinal fini à n+2 éléments et un ensemble F de cardinal fini à n éléments. On veut calculer le nombre de surjections de l'ensemble E sur l'ensemble F, soit S(n+2,n).

Je pensais me débrouiller comme suit, en adaptant la démonstration de S(n+1,n) :

Dans l'ensemble F, on a soit un élément qui possède exactement 3 antécédents dans E, soit (au moins) un élément qui possède exactement 2 antécédents dans E.

Dans le premier cas, on peut construire des surjections de E sur F de la façon suivante : on prend un élément de F (n possibilités), on lui "associe" 3 éléments de E (C(n+2,3) possibilités), et il reste à "associer" n-1 éléments de F avec n-1 éléments de E ((n-1)! possibilités). Au total, n*C(n+2,3)*(n-1)! possibilités.

Dans le deuxième cas, on peut construire des surjections de E sur F de la façon suivante : on prend un élément de F (n possibilités), on lui "associe" 2 éléments de E (C(n+2,2) possibilités), et il reste à associer n éléments de F avec n-1 éléments de E (S(n,n-1) = (n-1)*n!/2 possibilités). Au total, n*C(n+2,2)*(n-1)*n!/2 possibilités.

Si je fais la somme de toutes ces possibilités, j'obtiens :

n*C(n+2,3)*(n-1)! + n*C(n+2,2)*(n-1)*n!/2 = (n+2)!*n*(6n-2)/24.

Or, je sais que S(n+2,n) = (n+2)!*n*(3n+1)/24.

Donc, je me plante quelque part, mais je ne suis pas capable de trouver où... Si quelqu'un pouvait m'aider...

Merci.


Posted by: Chimerade

Citation:
Posté par Non inscrit
Bonjour,

Je bloque sur une question de niveau 1ère année de 1er cycle : si quelqu'un avait la gentillesse de me dire où est-ce que je me plante misérablement...

On se donne un ensemble E de cardinal fini à n+2 éléments et un ensemble F de cardinal fini à n éléments. On veut calculer le nombre de surjections de l'ensemble E sur l'ensemble F, soit S(n+2,n).

Je pensais me débrouiller comme suit, en adaptant la démonstration de S(n+1,n) :

Dans l'ensemble F, on a soit un élément qui possède exactement 3 antécédents dans E, soit (au moins) un élément qui possède exactement 2 antécédents dans E.

Dans le premier cas, on peut construire des surjections de E sur F de la façon suivante : on prend un élément de F (n possibilités), on lui "associe" 3 éléments de E (C(n+2,3) possibilités), et il reste à "associer" n-1 éléments de F avec n-1 éléments de E ((n-1)! possibilités). Au total, n*C(n+2,3)*(n-1)! possibilités.

Dans le deuxième cas, on peut construire des surjections de E sur F de la façon suivante : on prend un élément de F (n possibilités), on lui "associe" 2 éléments de E (C(n+2,2) possibilités), et il reste à associer n éléments de F avec n-1 éléments de E (S(n,n-1) = (n-1)*n!/2 possibilités). Au total, n*C(n+2,2)*(n-1)*n!/2 possibilités.

Si je fais la somme de toutes ces possibilités, j'obtiens :

n*C(n+2,3)*(n-1)! + n*C(n+2,2)*(n-1)*n!/2 = (n+2)!*n*(6n-2)/24.

Or, je sais que S(n+2,n) = (n+2)!*n*(3n+1)/24.

Donc, je me plante quelque part, mais je ne suis pas capable de trouver où... Si quelqu'un pouvait m'aider...

Merci.


Ben tu te plantes là :


Citation:
Posté par Non inscrit
Dans le deuxième cas, on peut construire des surjections de E sur F de la façon suivante : on prend un élément de F (n possibilités), on lui "associe" 2 éléments de E (C(n+2,2) possibilités), et il reste à associer n éléments de F avec n-1 éléments de E (S(n,n-1) = (n-1)*n!/2 possibilités). Au total, n*C(n+2,2)*(n-1)*n!/2 possibilités.


En effet, ce faisant, tu n'exclues pas la possibilité que l'élément de F choisi dans la première phase reçoives 2 éléments de E dans la deuxième phase, soit en tout trois éléments, et tu as déjà compté ces cas là...

Je pense qu'il faut dire :

Dans l'ensemble F, on a soit un élément qui possède exactement 3 antécédents dans E, soit deux éléments qui possèdent exactement 2 antécédents dans E.

Là tu arriveras à résoudre...


Posted by: Non inscrit

Bonjour,

"En effet, ce faisant, tu n'exclues pas la possibilité que l'élément de F choisi dans la première phase reçoives 2 éléments de E dans la deuxième phase, soit en tout trois éléments, et tu as déjà compté ces cas là..."

Mais... Une fois la correspondance établie entre l'élément de F de la 1ère phase et les 2 éléments de E, j'"enlève" pourtant bien cet élément de l'ensemble F (c'est pour cela que F perd une unité de cardinalité)... Donc, comment est-ce que je peux encore lui associer des éléments par la suite, alors je ne le considère plus dans mes choix ?

Je n'ai sans doute pas compris ce que tu voulais dire... Tu pourrais détailler un peu plus ? En particulier, j'ai aussi (ré)essayer de faire les calculs avec ta méthode, mais j'obtiens le même (faux) résultat...

Merci de ton aide.


Posted by: Chimerade

J'ai peut-être répondu un peu vite. Je vais refaire le problème à partir de zéro.
@+


Posted by: gamecuber

Citation:
il reste à associer n éléments de F avec n-1 éléments de E




Euh juste pour éviter toute erreur pour la suite, il me semble que c'est plutot "n-1 éléments de F à n éléments de E" , mais je pense que vous l'auriez vu de toute façon :)

++


Posted by: gamecuber

re-salut :

je pense que la disjonction de chimerade est la plus simple pour résoudre cet exercice :
- on peut reprendre ce qui a été fait pour le premier cas, ie un élément a 3 antécédents par f : on compte bien n* C(n+2,3) * (n-1)! possibilités.
- pour le 2e cas : 2 éléments ont 2 antécédents par f : on choisit d'abord ces deux éléments dans F (C (n,2) choix) ; on choisit ensuite les 4 antécédents de ceux-ci dans E (C (n+2,4) choix) ; enfin, il y a C (4,2) possibilités pour associer ces 4 éléments de E aux 2 éléments de F (puisque dès lors que 2 des antécédents sont choisis pour un élément F, les 2 autres sont associés à l'autre élément de F) ; enfin on compte le nombre de permutations d'un ensemble à (n-2) éléments ( (n-2)! ) pour associer les n-2 éléments restants dans chacun des ensembles E et F. On obtient finalement pour ce 2e cas : C(n,2)*C(n+2,4)*C(4,2)*(n-2)! .

En additionant les 2 résultats obtenus, on a finalement :

S(n+2,n)= n/6 *(n+2)! + n(n-1)(n+2)!/8 = (n+2)!*n*(3n+1)/24

Voilà, j'espère que mon explication est claire et compréhensible :)

Bonne continuation.

+


Posted by: gamecuber

Citation:
Une fois la correspondance établie entre l'élément de F de la 1ère phase et les 2 éléments de E, j'"enlève" pourtant bien cet élément de l'ensemble F (c'est pour cela que F perd une unité de cardinalité)...



Oui c'est exact, l'erreur ne venait pas de là. Le problème avec l'énoncé du 2e cas que l'auteur du topic a proposé, c'est qu'en isolant un élément de F, puis en lui associant 2 éléments de E et enfin en multipliant par S(n+1,n) , on compte plusieurs fois les mêmes surjections. On peut en effet "isoler" indifféremment chacun des 2 éléments de F qui aura 2 antécédents pour retomber sur la même surjection...

C'est pourquoi je pense qu'il vaut mieux considérer les 2 cas proposés par Chimerade. ;)

@+

PS : Désolé pour le "triple-posting" ...


Posted by: Chimerade

Citation:
Posté par gamecuber
Oui c'est exact, l'erreur ne venait pas de là. Le problème avec l'énoncé du 2e cas que l'auteur du topic a proposé, c'est qu'en isolant un élément de F, puis en lui associant 2 éléments de E et enfin en multipliant par S(n+1,n) , on compte plusieurs fois les mêmes surjections. On peut en effet "isoler" indifféremment chacun des 2 éléments de F qui aura 2 antécédents pour retomber sur la même surjection...


C'est tout-à-fait exact. J'avais effectivement répondu un peu trop vite et gamecuber a dit exactement ce qu'il fallait dire. On peut même préciser que l'on compte exactement deux fois les mêmes surjections dans la deuxième partie du calcul. On pourrait donc achever le raisonnement de non-inscrit en divisant par deux le deuxième terme de son calcul :

Au lieu de :
n*C(n+2,3)*(n-1)! + n*C(n+2,2)*(n-1)*n!/2 = (n+2)!*n*(6n-2)/24.
il faut faire :
n*C(n+2,3)*(n-1)! + [ n*C(n+2,2)*(n-1)*n!/2 ] / 2 = (n+2)!*n*(3n+1)/24.

C'est-à-dire le bon résultat !

Pour le reste, j'ai refait tous les calculs à partir de zéro et ce que j'aurais à dire est identique à ce qu'a déjà dit gamecuber à 21H54. Alors, inutile de le redire.

Bon courage !


Posted by: Non inscrit

Merci à vous deux... J'ai enfin compris mon erreur !


Posted by: gamecuber

Citation:
Merci à vous deux... J'ai enfin compris mon erreur !


Il n'y a pas de quoi!

Bonne continuation.

+


Posted by: Chimerade

Citation:
Posté par Non inscrit
Merci à vous deux... J'ai enfin compris mon erreur !

C'est un plaisir.

Bon courage










-