Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 14-09-2018 09:49:58

Zebulor
Invité

denombrement

Bonjour!

il s'agit de calculer le nombre d'applications surjectives d'un ensemble de n+3 éléments sur un ensemble de n éléments. E est l'ensemble de départ et F l'ensemble d'arrivée. Il s'agit du cas où 3 éléments de F ont 2 antécédents, les autres un seul.

J'ai trouvé ((n+3)!*n^2*(n+1))/8 solutions en considérant le nombre de choix possibles pour chaque élément de F associé à un doubleton de E, puis le nombre de bijections sur les parties de E et F restantes soit (n-3)!

On devrait trouver ((n+3)!*n^2*(n+1))/48 solutions. Je ne vois pas où est mon erreur


Merci à toute contribution !

#2 15-09-2018 08:48:29

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

Bonjour
Je n'ai pas vérifié ta seconde formule mais la tienne est visiblement  fausse: En effet tu fais n=1 et ça coince tandis que l'autre c'est bon.
Maintenant je ne comprends rien à cette phrase: "Il s'agit du cas où 3 éléments de F ont 2 antécédents, les autres un seul." 
Et peut être c'est à l'origine de ton erreur.
Un élément peut avoir 4 antécédents et tu n'en tiens pas compte. Ce qui est étonnant c'est que tu sembles ne pas considérer certains cas mais tu trouverais (si la seconde formule est bonne) plus de cas.
C'est à dire qu'il faut tout revoir.

Je te conseille déjà d'envisager le cas n=1, n=2 pour te familiariser avec l'exo. Et  ensuite trouver une bonne stratégie du dénombrement des surjections de E sur F.

Hors ligne

#3 15-09-2018 10:48:47

Michel Coste
Invité

Re : denombrement

Tu es sûr du deuxième résultat ? Ne serait-ce pas plutôt, pour le cas où trois éléments de l'ensemble d'arrivée ont deux antécédents,

[tex]\frac1{48} n(n-1)(n-2) (n+3)! [/tex]

#4 15-09-2018 10:57:29

Michel Coste
Invité

Re : denombrement

Si on compte les surjections avec un élément qui a quatre antécédents, c'est

[tex]\frac1{24} n (n+3)![/tex]

et si on compte celle où un élément a trois antécédents et un autre deux, c'est

[tex] \frac1{12} n(n-1)(n+3)![/tex]

Au total, ça fait bien

[tex] \frac1{48} n^2 (n+1) (n+3) ![/tex]

#5 15-09-2018 11:09:55

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

Et les surjections où 3 éléments ont exactement 2 antécédents, ils sont comptabilisés comment?

Dernière modification par aviateur (15-09-2018 11:10:17)

Hors ligne

#6 15-09-2018 13:29:39

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

donc on calcule les surjections avec
1. Un élément à 4 antécédents ---> x1
2. Un élément à 3 antécédents  un autre 2 ---> x2   
3  3 éléments ont 2 antécédents      ----x3

Je trouve x1=binomial[n, 1] binomial[3 + n, 4] (-1 + n)!
x2=2*binomial[n, 2]*binomial[n + 3, 3]*binomial[n, 2]*(n - 2)!
x3=binomial[n, 3]*binomial[n + 3, 2]*binomial[n + 1, 2]*binomial[n - 1, 2]*(n - 3)!

on ajoute x1+x2+x3 et on factorise et simplifie.

Dernière modification par aviateur (15-09-2018 13:30:03)

Hors ligne

#7 15-09-2018 14:57:47

D_john
Invité

Re : denombrement

Salut,
Si j’ai bien compris, Zebulor veux dénombrer les seules surjections E → F dont 3 éléments de F ont 2 antécédents.
Pour n = 3, il y a 15 partitions possibles de E en paires (donc 2 à 2 disjointes). Chaque partition contient évidemment 3 paires (donc 2 éléments de E sans ordre) à mettre en bijection avec les 3 éléments de F. D’où le nombre de surjections 3!*15 = 90.
La formule de Zebulor donne 6!*9*4/8 = 3240
La solution proposée dans #1 donne 540.
Conclusion : Cette solution ne correspond pas à l’énoncé donné par Zebulor.
… le tout, sauf erreur !
A+

#8 15-09-2018 17:24:42

zebulor
Invité

Re : denombrement

Bonjour à tous,

Je veux être plus clair en précisant, comme l'écrit D_John que je ne veux dénombrer que les surjections de E vers F dont 3 éléments de F ont 2 antécédents, et tous les autres éléments de F un seul antécédent.

Je n'ai  pas considéré les autres cas parce qu'ils me semblent plus faciles à décompter. Pour les autres cas étudiés par Michel Coste (message de 10h57) je trouve les mêmes résultats, par contre je ne comprends pas la conclusion "Au total ça fait bien...."

