Nombres de combinaisons — Les-mathematiques.net The most powerful custom community solution in the world

Nombres de combinaisons

Bonsoir,


Pourriez-vous m'aider à résoudre cela ? Combien de nombres à 6 Chiffres peut-on former si le 0 n'est jamais après le 3 ?

Je pense pouvoir le faire en étudiant toutes les positions possibles ou le 0 est après le 3 mais j'imagine qu'il y a une méthode plus mathématique.
Merci.

Réponses

  • Est-il sous-entendu qu'un nombre à six chiffres ne commence pas par $0$ ?
  • si , ce nombre peut commencer par 0.
  • Pour moi, 001234 n'est pas un nombre à 6 chiffres. Ou alors un nombre n'est plus un nombre.
  • oui je comprends mais dans l'exercice il l est. Merci
  • GBZM a raison, le seul nombre entier naturel dont l'écriture décimale commence par 0, c'est 0 ! Pour le dénombrement, au lieu de parler de nombres à 6 chiffres, parlons de suites de 6 chiffres et tout le monde sera content. Mais on peut se poser aussi la question du nombre de ces suites qui ne commencent pas par 0, et qui sont alors légitimement des écritures décimales de nombres entiers naturels.
  • On peut plutôt compter les suites de chiffres qui contiennent un 30. Mais il faut juste faire attention qu'une suite de 6 chiffres peut contenir deux 30, voire trois 30.
    Un doute me saisit : comment faut-il comprendre "le 0 n'est jamais après le 3". Faut il comprendre qu'on n'a pas de 30 ? Ou alors, que s'il y a un 3 quelque part, il n'y a aucun 0 à droite ?
    Décidément, cet énoncé est très mal fichu !
  • Soit un entier $b \geq 2$. On cherche le nombre $x_n$ de $n$-suites de $\{0,1,...,b-1\}$ dans lesquelles il n'y ait jamais $0$ après $1$.
    Soit $y_n$ le nombre de ces suites se terminant par $1$, et $z_n$ le nombre de ces suites ne se terminant pas par $1$.
    Alors : $x_{n+1}=(b-1)y_n+bz_n$, $x_n=y_n+z_n$, $y_n=x_{n-1}$.
    Si je n'ai pas fait d'erreur, ça résout le problème ; mais dans ces trucs-là une erreur est vite arrivée.
    Bonne soirée.
    Fr. Ch.
  • Ah oui, je comprends l'objection de GBZM. Moi j'ai compris que juste après 3 il n'y a pas 0, et c'est tout. Par exemple pour moi 310 convient. Mais si l'on ne veut aucun 0 après un 3, c'est autre chose. Bon, ça fait deux problèmes pour le prix d'un seul. J'espère en avoir résolu un.
  • Soit un entier $b \geq 2$. On cherche le nombre de $n$-suites de $\{0,1,...,b-1\}$ pour lesquelles il n'y a jamais aucun $0$ parmi tous les termes qui suivent un $1$.
    Cherchons le nombre de ces suites pour lesquelles le premier $1$ est en $k$-ème position. Ce nombre est : $(b-1)^{k-1}·1·(b-1)^{n-k}=(b-1)^{n-1}$. C'est aussi le nombre de ces suites dont aucun terme n'est égal à $1$, et qui conviennent donc. Le nombre demandé est donc : $(n+1)(b-1)^{n-1}$.
    Une erreur, signalée ci-après par babsgueye, et corrigée à la suite en conséquence
  • Salut.
    Pour le nombre de suites dont aucun terme n'est égal à $1$, est ce que c'est pas $(b-1)^n$ @Chaurien ?
  • Oups, en effet, merci. Alors la réponse est : $(b-1)^n+n(b-1)^{n-1}$, d'accord ?
  • Ben, j'espère que @alban343 a saisi ton raisonnement..
  • @ babsgueye
    @alban343 a-t-il saisi mon raisonnement ? À lui de le dire ...
  • Je reviens sur la première interprétation. On a un entier $b \ge 2$ et l'on cherche le nombre $x_n$ de $n$-suites de $\{0,1,...,b-1\}$ dans lesquelles il n'y a jamais un $1$ (ou un $3$, si $b \ge 4$) suivi de $0$.
    Si ce que j'ai écrit plus haut est correct, on a : $x_{n+1}=b x_n -x_{n-1}$. C'est donc une suite à récurrence linéaire d'ordre 2, à coefficients constants, avec conditions initiales : $x_1=b$, $x_2=b^2-1$. On peut prolonger la récurrence par $x_0=1$.
    On trouve l'expression de $x_n$ selon la méthode bien connue pour ce type de suite. Pour $b \ge 3$ l'équation caractéristique a deux racines réelles, qui donnent cette expression, mais la formule obtenue, avec ses racines carrées, est de peu d'intérêt pratique si l'on veut la valeur numérique de $x_6$ pour $b=9+1$. Mieux vaut faire de proche en proche les calculs de $x_3$, $x_4$, $x_5$, $x_6$, c'est pas la mer à boire. On trouve si je ne me trompe : $950~599$.

    Si l'on veut seulement, parmi ces $n$-suites, celles qui sont de vraies écritures de nombres à $n$ chiffres, selon l'objection de GBZM, c'est-à-dire qui ne commencent pas par $0$, on peut observer que le nombre de ces $n$-suites commençant par $0$ est $x_{n-1}$, et que donc les autres sont au nombre de $x'_n=x_n-x_{n-1}$. Même remarque vaut pour l'autre interprétation de ce problème.

    Bonne journée, encore chaude.
    Fr. Ch.
  • L'aide à un poseur de question consiste-t-elle à faire l'exercice à sa place ?
  • On peut généraliser en dénombrant les mots de $n$ lettres formés à partir d'un alphabet de $N$ lettres $(L_1,\cdots,L_N)$:
    1) qui ne possèdent pas le sous-mot $L_1L_2\cdots L_r$
    2) qui ne possèdent pas les lettres $L_1,L_2,\cdots ,L_r$ dans cet ordre, consécutivement ou non.

    Pour le premier cas il existe une formule (relativement) simple avec un sigma de $0$ à $\lfloor n/r\rfloor$, un coefficient binomial et une puissance de $N$.
    Pour le second cas il existe une formule simple avec un sigma de $0$ à $r-1$, un coefficient binomial et une puissance de $N-1$.
  • Suite à mon dernier message, contrairement à ce que j'ai écrit, on peut tout de même exploiter la formule qui donne directement $x_n$ en fonction de $n$.
    Soit $b\geq 3$. L'équation caractéristique de la récurrence $x_{n+1}=b x_n -x_{n-1}$ est : $t^{2}-bt+1=0$.
    Ses racines sont : $\alpha =\frac{b+\sqrt{b^{2}-4}}{2}$ et $\beta =\frac{b-\sqrt{b^{2}-4}}{2}$, qui vérifient : $\alpha +\beta =b$, $\alpha \beta =1$, $\alpha -\beta =\sqrt{b^{2}-4}>1$, $0<\beta <1<\alpha $.
    On a : $x_{n}=\frac{\alpha ^{n+1}-\beta ^{n+1}}{\alpha -\beta }$, soit : $\frac{\alpha ^{n+1}}{\alpha -\beta }=x_{n}+\frac{\beta ^{n+1}}{\alpha -\beta }$.
    D'où l'expression : $x_{n}=\left\lfloor \frac{\alpha ^{n+1}}{\alpha -\beta }\right\rfloor=\left\lfloor \frac{1}{\sqrt{b^{2}-4}}(\frac{b+\sqrt{b^{2}-4}}{2})^{n+1}\right\rfloor $.
    Par exemple pour $b=9+1$ et $n=6$, on retrouve le résultat que j'ai dit.
    Bonne après-midi.
    Fr. Ch.
  • Moi j'avais vu sous tes résultats @Chaurien, un raisonnement élémentaire de dénombrement (avec des $n$-listes) en voyant que tu avais généralisé en travaillant en base $b$ ($b\geq 2$ quelconque).
    Du coup le raisonnement tenu pour $1$, peut être tenu pour n'importe quel nombre de la liste $\{0, 1, 2,\ldots, b-1\}$ à la place de $1$.
    @alban343 obtient aisément alors sa réponse, en prenant $b = 10$ et $ n=6$.

    Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!