Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Dénombrement

Posté par
Weverne
17-02-19 à 18:02

Bonjour, on vient de commencer de commencer ce chapitre mais quand je vois les exercices je ne sais pas du tout commencer utiliser les formules du cours ...

Le père noel doit distribuer n cadeaux deux à deux distincts à n enfants(avec n). En supposant que le pere noel dépose les paquets au hasard, on souhaite étudier le nombre Dn de distributions qui font qu'aucun enfants n'obtienne son cadeau.

1) Que valent D1, D2 et D3 ?

Je suis vraiment pas sur mais Si Dn c'est le nombre qui fait qu'aucun enfant obtienne son cadeau alors logiquement D1=0 car il n'a aucune chance de se tromper, D2=2 car il peut se tromper et faire que les 2 enfants n'ont pas le bon cadeau ? D3=3 également ?
2) à l'aide d'un raisonnement de dénombrement. Prouver que pour tout entier n1

Dn+2=(n+1)(Dn+1+Dn


Alors la j'ai aucune idée d'ou commencer, par un dessin ça aiderait ?

3) Que valent D4 et D5 ?


J'ai besoin de la question 2 ..

4) pour tout entier n1, On pose Vn=Dn+1-(n+1)Dn
Prouver que la suite (Vn) est une suite géométrique et en déduire que : n1, Dn+1=(n+1)Dn+(-1)n+1


Je calcule Vn+1 et je tombe sur : Vn+1=(-1)*Vn du coup Vn=(-1)n+1*V1 mais après je bloque ...

5) Etablir que pour tout entier n1 :\frac{Dn}{n!}=\sum_{k=0}^{n}{\frac{(-1)^k}{k!}}

Je réclame votre précieuse aide, et aussi est-ce que les cardinals vont servir ou pas du tout ?

Posté par
carpediem
re : Dénombrement 17-02-19 à 18:22

salut

D_2 est faux ...

Posté par
Sylvieg Moderateur
re : Dénombrement 17-02-19 à 18:28

Bonjour,
D2 et D3 sont faux.
Oui, fais des dessins.

Posté par
Sylvieg Moderateur
re : Dénombrement 17-02-19 à 18:28

Bonjour carpediem

Posté par
Sylvieg Moderateur
re : Dénombrement 17-02-19 à 18:34

Deux remarques :
D'après 2), les valeurs que tu vas trouver au 1) doivent vérifier D3 = 2D2 + D1 . Si ce n'est pas le cas, c'est que tu fais une erreur.

Tu peux traiter 3) en admettant 2).

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:49

Ah oui finalement D2=0 et D3=0 ... avec le dessin ça se comprend mieux

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:49

OUPS D2=1 et D3=2 , désolé ! faute de frappe

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:51

De meme D4=9 et D5=44 avec la formule

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:52

Pour la 4) c'est le en déduire qui me perturbe, puisqu'on a montré que la suite (Vn) c'est géométrique alors il faut surement partir de la

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:53

la 2) je ne ne vois vraiment pas d'ou commencer

Posté par
Weverne
re : Dénombrement 17-02-19 à 18:56

la 4) je crois que je l'ai

Vn=(-1)n+1*V1

Or V1=1 du coup on fait passer le terme de l'autre coté pour obtenir la réponse souhaité

Posté par
Sylvieg Moderateur
re : Dénombrement 18-02-19 à 08:22

Bonjour,
Comment as-tu trouvé le n+1 en exposant ?

Pour 2), je n'ai rien trouvé de simple.
En numérotant les cadeaux : c1 c2 c3 ... cn cn+1 cn+2 et notant Cn+2 leur ensemble.
Et les enfants : e1 e2 c3 ... en en+1 en+2 et En+2 leur ensemble.
c1 ne doit pas être donné à e1.
Il y a donc n+1 choix pour donner c1 . Soit ei l'enfant qui reçoit c1 . On a i1 .
Deux cas pour le cadeau ci : Soit il est donné à e1 , soit il n'est pas donné à e1 .

