Dénombrement
Dénombrement
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!
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.
Re: Dénombrement
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} $$
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} $$
Re: Dénombrement
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.
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.
Re: Dénombrement
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} $$
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} $$
Re: Dénombrement
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.
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.
Re: Dénombrement
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 ?
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 ?
Re: Dénombrement
Jusque ici, tout va bien.
Re: Dénombrement
Si jusqu'ici tout va bien, alors tu es arrivé à bon port : c'est terminé !
Re: Dénombrement
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.
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
Re: Dénombrement
@bullquies : et comment comptes-tu comme cela les suites croissantes au sens large ?