Compter le nombre de chaînes — Les-mathematiques.net The most powerful custom community solution in the world

Compter le nombre de chaînes

Bonjour à tous,
j'ai un problème à résoudre mais je ne sais comment m'y prendre.
Je dois estimer le nombre de chaînes de 8 caractères alphanumériques possible...
Jusque la tout va bien, c'est 36^8

Mais j'ai une contrainte supplémentaire : les chaînes doivent avoir au moins 2 caractères différents entre elles. Pardonnez mon usage des notations mathématiques qui sera sans doute approximatif :

- je considère xn et yp pouvant prendre les valeurs [0,1,2,...,36]
- je considère les chaines (x1,x2,x3,x4,x5,x6,x7,x8) et (y1,y2,y3,y4,y5,y6,y7,y8)

Si (x1 = y1) et (x2 = y2) et (x3 = y3) et (x4 = y4) et (x5 = y5) et (x6 = y6)
Alors, je dois obligatoirement avoir (x7 <> y7) et (x8 <> y8)


EDIT : merci à GaBuZoMeu qui a reformulé mon problème de manière intelligible :

Quel est le nombre maximal d'éléments d'un ensemble A de chaînes de caractères de longueur 8 (sur un alphabet de 36 caractères) tel que deux éléments distincts de A diffèrent toujours en au moins deux places ?


Pourriez-vous m'aider à calculer ce nombre et à comprendre la méthodologie employée s'il vous plaît ? Mes connaissances en combinatoire et dénombrement sont plus que maigres et datent de plus de 10 ans...
Merci d'avance pour votre aide précieuse.
Kill