En comparant mes résultats avec aviateur pour X1 je trouve x1=n*binomial[n, 1] binomial[3 + n, 4] (-1 + n)!  Il me semble qu'il manquait le facteur n (n possibilités de choix de singletons dans F)

Puis je trouve X2= binomial[n + 3, 3]*binomial[n, 2]*(n - 2)!*n*(n-1) parce qu'il y a binomial[n + 3, 3] tripletons de F associés à un des n singletons de F, et dans les ensembles restants , il y a binomial[n, 2] doubletons de E associés à un des n-1 singletons reqtants dans F, puis (n-2)! bjections dans les paties restantes.

Pour X3, dont j'essaie de comprendre le raisonnement pour le trouver car c'est l'objet de ma demande, je réfléchis sur le résultat x3=binomial[n, 3]*binomial[n + 3, 2]*binomial[n + 1, 2]*binomial[n - 1, 2]*(n - 3)! donnée par aviateur!

Merci pour vos contributions et à bientôt..

#9 16-09-2018 00:01:32

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

Bonjour
En effet, d'abord et avant tout  il faut être plus clair.
Logiquement, vu l'énoncé, j'essaye de comprendre la  "vraie question"
Alors le "on devrait trouver...." correspond exactement au nombre de surjection de E vers F.
J'ai trouvé deux façons différentes de le calculer mais en particulier x1+x2+x3 donne la solution sous la forme donnée.
Maintenant  si j'ai bien compris c'est x3 qui t'intéresse. Tu trouves tout de même  la réponse à ta question

Dernière modification par aviateur (16-09-2018 00:02:56)

Hors ligne

#10 16-09-2018 00:06:22

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

En te relisant, j'en profite de nouveau pour confirmer que je suis sûr que c'est juste à cause du recoupement de mes 2 calculs et si tu ne comprends pas le x3 pas de pb je peux expliquer

Hors ligne

#11 16-09-2018 06:58:59

D_john
Invité

Re : denombrement

OK aviateur : petite preuve, on obtient bien tous deux x3(3) = 90
Bon dimanche à tous.

#12 16-09-2018 08:26:43

zebulor
Invité

Re : denombrement

Bonjour,

certains se sont couchés tard ou levé tôt pour me répondre! En effet il faut être clair. L'objet de ma demande c'est de trouver le nombre de surjections d'un ensemble E contenant n+3 éléments vers un ensemble F contenant n éléments dans le SEUL et UNIQUE cas où 3 éléments de F ont 2 antécédents, et les autres éléments de F un seul antécédent.

Ce qui m'intéresse, plus encore que la formule générale (qui dépend donc de l'entier naturel n), c'est le raisonnement qui conduit à ce nombre pour un entier n quelconque, et pas seulement pour une valeur de n particulière comme n=3. On devrait bien trouver : ((n+3)!*n²*(n+1))/48 toujours dans ce seul et unique cas!

En espérant avoir été plus clair !

Bon dimanche à aviateur et D_John

#13 16-09-2018 08:59:24

Michel Coste
Invité

Re : denombrement

NON !
La bonne réponse est, je le répète,

[tex]\frac1{48} n(n-1)(n-2) (n+3)![/tex]

On peut raisonner comme suit.

On part d'une permutation [tex]\sigma[/tex] de l'ensemble [tex]\{1,2,\ldots,n+3\}[/tex] et d'une injection [tex] u : \{n+1,n+2,n+3\} \to \{1,\ldots,n\}[/tex] ; il y a [tex] n(n-1)(n-2)(n+3)![/tex] tels couples [tex](u,\sigma)[/tex]. À un tel couple on associe la surjection [tex] f : \{1,\ldots,n+3\}\to \{1,\ldots,n\}[/tex] définie par [tex] f(i)=\sigma(i)[/tex] si [tex]\sigma(i)\leq n[/tex] et [tex]f(i)=u(\sigma(i))[/tex] si [tex]\sigma(i)>n[/tex].

Il est clair que la surjection [tex]f[/tex] a la propriété que chaque élément de [tex]\{1,\ldots,n\}[/tex] a un ou deux antécédents. On vérifie qu'on obtient ainsi toutes ces surjections, et que chacune de ces surjections est obtenue pour 48 couples [tex](u\sigma)[/tex] différents. Je te laisse vérifier ce dernier point, avec l'indication que [tex]48= 6!\times 2^2[/tex].

#14 16-09-2018 09:08:02

D_john
Invité

Re : denombrement

OK zebulor, c'est bien comme ça que j'avais compris le dénombrement à faire (càd x3). Pour moi, si une formule est fausse pour une seule valeur de n (cf. n=3) alors elle est fausse pour toute valeur de n. L'avantage de n =3, c'est qu'avec un peu de patience, on peut encore écrire l'ensemble en extension.
Au risque de me répéter, la méthode que j'ai utilisée consiste à créer 3 paires disjointes dans E (de toutes les manières possibles), ce qui me ramène à un ensemble de n éléments à mettre en bijection avec F de toutes les manières possibles. Je ne vois pas d'autres surjections que celles-ci mais peut-être me trompe-je... et dans ce cas, aviateur aussi avec ses 2 méthodes.
A+

