Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
113 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombres de combinaisons

Envoyé par alban343 
Nombres de combinaisons
l’an passé
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.
Re: Nombres de combinaisons
l’an passé
Est-il sous-entendu qu'un nombre à six chiffres ne commence pas par $0$ ?
Re: Nombres de combinaisons
l’an passé
si , ce nombre peut commencer par 0.
Re: Nombres de combinaisons
l’an passé
Pour moi, 001234 n'est pas un nombre à 6 chiffres. Ou alors un nombre n'est plus un nombre.
Re: Nombres de combinaisons
l’an passé
oui je comprends mais dans l'exercice il l est. Merci
Re: Nombres de combinaisons
l’an passé
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.



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par Chaurien.
Re: Nombres de combinaisons
l’an passé
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 !



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par GaBuZoMeu.
Re: Nombres de combinaisons
l’an passé
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.



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par Chaurien.
Re: Nombres de combinaisons
l’an passé
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.
Re: Nombres de combinaisons
l’an passé
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



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par Chaurien.
Re: Nombres de combinaisons
l’an passé
avatar
Salut.
Pour le nombre de suites dont aucun terme n'est égal à $1$, est ce que c'est pas $(b-1)^n$ @Chaurien ?
Re: Nombres de combinaisons
l’an passé
Oups, en effet, merci. Alors la réponse est : $(b-1)^n+n(b-1)^{n-1}$, d'accord ?
Re: Nombres de combinaisons
l’an passé
avatar
Ben, j'espère que @alban343 a saisi ton raisonnement..
Re: Nombres de combinaisons
l’an passé
@ babsgueye
@alban343 a-t-il saisi mon raisonnement ? À lui de le dire ...
Re: Nombres de combinaisons
l’an passé
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.
Re: Nombres de combinaisons
l’an passé
L'aide à un poseur de question consiste-t-elle à faire l'exercice à sa place ?
Re: Nombres de combinaisons
l’an passé
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$.



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par jandri.
Re: Nombres de combinaisons
l’an passé
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.
Re: Nombres de combinaisons
l’an passé
avatar
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.



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 137 323, Messages: 1 329 157, Utilisateurs: 24 391.
Notre dernier utilisateur inscrit fonction.holomorphe.


Ce forum
Discussions: 748, Messages: 6 022.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page