Dénombrement pour un ensemble
-
?Un Ancien Utilisateur dernière édition par
Bonjour
J'ai quitté la terminale il y a déjà qq années (pour ainsi dire plus de 10 ans !) et mes notions sur les ensembles ne sont plus suffisantes pour arriver à faire un dénombrement correct...
J'aimerais trouver le nombre de combinaisons possibles respectant les consignes suivantes
- le n-uplet est constitué n variables de (x1, x2, ..., xn)
- x1, x2, ..., xn sont entiers
- les n variables sont liées par la loi 0 ≤ min ≤ x1 ≤ x2 ≤ ... ≤ xn-1 ≤ xn ≤ max
Exemple : si je prends min = 1, max = 3, n = 3, j'ai 10 triplets possibles qui sont
(1,1,1) (1,1,2) (1,1,3) (1,2,2) (1,2,3) (1,3,3) (2,2,2) (2,2,3) (2,3,3) et (3,3,3)J'aimerais arriver à déterminer ce nombre de combinaisons avec une formule du type
nombre de combinaison = f(n, max, min)Je n'arrive pas à trouver une fonction exacte pour tous les cas triviaux que je pose et je n'ai encore moins de démonstration qui puisse me garantir qu'une telle fonction soit bonne
--> qqn pourrait-il SVP m'aider ?Merci
-
Mmathtous dernière édition par
Bonjour,
n, le nombre de nombres, dépend de min et de max : ce n'est pas un paramètre libre.
D'ailleurs, n = max-min +1 (+1 puisqu'on compte à la fois min et max).
Connaissant n, il est alors facile de trouver le nombre de n-uples.
-
?Un Ancien Utilisateur dernière édition par
ahhhh... j'ai dû louper une étape car je ne vois pas la "facilité" :s
désolé d'avoir perdu toutes ces notions...
-
Mmathtous dernière édition par
Dans ton exemple, n=3 : combien trouves-tu de triplets ?
Prends un autre exemple. Par exemple min = 5 et max = 6. Que vaut n ? Combien de n-uples ?
-
?Un Ancien Utilisateur dernière édition par
Dans mon exemple, je trouve 10 triplets
Dans l'autre exemple, je ne vois pas ce qui m'empêche de prendre n = 8 ou n = 2000. J'aurais respectivement 8 et 2000 n-uples comme solution.
Mais le fait que max = min + 1 simplifie largement l'équation !
-
Mmathtous dernière édition par
Citation
Dans mon exemple, je trouve 10 tripletsLe mot "triplet" signifie des ensembles de 3 éléments ordonnés.
Ainsi, le triplet (1,1,2) est différent du triplet (1,2,1) que tu ne donnes pas.
Il faut préciser l'énoncé : s'agit-il de triplets ou d'ensembles non ordonnés ?
-
?Un Ancien Utilisateur dernière édition par
AAhh j'ai du mal m'exprimer... désolé...
Je voulais dire "ensemble de trois valeurs"Si je reformule, j'aimerais trouver le nombre de combinaisons possibles respectant les consignes suivantes
- la combinaison est constitué n variables de (x1, x2, ..., xn)
- x1, x2, ..., xn sont entiers
- les n variables sont liées par la loi 0 ≤ min ≤ x1 ≤ x2 ≤ ... ≤ xn-1 ≤ xn ≤ max
L'exemple reste identique mais par exemple la combinaison (1,2,1) ne peut respecter mes conditions car dans ce cas x2 > x3
-
Mmathtous dernière édition par
En fait, il manque encore une précision.
J'ai écrit :
Citation
n = max-min +1Mais en fait, il est possible que n soit plus petit : max-min +1 est alors le maximum que peut valoir n.
Qu'en est-il exactement ?
-
?Un Ancien Utilisateur dernière édition par
justement, je n'ai aucune certitude sur le lien entre max, min et n. De mon point de vue, c'est totalement indépendant
n peut valoir 2000000 même si min = 2 et max = 6 par exemple
-
?Un Ancien Utilisateur dernière édition par
Qqn vient de me guider ici : http://fr.wikipedia.org/wiki/Combinaison_avec_répétition
Je crois que cela me donne la réponse
Etes vous du même avis ?
-
Mmathtous dernière édition par
Oui, d'ailleurs, j'ai une solution comparable ici :
solution
Toutefois, ce que Wikipedia nomme k, que je nomme p, que tu nommes n (bonjour les changements de notations !) est inférieur ou égal à max-min +1.
Cela ne change rien toutefois.
Par exemple si min =2 et max = 3, les xi ne peuvent valoir que 2 ou 3, qu'ils soient 1000 (dont beaucoup seront égaux) ou seulement deux.
Les suites seront donc (2,2), (2,3), et (3,3).
-
?Un Ancien Utilisateur dernière édition par
Merci ! bien que je n'ai pas saisi toute la démo, j'ai maintenant de quoi avancer sur mon soucis
Ps: aahhhh c'est pas beau de vieillir
on oublie tout, même (et surtout ?) les maths
-
Mmathtous dernière édition par
Non, non : c'est moi qui suis en tort (ce qui ne m'empêche pas d'être vieux aussi, et même davantage) : je voulais à tout prix que n soit inférieur ou égal à Max - min + 1. Mais ce n'est nullement obligatoire.
Ce qui est obligatoire c'est que n soit inférieur ou égal à Max-min+n, ce qui est automatiquement vérifié.
La démonstration est basée sur le transfert de la suite (xi) vers la suite (bi) qui elle, est strictement croissante.
Bon courage.
-
?Un Ancien Utilisateur dernière édition par
en tous les cas, merci beaucoup ! ça me retire une belle épine du pied et je pourrais expliquer tout cela en frimant mercredi prochain aux collègues (en faisant croire que c'est dans mes bonnes résolutions 2013 :D)
Passez un bon réveillon
-
Mmathtous dernière édition par
Bonnes fêtes de fin d'année également.