Dénombrement digicode

tylnx
Modifié (June 2023) dans Combinatoire et Graphes
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.

Réponses

  • L2M
    L2M
    Modifié (June 2023)
    C'est vachement compliqué.
  • Merci L2M . Parlant d'odre croissant, est-ce qu'on peut s'autoriser à écrire par exemple A2334 ?
  • 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.
  • 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
    L2M
    Modifié (June 2023)
    Il faut savoir aussi qu'on peut prendre des chiffres non consécutifs, comme $A3589$.
  • Effectivement!
  • 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.


    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • L2M
    L2M
    Modifié (June 2023)
    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
    Modifié (June 2023)
    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
    Modifié (June 2023)
    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
    Modifié (June 2023)
    [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.
  • Tu as oublié 112, 113 et 223.
  • tylnx
    Modifié (June 2023)
    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
    L2M
    Modifié (June 2023)
    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
    Modifié (June 2023)
    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 ! 
  • PetitLutinMalicieux
    Modifié (June 2023)
    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$.
Connectez-vous ou Inscrivez-vous pour répondre.