Dénombrement digicode

tylnx

Bonjour à tous.
Besoin d'aide pour la dernière question de cet exercice.

A l'entrée d'un immeuble, on dispose d'un clavier de 12 touches: trois lettres $A, B$ et $C$, et les neuf chiffres autres que 0. Le code d'ouverture de la porte est composé d'une lettre suivie d'un nombre de quatre chiffres. Par exemple A 1998.
(1) Combien existe-t-il de codes différents ?
(2) Combien y a-t-il de codes
(a) comportant au moins une fois le chiffre 7 ?
(b) pour lesquels tous les chiffres sont pairs ?
(c) pour lesquels les quatre chiffres sont différents ?
(d) pour lesquels les quatre chiffres sont dans l'ordre croissant ?

Merci d'avance.

L2M

C'est vachement compliqué.

tylnx

Merci L2M . Parlant d'odre croissant, est-ce qu'on peut s'autoriser à écrire par exemple A2334 ?

L2M

Je ne sait pas, il faut le préciser dans la question. Mais on peut essayer de répondre suivant les deux sens possible de la question. Ma première réponse êtait fausse car j'ai cru au début que l'ordre est croissant successif.

tylnx

Si  un chiffre peut se répéter le nombre de cas possibles devient très grand, et donc difficile à lister. Je me s'il ya une méthode pour trouver le nombre de possiblités sans avoir à lister tous les cas.

L2M

Il faut savoir aussi qu'on peut prendre des chiffres non consécutifs, comme $A3589$.

tylnx

Effectivement!

lourrran

les chiffres sont en ordre croissant.
On peut procéder par 'disjonction' de cas (je frime avec ce mot compliqué, il va falloir assurer derrière).

-a- les 4 chiffres sont différents
-b- on a 3 chiffres différents. On compte le nombre de codes de type abc avec a<b<c, puis on multiplie par 3 parce que à partir de abc, on peut faire aabc, ou abbc ou abcc.
-c- on a 2 chiffres différents. La démarche est similaire, on compte le nombres de code de type ab avec a<b puis on multiplie par 3 parce que à partir de ab, on peut faire aaab ou aabb ou abbb.
-d- les 4 chiffres sont identiques. Là c'est simple, il y a 9 cas.

L2M

Définissons $N_k$ comme le nombre de choix possibles de 4 chiffres pris dans l'ordre croissant lorsque le premier chiffre choisi est $k$, $k=1;2;3;...;9$.

On remarque une récurrence entre les $N_k$ :

* $N_{\textcolor{blue}{7}}=N_{\textcolor{blue}{8}}=N_{\textcolor{blue}{9}}=0$.

* $N_{\textcolor{blue}{6}}=1$.

* $N_{\textcolor{blue}{5}}= \textcolor{red}{3}+N_6=4$.

* $N_{\textcolor{blue}{4}}=\textcolor{red}{6}+N_5=10$.

* $N_{\textcolor{blue}{3}}=\textcolor{red}{10}+N_4=20$.

....

Puis on remarque aussi ceci :

$\textcolor{red}{3}=C_{8-\textcolor{blue}{5}}^{2}$, $\textcolor{red}{6}=C_{8-\textcolor{blue}{4}}^{2}$, $\textcolor{red}{10}=C_{8-\textcolor{blue}{3}}^{2}$,...

Ansi :

$N_k=C_{8-k}^{2}+N_{k+1}$ avec $1\leq k \leq 6.$

D'après une sommation télescopique de $k=n$ à $k=6$ ($n\leq 6$), on trouve :

$N_n-N_7=\sum_{k=n}^{6}C_{8-k}^{2}$

$N_n=N_7+\sum_{k=n}^{6}C_{8-k}^{2}=\sum_{k=n}^{6}C_{8-k}^{2}$

* $N_{\textcolor{blue}{7}}=N_{\textcolor{blue}{8}}=N_{\textcolor{blue}{9}}=0$.

* $N_{\textcolor{blue}{6}}=C_{2}^{2}=1$.

* $N_{\textcolor{blue}{5}}= \sum_{k=5}^{6}C_{8-k}^{2}=4$.

* $N_{\textcolor{blue}{4}}=\sum_{k=4}^{6}C_{8-k}^{2}=10$.

* $N_{\textcolor{blue}{3}}=\sum_{k=3}^{6}C_{8-k}^{2}=20$.

* $N_{\textcolor{blue}{2}}=\sum_{k=2}^{6}C_{8-k}^{2}=35$.

* $N_{\textcolor{blue}{1}}=\sum_{k=1}^{6}C_{8-k}^{2}=56$.
Le nombre de possiblités est donc : $3\times (1+4+10+20+35+56)=378$.
Ici, je n'ai pas inclus les issues où il y a répétition de chiffres.

