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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 $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.
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
Pour le nombre de suites dont aucun terme n'est égal à $1$, est ce que c'est pas $(b-1)^n$ @Chaurien ?
@alban343 a-t-il saisi mon raisonnement ? À lui de le dire ...
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.
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$.
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.
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.