#15 16-09-2018 10:20:32

zebulor
Invité

Re : denombrement

Je savais pas qu'on travaillait aussi le dimanche ici ! :-) On en vient au coeur du sujet! je vais réfléchir sur le raisonnement de Michel Coste. En effet D_John il me semble aussi que si une formule est fausse pour une seule valeur de n, alors elle est fausse pour le cas où n est quelconque... sauf pure coincidence...
A+

#16 16-09-2018 10:36:57

zebulor
Invité

Re : denombrement

En effet Michel Coste c'est bien cette formule !

Votre démonstration répond à mon problème. Merci.

#17 16-09-2018 17:46:07

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

Je fais remarquer que que mon x_3 et la solution donnée par M Coste c'est le même (évidemment j'ai vérifé au cas où).
Simplement je n'ai pas donné les explications et simplifié.
Alors je confirme que la formule que tu a donnée correspond bien au nombre de surjections totales.

Hors ligne

#18 16-09-2018 19:04:24

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Re : denombrement

Bonsoir,

Michel Coste a écrit :

Au total, ça fait bien

[tex] \frac1{48} n^2 (n+1) (n+3) ![/tex]

Michel Coste a écrit :

NON !
La bonne réponse est, je le répète,

[tex]\frac1{48} n(n-1)(n-2) (n+3)![/tex]

Je n'appelle pas cela se répèter mais se corriger, reste à savoir si la correction est bonne ?

Bonne soirée.


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#19 16-09-2018 19:12:23

Michel Coste
Invité

Re : denombrement

Dattier, tu devrais apprendre à lire (je veux dire, lire en comprenant ce que tu lis).

#20 16-09-2018 19:13:24

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Re : denombrement

Michel Coste a écrit :

Tu es sûr du deuxième résultat ? Ne serait-ce pas plutôt, pour le cas où trois éléments de l'ensemble d'arrivée ont deux antécédents,

[tex]\frac1{48} n(n-1)(n-2) (n+3)! [/tex]

Je rêve ou ce message a été ajouté...

Mimi, c'est pas bien de pirater le site tous cela pour avoir raison... lol


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#21 16-09-2018 19:15:40

Michel Coste
Invité

Re : denombrement

Reste délirer sur le Café mathématique, ça vaudra mieux.

#22 16-09-2018 19:25:35

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Re : denombrement

2 choses l'une, soit Mimi a piraté le site, soit Mimi a perdu sa maîtrise du sujet, en publiant 2 messages l'un aprés l'autre (sans réponse entre), comme s'il avait oublié des infos...

Dans les 2 cas, c'est pas bon pour Mimi.

Dernière modification par Dattier (16-09-2018 19:26:17)


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#23 17-09-2018 11:13:19

aviateur
Membre
Inscription : 19-02-2017
Messages : 189

Re : denombrement

Bonjour
Je ne comprends pas où tu vois un problème Dattier. M.Coste a donné  la bonne réponse avec des justifications détaillées.

Dernière modification par aviateur (17-09-2018 11:14:20)

Hors ligne

#24 17-09-2018 18:25:07

zebulor
Invité

Re : denombrement

rebonjour aux matheux et/ou aviateurs qui m 'ont répondu!

Je reviens sur ma méthode, mon raisonnement doit être faux car j'avais un 8 au lieu de 48 en dénominateur.

Voilà mon raisonnement : il y a C(n+3,2) éléments de E qui constituent un doubleton, associé à 1 singleton de F possible parmi n éléments, puis C(n+1,2) éléments de E constituant un doubletons associé à n-1 éléments possibles de F, puis un dernier doubleton de E, (il en reste C(n-1,2) associé à n-2 éléments restants de F.
Pour les parties restantes de E et F, il y a (n-3)! bijections possibles.

le nombre total me donne C(n+3,2)*n*C(n+1,2)*(n-1)*C(n-1,2)*(n-3)!  et en simplifiant ça donne (n+3)!n(n-1)(n-2)/8....

PS : C(n,p) désigne le onmbre de parties à p éléments d'un ensemble à n éléments…

Si quelqu'un peut m'aider à comprendre où se trouve mon erreur...il doit y avoir un facteur 6 qui manque

Merci

#25 17-09-2018 18:43:18

Michel Coste
Invité

Re : denombrement

C'est simple : en faisant ce que tu fais, tu choisis un ordre sur l'ensemble des éléments de F qui ont deux antécédents : le premier, le deuxième, le troisième. Combien y a-t-il de façons d'ordonner (de permutations, quoi) un ensemble à trois éléments ?

Pied de page des forums