Dénombrement

Un problème, une question, un nouveau théorème ?
Répondre

Messages : 0

Inscription : 19 nov. 2018 13:55

Profil de l'utilisateur : Élève de lycée

Dénombrement

Message par GrosBougre » 19 nov. 2018 14:27

Salut à vous, les vieux bougres!

J'ai un petit problème de dénombrement et j'ai du mal à m'en sortir. J'ai des pistes, mais je ne parviens pas à faire le calcul.

J'ai un microcontrôleur 12 bits, donc qui donne des valeurs entre 0 et 4095. Je doit relever 300 valeurs successives de ce microcontrôleur,avec la contrainte suivante: les valeurs mesurées ne peuvent que croitre. Je veux connaitre le nombre de chemins possibles qu'il est possible d'obtenir. On part de 0 à l'état 0.

Sans ma contrainte de valeur croissante, ça serait très simple (du style $ 4095^{300} $), mais le fait que les valeurs doivent être nécessairement croissante me bloque.Si on passe directement à l'état 2 à une valeur de 4095, ça donne un seul chemin pour les 298 états suivant, etc.
J'ai du mal à calculer le nombre de chemins devenu inaccessibles à chaque état en fait.

Pas certain d'avoir été assez clair, mais si quelqu'un peut m'aider à formaliser mon problème, ça serait fort sympathique!
Dernière modification par GrosBougre le 19 nov. 2018 15:46, modifié 1 fois.

Messages : 41

Inscription : 22 août 2018 15:42

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GaBuZoMeu » 19 nov. 2018 14:35

Croissant au sens large ou strictement croissant ?
La première des 300 valeurs est un 0 imposé ?

S'il s'agit de 300 valeurs en une suite croissante au sens large, sans imposer la première valeur : le coefficient binomial $$ \binom{4395}{300} $$

Messages : 0

Inscription : 19 nov. 2018 13:55

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GrosBougre » 19 nov. 2018 14:45

Merci, déjà!
Tu voulais dire $$ \binom{4095}{300} $$?

Oui, la première valeur est imposée à 0. J'ai du mal à me le présenter dans la tête. Je ne vois pas trop où intervient cette notion de croissance et donc de limitation du nombre de chemins dans le coefficient binomial.

Messages : 41

Inscription : 22 août 2018 15:42

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GaBuZoMeu » 19 nov. 2018 16:12

Non, je voulais écrire ce que j'ai écrit ! Et tu n'as pas répondu à ma question sur strictement croissant ou croissant au sens large.
Si la première des 300 valeurs est fixée à 0, on n'a pas à s'en préoccuper et on n'a donc plus que 299 valeurs à considérer. Si elles vont en croissant au sens large, c'est $$ \binom{4394}{299} $$
Si elles vont en croissant strictement, c'est $$ \binom{4095}{299} $$

Messages : 0

Inscription : 19 nov. 2018 13:55

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GrosBougre » 19 nov. 2018 16:20

Croissant, au sens large, pas nécessairement strictement croissant.
Je te crois sur parole mon brave GaBuZoMeu, mais j'essais de comprendre. J'essais de le faire "à la main" pour essayer ensuite de trouver une formule plus générale.

Si en passant de la première étape à la deuxième, je vais de 0 à 4095 directement => un seul chemin possible pour la suite
Si je passe de 0 à 4094, je peux alors au choix stagner ou alors monter de 1 à une des étapes =>299 chemins (si je ne m'abuse)

Il faut sommer tous les états comme ça, mais j'ai du mal à voir la logique de ton raisonnement.

Messages : 41

Inscription : 22 août 2018 15:42

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GaBuZoMeu » 19 nov. 2018 16:31

1e étape : on a une bijection entre l'ensemble des suites strictement croissantes de longueur $ k $ d'entiers naturels $ <n $ et l'ensemble des parties à $ k $ éléments de $ \{0,1,\ldots,n-1\} $ : à une suite, associer son image. D'accord ?
2e étape : on a une bijection entre l'ensemble des suites croissantes au sens large de longueur $ k $ d'entiers naturels $ <n $ et l'ensemble des suites strictement croissantes de longueur $ k $ d'entiers naturels $ < n+k-1 $ : à la suite $ (u_i)_{0\leq i < k} $ associer la suite $ (i+u_i)_{0\leq i < k} $. D'accord ?

Messages : 0

Inscription : 19 nov. 2018 13:55

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GrosBougre » 19 nov. 2018 16:47

Jusque ici, tout va bien.

Messages : 41

Inscription : 22 août 2018 15:42

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GaBuZoMeu » 19 nov. 2018 17:03

Si jusqu'ici tout va bien, alors tu es arrivé à bon port : c'est terminé ! :wink:

Messages : 3823

Inscription : 17 avr. 2012 21:19

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par bullquies » 19 nov. 2018 17:19

tu tires 299 valeurs au pif (sachat que 0 est la première des 300 valeurs, il en reste 299 à déterminer).

Puis il suffit de les ranger par ordre croissant, et ça te donne un chemin viable.
The Axiom of Choice is obviously true, the Well-Ordering Principle is obviously false, and nobody knows about Zorn's Lemma. - Jerry Bona

Messages : 41

Inscription : 22 août 2018 15:42

Profil de l'utilisateur : Élève de lycée

Re: Dénombrement

Message par GaBuZoMeu » 19 nov. 2018 17:25

@bullquies : et comment comptes-tu comme cela les suites croissantes au sens large ?

Répondre