Le mot dans la première question doit-il être séparé par deux espaces quand il est au "milieu" et un espace quand il est sur les bords ou aucun si il fait K caractères ?

Et dans la deuxième quel est la taille du mot duquel on extrait les M lettres?

Ouais, calculer avec des lettres ! Merci ch'Ef !


1) On a une chance sur [latex]K^M[/latex] que le mot soit écrit sur les [latex]M[/latex] premiers caractères, puis (si [latex]N > M[/latex]) une autre chance sur [latex]K^M[/latex] que le mot soit écrit sur les caractères [latex]2[/latex] a [latex]M+1[/latex], puis etc.
Au final, ça nous donne a priori une proba de
[TeX](N-M+1) \times \frac1{K^M}[/TeX]
Sauf qu'il s'agit d'une proba a priori... Si le mot n'est pas écrit par les [latex]M[/latex] premiers caractères, je pense que cela donne une (maigre) indication sur ce que les lettres [latex]1[/latex] a [latex]M[/latex] ne sont pas, ou ne sont pas toutes en même temps.

Genre, si le mot est constitué de [latex]M[/latex] fois le même caractère, le fait qu'il ne soit pas écrit au début de la chaîne de [latex]N[/latex] caractères rend sa présence bien plus improbable sur les caractères [latex]2[/latex] a [latex]M+1[/latex], non ?

Ou alors je pense trop loin. Va pour [latex]\frac{N-M+1}{K^M}[/latex].


2) Est-ce que certains des caractères de M sont identiques ? Exemple avec M=N=3 et les dix chiffres comme caractères possibles : la chaîne de caractères 111 a une chance sur mille d'apparaître dans un ordre quelconque dans une chaîne de longueur 3, tandis que 123 a six chances sur mille (dans les chaînes 123, 132, 213, 231, 312, 321).

En gros, un caractère (que je vais noter [latex]m[/latex]) apparaissant [latex]\alpha[/latex] fois dans la chaîne que l'on veut trouver divise par [latex]\alpha ![/latex] la probabilité d'apparition dans le désordre.

Le "pire des cas" est donc celui où la chaîne a chercher est constituée de [latex]M[/latex] fois le même caractère, auquel cas la proba d'apparition dans la chaîne de longueur [latex]N[/latex] est :
[TeX]\frac{N !}{M! (N-M)!} \times \frac 1{K^M}[/TeX]
Le premier facteur est le nombre de façons de placer [latex]M[/latex] éléments parmi [latex]N[/latex] dans un ordre quelconque, soit [latex]C^N_M[/latex].

C'était le pire des cas ; dans le meilleur, tous les caractères sont différents, ce qui multiplie la proba par M! pour donner :
[TeX]\frac{N !}{(N-M)!} \times \frac 1{K^M}[/TeX]
On tombe, en lieu et place des combinaisons, sur des arrangements. Logique, non ?

Le cas général, maintenant : le mot a trouver est composé de [latex]m_i[/latex] fois le [latex]i[/latex]-ième caractère de l'alphabet, avec, bien sûr, [latex]\sum_{i=1}^K m_i = M[/latex]. Alors, la probabilité "optimale" (ci-dessus) est divisée par [latex]\prod_{i=1}^K (m_i !)[/latex], d'où la probabilité générale :
[TeX]\frac{N !}{K^M (N-M)! \prod_{i=1}^K (m_i !)}[/TeX]

@Nicouj, oui quand on tape N caractères on obtient un mot de N caractères.

Exemple K=26, N=6 et M=4 :
J'ai une machine a écrire de 26 caractères, les lettres de l'alphabet, je tapes 6 caractères ABCDEF, j'ai bien obtenu le mot ABCDEF, mais lui meme contient le mot de 4 lettres ABCD par exemple. La question 1 demande la probabilité d'avoir écrit ABCD (ou BCDE, ou CDEF).

Ok j'ai mieux compris

Donc en tapant N lettres, j'écris N-M+1 mots de M lettres (donc forcément au moins un mot de M lettres ce que je croyais être la question ^^)

Si l'alphabet de la machine compte K caractères, il y a K^M mots de M lettres.

1)Donc j'ai (N-M+1)/K^M chances de taper un mot particulier   ?

2)Chacune des N lettres tapées au hasard a 1 chance sur K d'être la première lettre de mon mot. Si une lettre est bonne, chacune des N-1 restantes a une chance sur K d'être la 2eme lettres ...

Soit N/K * (N-1)/K * (N-1)/K * ... * (N-M+1)/K = [latex]\frac{N!}{K^M * (N-M)!}[/latex]

Je vous donne mes propositions de réponses :

1- La première question tout le monde est d'accord, le nombre de mots qui fonctionnent :[latex]{N-M+1}[/latex] divisé par le nombre de mots possibles [latex]{K^M}[/latex] soit : [latex]\frac{N-M+1}{K^M}[/latex]

2- MthS nous gratifie d'une explication avec des caractères distincts et non distincts, je n'avais pas forcément réfléchi à ce cas, mais il s'agit simplement de calculer les arrangements possibles des lettres. [latex]\frac{A^M_N}{K^M} = \frac{N!}{(N-M)!K^M}[/latex]

Bonnes réponses de MthS-MlndN, Nicouj et une partie pour Milou_le_viking.

Très bonne remarque Dans la réponse que j'ai proposée certains cas doivent être comptabilisés plusieurs fois et donc ne fonctionne que lorsque N < 2M.

Quelqu'un est motivé pour distinguer les cas ?