Second cas : Noter c'1 = ci et Cn+1 l'ensemble des cadeaux {c'1}(Cn+2\{c1;ci}) , autrement dit les cadeaux de Cn+2 auxquels on a enlevé c1 et ci et rajouté c'1 .
Et En+1 = En+2\{ei} .
Quel est le nombre de distribution des cadeaux de Cn+1 aux enfants de En+1 tels que c'1 ne soit pas donné à e1 , c2 pas à e2 , ... , cn+2 pas à en+2 ?

Je te laisse chercher le premier cas qui est plus facile.

Posté par
carpediem
re : Dénombrement 18-02-19 à 09:45

soit c_1, c_2, ..., c_n les cadeaux correspondant aux enfants e_1, e_2, ..., e_n et a et b les cadeaux aux enfants e = e_{n + 1} $ et $ f = e_{n + 2}

distribue signifie "distribue sans qu'aucun enfants ne reçoivent son cadeau"

alors :

on distribue les n premiers cadeaux ... et il ne reste qu'une façon de distribuer les cadeaux a et b (les permuter) aux enfants e et f
ou
on distribue n - 1 des n premiers cadeaux et l'un des deux cadeaux a ou b et il ne reste qu'une façon de distribuer les deux derniers cadeaux aux enfants e et f
ou
on distribue n + 1 cadeaux à n + 1 enfants et le dernier ne doit pas recevoir son cadeau

d'où le résultat demandé ...

Posté par
Sylvieg Moderateur
re : Dénombrement 19-02-19 à 09:59

Bonjour,
Je recopie mes explications en modifiant la définition de Cn+1 :
En numérotant les n+2 cadeaux : c1 c2 c3 ... cn cn+1 cn+2 , et notant Cn+2 leur ensemble.
Et les n+2 enfants : e1 e2 e3 ... en en+1 en+2 , avec En+2 leur ensemble.
c1 ne doit pas être donné à e1.
Il y a donc n+1 choix pour donner c1 . Soit ei l'enfant qui reçoit c1 . On a i1 .
Deux cas pour le cadeau ci : Soit il est donné à e1 , soit il n'est pas donné à e1 .

Second cas : Noter Cn+1 = Cn+2\{c1} et En+1 = En+2\{ei} .
Puis noter c'1 = ci .
Les numéros des cadeaux sont alors 1,2,...,n+2 sauf i .
Idem pour les numéros des enfants.
On est dans le second cas ; donc c'1 n'est pas donné à e1 .
Quel est le nombre de distribution des cadeaux de Cn+1 aux enfants de En+1 tels que c'1 ne soit pas donné à e1 , c2 pas à e2 , ... , cn+2 pas à en+2 ?

Je laisse chercher le premier cas qui est plus facile.

Ps à carpediem
Je n'ai pas compris tes explications

Posté par
carpediem
re : Dénombrement 19-02-19 à 10:15

quand on distribue n + 2 cadeaux alors on distribue n cadeaux aux n premiers enfants (et il faut distribuer les deux derniers cadeaux) ou on distribue n + 1 cadeaux aux n + 1 premiers enfants (et il faut distribuer le dernier cadeau)

dans chaque cas (disjoint) les deux derniers cadeaux ou le dernier ne doivent pas être celui qui est prévu aux enfants

Posté par
Weverne
re : Dénombrement 19-02-19 à 19:55

Je vais pas vous mentir je me sens vraiment pas capable la maintenant de mener de telle raisonnement mais j'essaie de comprendre les votres

Et si sylvieg n'a pas compris celui carpediem comment moi je pourrais comprendre

Ce que je ne comprend pas sylvieg c'est vous dites que le cadeau 1 ne doit pas etre donné à l'enfant 1 puis vous faites après le cas ou on lui donne et je ne comprend pas pourquoi

Citation :
Il y a donc  n+1  choix pour donner  c1 . Soit  ei   l'enfant qui reçoit  c1 . On a  i1 .
Deux cas pour le cadeau  ci  : Soit il est donné à  e1 , soit il n'est pas donné à  e1 .

Enfaite qu'on lui donne et qu'on lui donne pas qu'est-ce qu'on arrive à en tirer ?

Posté par
carpediem
re : Dénombrement 19-02-19 à 21:15

la relation de récurrence est D_{n + 2} = (n + 1)(D_{n + 1} + D_n)

et elle fait intervenir les deux termes précédent donc ce qui se passe soit après avoir distribué n cadeaux soit après en avoir distribué n + 1

carpediem @ 18-02-2019 à 09:45

soit c_1, c_2, ..., c_n les cadeaux correspondant aux enfants e_1, e_2, ..., e_n et a et b les cadeaux aux enfants e = e_{n + 1} $ et $ f = e_{n + 2}

distribue signifie "distribue sans qu'aucun enfants ne reçoivent son cadeau"

alors :

on distribue les n premiers cadeaux ... et il ne reste qu'une façon de distribuer les cadeaux a et b (les permuter) aux enfants e et f soit une issue et il y a D_n façons de le faire
ou
on distribue n - 1 des n premiers cadeaux et l'un des deux cadeaux a ou b et il ne reste qu'une façon de distribuer les deux derniers cadeaux aux enfants e et f soit n issues de choisir le cadeau parmi les n qu'on ne distribue pas et il y a toujours D_n façons de le faire
ou
on distribue n + 1 cadeaux à n + 1 enfants et le dernier ne doit pas recevoir son cadeau soit n + 1 issues de choisir le cadeau parmi les n + 1 qu'on ne donnera pas puisque'on le donnera au n + 2-ième enfant et il y a d_{n + 1} façons de le faire

d'où le résultat demandé ...

Posté par
Sylvieg Moderateur
re : Dénombrement 19-02-19 à 22:50

@Weverne,
Si tu veux essayer de comprendre mes explications :

Utilise un schéma avec 2 colonnes. Celle de gauche qui représente les cadeaux numérotés 1,2,...,n+2 et celle de droite qui représente les enfants numérotés 1,2,...,n+2.

Commence par chercher le premier cas qui est plus facile :
Le cadeau numéroté 1 est donné à l'enfant numéroté i et le cadeau numéroté i est donné à l'enfant numéroté 1.
Sur le schéma, tu fais une flèche du cadeau numéroté 1 vers le milieu de la colonne de droite où tu marques dans les pointillés un enfant numéroté i .
A l'horizontale, tu marques le cadeau numéroté i dans la colonne de gauche, puis tu fais une flèche de ce cadeau vers l'enfant numéroté 1 .
De combien de manière peut-on terminer la distribution ?

Posté par
Sylvieg Moderateur
re : Dénombrement 20-02-19 à 08:43

Bonjour,
J'ai mieux relu ceci dans ton message :

Citation :
vous dites que le cadeau 1 ne doit pas etre donné à l'enfant 1 puis vous faites après le cas ou on lui donne

Non, je fais 2 cas pour le cadeau ci , le cadeau numéroté i :
Soit il est donné à l'enfant numéroté 1 , soit il est donné à un enfant ni numéroté 1, ni numéroté i .

Dans ces 2 cas, je ne parle plus du cadeau numéroté 1 .
Le cadeau numéroté 1 a déjà été donné à un des n+1 enfants pas numéroté 1 .

Posté par
loulouem
re : Dénombrement 08-01-24 à 18:17

Bonsoir, j'ai exactement le même exercice en devoir maison mais je galère énormément sur les questions 4 et 5
j'ai fait la 4a bien que je ne sois pas sur et il me reste la 4b et la 5, auriez vous une solution avec explications à me donner  s'il vous plaît ? 🙏

Posté par
MattZolotarev
re : Dénombrement 08-01-24 à 18:56

loulouem @ 08-01-2024 à 18:17

Bonsoir, j'ai exactement le même exercice en devoir maison mais je galère énormément sur les questions 4 et 5
j'ai fait la 4a bien que je ne sois pas sur et il me reste la 4b et la 5, auriez vous une solution avec explications à me donner  s'il vous plaît ? 🙏


Une solution, non, une explication peut-être !

Une fois que tu as montré que (v_n) est géométrique, tu peux déduire son terme général avec une formule de Première. Normalement, tu trouves que pour tout n\geqslant 1, v_n=(-1)^{n+1}.

Or, tu sais que pour n\geqslant 1,\ v_n=D_{n+1}-(n+1)D_n... Donc la 4.b. se fait en une ligne... !

Pour la question 5., pourquoi ne pas tenter une récurrence (en utilisant la relation que l'on a entre D_{n} et D_{n+1}) ?

La question la plus difficile pour moi reste clairement la 2.

Posté par
MattZolotarev
re : Dénombrement 08-01-24 à 19:00

(Sinon, pour plier cet exo en 2 secondes, montrer que pour n\in\mathbb{N}^*, n!=\underset{k=0}{\overset{n}{\sum}}\begin{pmatrix}n\\k\end{pmatrix} D_k, puis conclure avec la formule d'inversion de Pascal



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1682 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !