Dénombrement

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

dénombrement

par aviateur » 15 Sep 2018, 10:12

Bonjour
Je propose cet exercice de dénombrement que j'ai vu quelque part.
Soit un entier naturel et deux ensembles E et F tels que card(E)=n+3 et card(F)= n.
Quel est le nombre de surjections de E sur F?



nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: dénombrement

par nodgim » 15 Sep 2018, 10:41

Je dirais :

n ^ (n+3) - somme (k de 1 à n ) { C(n+3, k) * ( n - k ) ^ ( n + 3 ) }

aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

Re: dénombrement

par aviateur » 15 Sep 2018, 11:01

Bonjour
Non c'est pas ça. Honnêtement je ne l'ai pas encore fait. On m'a donné une formule mais je ne l'ai pas vérifiée.
Mais pour n=2 c'est facile de voir qu'il y a 30 surjections et toi ça fait 27.

aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

Re: dénombrement

par aviateur » 15 Sep 2018, 12:00

Rebonjour
Je viens de faire les calculs alors j'ai une solution qui ressemble un peu à la tienne (dans sa forme). Je pense que tu as dû faire une petite erreur surement rectifiable.
Cependant la solution qui m'est donnée a une forme plus sympathique, elle est donnée sous la forme d'un produit (alors qu'ici elle est sous la forme d'une somme).
Les deux solutions coïncident mais par contre à première vue je ne vois pas comment passer de cette forme "somme" à la forme "produit".
A mon avis il faudrait refaire le dénombrement d'une autre façon.
Je ne donne pas le résultat pour laisser chercher celui qui est intéressé.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 12:11

Bonjour, regarde ce document c'est intéressant : http://www.klubprepa.fr/Site/Document/C ... ument=3616

aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

Re: dénombrement

par aviateur » 15 Sep 2018, 13:21

Merci LB2, j'avais la formule sous forme d'une somme. Mais grosso c'est la question 11 (en l'adaptant) qui donne la solution de l'exercice sous la forme d'un produit.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 13:34

Oui, mais je suis en train de me perdre un peu dans les calculs... Tu obtiens quoi comme formule close? C'est aisé une fois qu'on a "intuité" la formule de la démonter par récurrence.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 14:10

Avec un peu d'aide de wolfram, j'obtiens

En fait la relation de récurrence obtenue par la Q11. peut permettre d'obtenir le résultat avec le changement de variable pour se ramener à un polynôme en n

Mais ce que j'aimerais bien avoir c'est une preuve combinatoire directe : à savoir distinguer les cas "un élément est atteint 4 fois", "1 élément est atteint 2 fois et 1 élément est atteint 3 fois" , "3 éléments sont atteint 2 fois"
et dénombrer chaque cas.

aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

Re: dénombrement

par aviateur » 15 Sep 2018, 15:23

Oui c'est la formule donnée.
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, on factorise et on tombe sur la formule.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 15:34

Merci beaucoup et bravo pour cet éclaircissement, cela répond exactement à ma question

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: dénombrement

par nodgim » 15 Sep 2018, 17:35

Mon raisonnement était celui là :
C'est le nombre de nombre à n+3 chiffres exprimés en base n, hormis les nombres qui ne possèdent pas au moins une fois tous les chiffres de la base.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 18:10

c'est intéressant, peux tu détailler un peu? la somme s'arrête à n-1 non ?

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: dénombrement

par nodgim » 15 Sep 2018, 18:19

Re-correction (cette fois , la formule a été comparée avec la formule produit)

n ^ (n+3) - somme (k de 1 à n ) { C(n, k) * ( n - k ) ^ ( n + 3 ) * (-1) ^ k }

Oui, on l'arrête à n-1, c'est plus beau "n" que "n-1"

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 15 Sep 2018, 19:07

c'est un crible de poincaré?

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: dénombrement

par nodgim » 15 Sep 2018, 20:37

Ah ! Je ne savais pas que ça s'appelait comme ça. C'est une écriture assez courante en dénombrement.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21481
Enregistré le: 11 Nov 2009, 23:53

Re: dénombrement

par Ben314 » 15 Sep 2018, 23:50

nodgim a écrit:Ah ! Je ne savais pas que ça s'appelait comme ça.
Tu es comme moi : de l'époque où, en France, on n'avait pas encore la manie d’attribuer des nom propres à tout les théorème et définitions. Bref, pour les vieux cons comme moi (et toi ?), ça s'appelle le principe d'inclusion-exclusion
Remarque :
- Faut dire qu'on était sacrément con dans le temps : rien qu'avec le nom du théorème tu risquait de savoir de quoi tu parle. Quelle horreur !!!
- Sans parler du fait que, pour pouvoir te faire mousser en société avec du "jargon jargonesque", c'était vraiment nul à chier. Depuis qu'on utilise en France le "Théorème d'Al-Kashi" on voit tout de suite qu'on est bien plus balèze que tout les autre abrutis d'étrangers avec leur débile "Loi des cosinus".


EDIT :
D'un autre coté, je comprend pas bien où ça pourrait te servir le principe d'inclusion-exclusion pour calculer les bidules :
Si on note le nombre de surjections d'un ensemble à éléments dans un ensemble à éléments, alors il me semble que le premier truc qui vient à l'esprit, c'est quand même d'écrire que, pour entièrement déterminer une application (quelconque) d'un ensemble à éléments dans un ensemble à on peut :
1) Choisir un certain nombre d'élément à l'arrivée.
2) Puis choisir une surjection de l'ensemble de départ sur les éléments en question.
Donc et ça me semble archi-classique d'inverser ce type de système linéaire (il me semble que, dés qu'on voit la notion de système linéaire et de matrices associées, on voit en exercice quel est l'inverse de la matrice formée des coeff. binomiaux, non ?)

Mais bon, y'a sûrement d'autre méthodes (mais plus simple, j'y crois pas bien).
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

nodgim
Habitué(e)
Messages: 2002
Enregistré le: 27 Jan 2008, 12:21

Re: dénombrement

par nodgim » 16 Sep 2018, 10:56

Euh, sûrement Ben, mais bon mes restes d'étude de Lycée sont loin....

C'est d'ailleurs intéressant de donner ce qui en est resté dans la mémoire : Dès 3 mois et plus en TC d'espaces vectoriels il n'en reste pratiquement rien. Matrices: Idem. Algèbre : peut être est ce dû aux graphes qu'on visualise facilement, c'est sans doute ce qui a été le mieux conservé.
Modifié en dernier par nodgim le 16 Sep 2018, 20:10, modifié 1 fois.

LB2
Habitué(e)
Messages: 1504
Enregistré le: 05 Nov 2017, 18:32

Re: dénombrement

par LB2 » 16 Sep 2018, 10:57

Oui Ben, cette méthode est très naturelle, et permet d'obtenir les Sn,p avec un procédé connu dans certains livres comme "formule d'inversion de Pascal", ce qui revient à résoudre le système linéaire associé.

Le principe d'inclusion-exclusion est une autre façon d'obtenir le même résultat

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 69 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite