Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ProbabilitésTopics traitant de probabilités [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

dénombrement

Posté par dol (invité) 04-01-06 à 20:11

Bonjour, voila j'ai qq problemes avec ces deux petites questions :

Déterminer le nombre d'entiers naturels à 5 chiffres vérifiant:

1) Les chiffres sont disposés en ordre strictement croissant
2) Les chiffres sont disposés en ordre croissant

merci d'avance pour votre aide

Posté par
ottore : dénombrement 04-01-06 à 20:12

Bonjour,
qu'as tu essayé?

Essaie de voir combien de possibilités tu as de choisir le premier nombre, le deuxième , le troisième etc.

Posté par dol (invité)re : dénombrement 05-01-06 à 10:26

j'ai essayé mé je suis pas sur que ca marche car le nombre de possibilité de choisir le 2e depend du premier nombre choisi ...

Posté par philoux (invité)re : dénombrement 05-01-06 à 10:57

bonjour

je te propose une méthode à continuer et développer

Cas de croissance non stricte avec N = abcde

prenons a=0

prenons b=9 => cde=999 : (1)
prenons b=8 => cde=888 889 (2) et 899 (1)  : 1+2 = (3)
prenons b=7 => cde=777 778 779 (3) et 788 789 (2) et 799 (1)  : 1+2+3 = (6)
prenons b=6 => cde=666 667 668 669 (4) et 677 678 679 (3) et 688 689 (2) et 699 (1)  : 1+2+3+4 = (10)

tu vois apparaître une loi du type
prenons b=n => ...  : 1+2+3+4+...+n = ( n(n+1)/2 )

à continuer et à sommer puis passer à a=1 ...

Il y a sûrement plus simple, plus élégant avec des formules de proba mais ce n'est pas ma tasse de thé

En le dénombrant ainsi, c'est un peu fastidueux mais tu es certain(e) d'aboutir

Philoux



Posté par
elhor_abdelali Correcteurre : dénombrement 05-01-06 à 11:08

Bonjour otto et dol;
Juste une idée:
je crois qu'il y a autant d'entiers naturels à 5 chiffres disposés en ordre strictement croissant (respectivement croissant) qu'il y a d'applications strictement croissantes (respectivement croissantes) de l'ensemble \{1,2,3,4,5\} dans l'ensemble \{1,2,3,4,5,6,7,8,9\} et on se raméne ainsi à la question plus générale suivante:
E_p et E_n étant deux ensembles finis de cardinals respectifs p et n,
-Combien y a t il d'applications strictement croissantes de E_p dans E_n ? (rép: C_{n}^{p}).
-Combien y a t il d'applications croissantes de E_p dans E_n ? (rép: C_{n+p-1}^{p}).
Sauf erreurs...

Posté par dol (invité)re : dénombrement 08-01-06 à 12:41

je croyais que C_n^{p} représentis le nombre total de combinaisons et o pas le d'applications strictement croissante

Posté par dol (invité)re : dénombrement 09-01-06 à 18:21

svp, quelqu'un a-t-il une autre idée

Posté par
Nicolas_75 Correcteurre : dénombrement 14-01-06 à 06:30

"je croyais que C(n,p) représentis le nombre total de combinaisons et o pas le d'applications strictement croissante"
Euh... 2=1+1. Ce n'est pas pour cela que 2\neq 3-1

Déterminer le nombre d'entiers naturels à 5 chiffres vérifiant:
1) Les chiffres sont disposés en ordre strictement croissant

C'est en effet la même chose que de dénombrer le nombre d'applications strictement croissantes de \mathbb{[}1;5\mathbb{]} dans \mathbb{[}0;9\mathbb{]}.

elhor_abdelali indique que le nombre d'applications strictement croissantes de l'ensemble E de cardinal p dans F de cardinal n est égal à {n \choose p}. (On suppose évidemment ces deux ensembles disposant d'un ordre total.)

Essayons de le démontrer.

Démonstration 1
Définir une application f strictement croissante de E dans F revient simplement à choisir dans F les images, différentes deux à deux, des p éléments de E, c'est-à-dire une partie de F de cardinal p. Il y en a {n \choose p}. Ensuite, on ordonne ces p images pour les classer en ordre strictement croissant. Il n'y a qu'une seule façon de le faire. CQFD

Démonstration 2
On va procéder par récurrence sur p.
Soit la propriété :
\mathscr{P}(p) : "pour tout n, le nombre ASC(n,p) d'applications f strictement croissantes de l'ensemble E de cardinal p dans F de cardinal n est égal à {n \choose p}."
\mathscr{P}(1) est vraie.
Supposons \mathscr{P}(p) vraie et tentons de démontrer \mathscr{P}(p+1).
Soit donc un ensemble E de cardinal p+1
Soit M le plus grand élément de E.
Pour faciliter la lecture de la démonstration, on va supposer que F=\mathbb{[}1;n\mathbb{]}=\{1, 2, ..., n\} mais la démonstration reste vraie dans le cas général.
f(M) peut prendre n'importe quelle valeur dans \mathbb{[}p+1;n\mathbb{]}, car il faut au moins garder de côté les p plus petits éléments de F, pour servir d'images aux autres éléments de E.
Supposons que f(M)=k (k\in\mathbb{[}p+1;n\mathbb{]}).
Il faut ensuite déterminer les images des autres éléments de E, c'est-à-dire le nombre d'applications strictement croissantes de E\setminus\{M\} de cardinal p dans \mathbb{[}1;k-1\mathbb{]} de cardinal k-1. D'après l'hypothèse de récurrence, il y a {k-1\choose p} possibilités. Finalement, le nombre cherché vaut :
\fbox{ASC(n,p+1) = \bigsum_{k=p+1}^n{k-1\choose p}}
On reconnaît le coefficient de X^p dans :
(1+X)^p+...+(1+X)^{n-1}=(1+X)^p\frac{(1+X)^{n-p}-1}{X}
= \bigsum_{i=a}^b coefficient de X^i dans \frac{(1+X)^{n-p}-1}{X} * coefficient de X^{p-i} dans (1+X)^p
où a et b sont choisis tels que :
(i) 0\le i\le n-p-1
(ii) 0\le p-i\le p
\fbox{ASC(n)=\bigsum_{i=0}^{min(p,n-p-1)}{n-p\choose i+1}{p\choose p-i}}
On reconnaît le coefficient de X^{p+1} dans (1+X)^{n-p}(1+X)^n=(1+X)^n
Donc, finalement :
\fbox{ASC(n,p)={n\choose p+1}}
Ouf !

Sauf erreur.

Nicolas

Posté par
Nicolas_75 Correcteurre : dénombrement 14-01-06 à 06:39

Erratum. Faute de frappe.
Dans les trois encadrés de la démonstration 2, il faut lire :
\fbox{ASC(n,p+1)=...}


Rechercher
Menu
Espace membre
Changer d'île

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 1675 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 !