LOU16

Bonjour
Il est "connu" que $$\displaystyle\text{Card }\Big\{(x_1,x_2,\dots x_k) \in [\![1;n]\!]^k\mid \forall i\in[\![2;k]\!] ,\:x_{i-1}< x_i \Big\}=\text{ Card }\mathcal P_k([\!|1;n]\!])=\binom{n}{k}.$$

Donc: $\:\:\displaystyle 3\times\binom 94 \text{ codes de quatre chiffres dans un  ordre strictement croissant }.$

J'ai trouvé  (mais cela doit bien entendu être connu) que:$$\displaystyle\text{Card }\Big\{(x_1,x_2,\dots x_k) \in [\![1;n]\!]^k \mid \forall i\in[\![2;k]\!] ,\:x_{i-1}\leqslant x_i \Big\}=\binom{n+k-1}{k}.$$

Donc :$\:\:\displaystyle 3\times \binom{12} 4 \text{ codes avec les quatre chiffres dans l'ordre croissant }.$

On a en effet une bijection $f$ entre $E=\Big\{x \in [\![1;n]\!]^k \mid \forall i\in[\![2;k]\!] ,\:x_{i-1}\leqslant x_i \Big\}$ et $F \displaystyle =\Big\{ y\in (\N^*)^n \mid \sum_{i=1}^n y_i =n+k\Big\}.$

Elle est définie par: $\forall  (x,y)\in E\times F, \quad f(x)=y\iff \forall i\in [\![1;n]\!],\:\:y_i=1+\text{ Card }\Big\{j \in [\![1;k]\!]\mid x_j=i\Big\}.$

Math Coss

Oui, c'est connu. On peut par exemple associer à une suite croissante au sens large $x_1\le x_2 \le x_3\le x_4$ une suite strictement croissante $x_1<x_2+1<x_3+2<x_4+3$ et vice versa. 

tylnx

LOU16 a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2430518/#Comment_2430518

[Inutile de recopier l’avant dernier message. AD]

Bonjour,
Désolé pour mon absence ! 
J'ai un doute sur la formule  $$\text{Card }\Big\{(x_1,x_2,\dots x_k) \in [\![1;n]\!]^k \mid \forall i\in[\![2;k]\!] ,\ x_{i-1}\leqslant x_i \Big\}=\binom{n+k-1}{k}.$$
En effet, en testant le cas $\{1, 2, 3\}$, avec un code de trois chiffres croissants de cet ensemble,  on trouve que 7 possibilités, alors que ta formule dit qu'il y a en $10=\binom{3+3-1}{3}$.
Les sept possibilités que je trouve sont : 111, 123,  122,  133,  222,  233,  333.

L2M

Tu as oublié 112, 113 et 223.

tylnx

Merci L2M !
Il ne me reste plus qu'à comprendre la formule  donnée par LOU16.

$$\text{Card }\Big\{(x_1,x_2,\dots x_k) \in [\![1;n]\!]^k \mid \forall i\in[\![2;k]\!] ,\ x_{i-1}\leqslant x_i \Big\}=\binom{n+k-1}{k}$$

L2M

On peut procéder comme suit : 
* Le nombre de codes croissants de $k$ éléments parmi $n$ sans aucune répétition est $\binom{n}{k}$.
* Le nombre de codes croissants de $k$ éléments parmi $n$ avec une seule répétition d'un seul chiffre  est $\binom{n}{k-1}(k-1)$.
* Le nombre de codes croissants de $k$ éléments parmi $n$ avec deux répétitions d'un seul chiffre est $\binom{n}{k-2}(k-2)$... Ainsi de suite.
Donc, le nombre de codes possibles est : 
$$\binom{n}{k}+\binom{n}{k-1}(k-1)+\binom{n}{k-2}(k-2)+...+\binom{n}{1}(1)
.$$ Cette somme n'est autre que $\binom{n+k-1}{k}$.

Math Coss

Je n'ai pas lu mais visuellement il manque un facteur $k$ dans le premier terme de la dernière somme. 
Après avoir lu, je ne comprends pas : ne peut-on pas imaginer plusieurs répétitions ? Par exemple deux chiffres répétés deux fois ? Cela ajoute beaucoup de termes ! 

L2M

Si, Math Coss !

PetitLutinMalicieux

Bonjour
J'aurais dit comme Lou16, mais de façon beaucoup plus vulgaire. Si on tire 4 numéros parmi 9, ils sont forcément dans l'ordre. On tire donc 4 numéros parmi 9, indépendamment de l'ordre et avec répétition : c'est une combinaison avec répétition. $C^1_3\Gamma^4_9=3C_{9+4-1}^4=3C_{12}^4=3*495=1485$.