Réponses

  • Il est plus simple de regarder "l'événement complémentaire". Ça veut dire quoi que ta condition d'existence de deux caractères distincts n'est pas respectée ? Ça veut juste dire que ta chaîne est de la forme $xxxxxxxx$,où $x$ est l'un des $36$ caractères possibles. Il y a donc... mauvais cas, et tu peux les retirer de ta liste de $36^8$ chaînes ! ;-)
  • Bonjour et merci pour le temps accordé à ma question.
    Je me rend compte que j'ai mal exprimé ma condition. Effectivement, si je devais juste retirer est chaines faites d'un unique caractère, c'aurait été trop simple.

    J'essaie de modéliser le problème et je l'ajoute dans mon premier poste. pardonnez mon usage des notations mathématiques qui sera sans doute approximatif :

    - je considère xn et yp pouvant prendre les valeurs [0,1,2,...,36]
    - je considère les chaines (x1,x2,x3,x4,x5,x6,x7,x8) et (y1,y2,y3,y4,y5,y6,y7,y8)

    Si (x1 = y1) et (x2 = y2) et (x3 = y3) et (x4 = y4) et (x5 = y5) et (x6 = y6)
    Alors, je dois obligatoirement avoir (x7 <> y7) et (x8 <> y8)

    mais ça pourrait etre les 2 premiers termes qui soient différents entre eux, oubien le premier et le 6ème etc...
  • Je n'ai rien compris. Tu commences par supposer que $(x_1, \dots, x_8) = (y_1, \dots, y_8)$ puis tu dis "alors $x_7 \neq y_7$ et $x_8 \neq y_8$". Honnêtement je ne peux pas t'aider si tu n'expliques pas clairement ta question.
  • pardon, je viens de corriger.
    par ailleurs, comment faire pour insérer les caractères spéciaux comme le "=" barré ? quand je publie le message, il le remplace par un "?"
  • Ta question est toujours aussi incompréhensible.

    Tu dis vouloir compter les chaînes de caractères possédant une certaine propriété. Laquelle ?
    Est-ce qu'il faut comprendre ce que tu racontes comme ça :
    On se donne une chaîne de longueur 8. On veut compter toutes les chaînes de caractères qui diffèrent de la chaîne donnée en au moins deux places.

    Ou alors, ton problème n'est pas de compter les chaînes de caractères possédant une certaine propriété, mais un problème du genre : quelle est le plus grand nombre d'éléments possible pour un ensemble de chaînes dans lequel deux chaînes distinctes quelconques diffèrent en au moins deux places ?
  • Je suis désolé si je ne suis pas clair, mais mon problème est bien celui que tu décris :

    Compter les chaînes de caractères possédant une certaine propriété, mais un problème du genre : quelle est le plus grand nombre d'éléments possible pour un ensemble de chaînes dans lequel deux chaînes distinctes quelconques diffèrent en au moins deux places ?
  • Toujours aussi peu clair, même quand tu me cites !!!

    Ton problème est bien :

    Quel est le nombre maximal d'éléments d'un ensemble $A$ de chaînes de caractères de longueur 8 (sur un alphabet de 36 caractères) tel que deux éléments distincts de $A$ diffèrent toujours en au moins deux places ?

    Réponds oui ou non, comme ça on saura à quoi s'en tenir.
  • On a exactement 36^7 solutions.
    Recherche 'cle de controle code barre EAN13' pour avoir l'explication
  • Ce à quoi lourrran fait allusion est, je pense, le système du "bit de parité", sauf qu'au lieu d'avoir des éléments de $\Z/2\Z$ comme "bits" on a des éléments de $\Z/36\Z$. On conserve les chaînes dont la somme des "bits" dans $\Z/36\Z$ est égale à $0$. Deux chaîne distinctes dans ce sous-ensembles ont forcément au moins deux "bits" qui diffèrent, et ce sous-ensemble a $36^7$ éléments (on peut choisir arbitrairement les $36$ premiers bits, le huitième est alors entièrement déterminé).
  • En d'autres mots, chaque caractère est un nombre entre 0 et 35. On détermine les 7 premiers caractères ($36^7$ possibilités) ; et à partir des 7 premiers caractères, on détermine le 8ème.
    Exemple de formule : $n_8 = mod ( n_1 +n_2 +n_3 + n_4 + n_5 + n_6 + n_7,36) $

    Prenons 2 chaines différentes.
    Soit il y a déjà au moins 2 caractères qui sont différents dans les 7 premières positions, et ces chaines conviennent.
    Soit il y a un seul caractère qui les différencie dans les 7 premières positions, et alors le 8ème caractère donné par cette formule sera forcément différent.

    On a donc l'assurance que toutes les chaines construites ainsi prises 2 à 2 ont au moins 2 caractères différents.
  • Il n'est peut-être pas tout à fait évident que le dispositif du "bit de parité" réalise bien le maximum.
    Soit $N$ le cardinal d'un ensemble $A$ de chaînes tel que deux d'entre elles diffèrent toujours au moins en deux places. On a l'habitude d'appeler "distance de Hamming" entre deux chaînes de même longueur le nombre de places où elles différent. La distance non nulle minimale dans $A$ est supérieure ou égale à 2.
    Comptons le nombre de paires $\{c,d\}$ où $c$ est dans $A$, $d$ n'est pas dans $A$, et la distance de $c$ à $d$ est 1.
    Pour chaque $c$ dans $A$, aucun de ses $8\times 35$ voisins à distance 1 n'est dans $A$. Il y a donc $N\times 8\times 35$ telles paires.
    Pour chaque $d$ qui n'est pas dans $A$, et pour chaque place de $d$, il y a au plus un élément de $A$ qui diffère de $d$ seulement en cette place. Le nombre de paires est donc majoré par $(36^8-N)\times 8$.
    On en déduit $N\leq 36^7$. Le système du bit de parité réalise donc bien le maximum.
    C'est d'ailleurs valable quel que soit la longueur des chaînes, et quel que soit le nombre de caractères dans l'alphabet.
  • Merci à tous pour vos super réponses malgré mes petites grosses difficultés à formuler ma problématique.

    Je vais essayer de comprendre comment est calculé le caractère de contrôle et pourquoi il sera forcément différent.
    Je comprends qu'il existe un unique caractère répondant aux règles de calcul avec les 7 premiers caractères en inputs, mais je veux comprendre pourquoi !
  • Lourran a écrit une formule explicite (qui ne correspond pas tout à fait à ce que je décrivais, mais ça n'a pas d'importance). Tu ne la comprends pas ?
  • Je comprends la formule, mais les implications d'unicité ne me semblent pas évidentes au premier abord ; je vais devoir regarder en détail.
  • Dans ma première réponse, je parlais des codes barres ( le gencod, qu'on trouve sur chaque produit).
    On est exactement dans la même logique, et l'unicité est évidente.

    Le gencod, c'est un code sur 13 chiffres. En fait 12 chiffres plus un caractère de contrôle.
    Quand on a choisi les 12 premiers chiffres, on fait une certaine opération. Pour simplifier, je vais dire qu'on additionne ces 12 chiffres (ce n'est pas tout à fait ça, mais peu importe) ça nous donne un résultat.
    Par exemple, si les 12 premiers chiffres sont 302010111111, la somme donne 12.
    Dans le cas du gencod, on part de ce nombre, et on prend le complément à la dizaine supérieure. ici, 20-12, ça donne 8. Et donc le 13 ème chiffre sera 8, obligatoirement.

    L'unicité est garantie (on additionne nos 12 chiffres, si on obtient 12 ou 22 ou 32 ou 42 ou ... , alors on ajoute un 8 ; si on obtient 13 ou 23 ou 3 ou 43 ..., on ajoute un 7, etc etc )
    Dans ton cas, c'est exactement pareil.

    Attention quand même. Je dis qu'à partir des 12 premiers chiffres , on les additionne... puis on cherche le complément à la dizaine supérieure... ok, cette méthode marche.

    Dans la vraie méthode du gencod, on prend certains chiffres, on les additionne. On multiplie ce résultat par 3. Puis on additionne tous les autres chiffres.
    Dans le cas du gencod, ça marche. Ca assure que 2 gencods différents ont bien au moins 2 chiffres différents.
    Dans ton cas, ça ne marcherait pas !
    Je te dirais bien de deviner pourquoi ... mais je pense que tu vas galérer... oublie le challenge. C'est sans importance.

    Par contre, dans ton cas, considérer que chacun des 7 premiers caractères est un nombre entre 0 et 35, additionner ces 7 nombres, et garder ce resultat (modulo 35), ça marche.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!