Dénombrement des lettres qui se touchent

Énigme des bouquins		haut
Énigme Sur l'étagère d'une bibliothèque, se trouvent sept livres: 5 sont d'Alexandre Dumas (D); 1 est écrit par Victor Hugo (H); et 1 fut publié par Voltaire (V). Parmi toutes les permutations de ces livres, on cherche les cas où un livre de Dumas n'est pas voisin du livre d'Hugo.	Traduction en permutations de lettres Ensemble: [D, D, D, D, D, H, V] Combien de permutations sans que D et H soient voisins ? Exemple: [D, D, D, D, D, V, H]
Solution On peut se lancer dans un calcul de dénombrement, ce que l'on va faire, mais, en l'occurrence, la solution est relativement simple. Un petit raisonnement conduit à deux solutions uniquement: les deux cas où la lettre H est aux extrémités de la suite des lettres.	Exigence: D et H ne se "touchent" pas. Alors, H doit être isolé d'un D par un V. Le V doit être externe à la suite des D, sinon le H serait toujours voisin d'un D: Avec, par exemple, [D, D, D, V, D, D], impossible de placer le H non mitoyen avec un D. Le V est soit d'un côté ou de l'autre de la suite des D, d'où les deux seules solutions. [H, V, D, D, D, D, D] et [D, D, D, D, D, V, H]

Cas général

Quelle est la solution dans le cas de k livres dont un est répété h fois ?

Ayant une bonne connaissance en dénombrement, on arrive rapidement à une formulation.

Mais les problèmes de dénombrement recèlent souvent des pièges. Une analyse détaillée n'est pas inutile.

Formulation rapide

haut

Analyse initiale

Nous devons dénombrer les trois cas suivants:
HD, DH sans oublier DHD.

Permutations totales (P_T)

Jeux de lettres: [D, D, D… H, V …]

Total k lettres dont une est répétée h fois

Permutations avec répétitions: P_T = k! / h!

Cas du bloc DH ou HD

En comptabilisant tous les cas en DH, viennent avec eux les cas en DHD, lesquels seront également présents lors du comptage des HD.

Ces cas sont donc comptés en double.

Considéré comme un tout ce bloc est permutable parmi les autres lettres:

Le bloc occupe une des k – 1 positions possibles dans la suite des lettres.

Doublé du fait des blocs DH ou HD

Les autres lettres permutent parmi les k – 2 positions restantes, sans oublier les permutations équivalentes sur les (h – 1) lettres D qui restent.

Bilan:

Cas du bloc DHD

Il est nécessaire de compter les cas DHD de manière à les défalquer du comptage précédent.

Considéré comme un tout ce bloc est permutable parmi les autres lettres:

Le bloc occupe une des k – 2 positions possibles dans la suite des lettres.

Il n'y a pas de permutation interne au bloc DHD.

Les autres lettres permutent parmi les k – 3 positions restantes, sans oublier les permutations équivalentes sur les (h – 2) lettres D qui restent.

Bilan:

Cas en contact

Cas sans contact

Cas où DHD est présent
=> h = 2 ou plus.

Cas où h = 1 >>>

Exemple avec le cas de notre énigme [D, D, D, D, D, H, V]

k = 7 et h = 5

On retrouve, la quantité 2, trouvée ci-dessus.




P_Contact = P_DH/HD – P_DHD	= 60 – 20 = 40
P_Sans = P_Total – P_Contact	= 42 – 40 = 2

Analyse détaillée

Une bonne pratique consiste à analyser plus intimement le comportement des cas possibles.

Le but est de découvrir le mécanisme de leur formation et ainsi s'assurer que la formulation est correcte.

Analyse DH – Lettres distinctes

haut

Observation

Avec trois lettres distinctes:

3! = 6 permutations;

4 avec D et H qui se touchent; et

2 sans contact.

Raisonnement

Avec DH, j'ai le choix du V devant ou derrière; avec HD idem = 2x2 cas.

P_S = 3! – 2x2 = 6 – 4 = 2

Toutes les permutations

D, H, V

D, V, H

H, D, V

H, V, D

V, D, H

V, H, D

En jaune, les deux seuls cas sans contact entre D et H.

Observation

Avec quatre lettres distinctes:

4! = 24 permutations;

12 avec D et H qui se touchent; et

12 sans contact.

Raisonnement

Avec DH:

Le bloc DH a une position parmi trois possibles;

Ensuite, V et Z ont deux possibilités;

Enfin, le bloc DH peut être inversé.

P_S = 4! – 3x2x2 = 24 – 12 = 12

Permutations

avec contact

[D, H, V, Z]

[D, H, Z, V]

[V, D, H, Z]

[Z, D, H, V]

[V, Z, D, H]

[Z, V, D, H]

[H, D, V, Z]

[H, D, Z, V]

[V, H, D, Z]

[Z, H, D, V]

[V, Z, H, D]

[Z, V, H, D]

Permutations

sans contact

[D, V, H, Z]

[D, V, Z, H]

[D, Z, H, V]

[D, Z, V, H]

[V, D, Z, H]

[Z, D, V, H]

[H, V, D, Z]

[H, Z, D, V]

[H, V, Z, D]

[H, Z, V, D]

[V, H, Z, D]

[Z, H, V, D]

Observation

Avec cinq lettres distinctes:

5! = 120 permutations

48 avec D et H qui se touchent

72 sans contact

Raisonnement

Avec DH:

Le bloc DH a une position parmi quatre possibles: (5 – 1).

Ensuite, [V, Z, A] ont 3! possibilités

Enfin, le bloc DH peut être inversé

P_S = 5! – (5–1) x 3! x 2 = 120 – 48 = 72

P_S = 5! – 4! x 2

Raisonnement rapide

Si le bloc DH est considéré comme un seul objet:

il y a (k – 1)! permutations.

Avec DH et HD, la quantité de permutations est multipliée par 2.

Bilan des cas de contacts:

P_S = k! – (k – 1)! x 2

Généralisation

Avec k lettres distinctes:

k! = 120 permutations

Position du bloc: (k – 1)

Autres lettres (k – 2)!

permutation du bloc: 2

P_S = k! – (k – 1)! x 2 = k! (k – 2) / k

P_S est la quantité de cas où H et D sont sans contact.

h = 1 (lettres distinctes)

k	Total	Contact	Sans
3	6	4	2
4	24	12	12
5	120	48	72
6	720	240	480
7	5 040	1 440	3 600
8	40 320	10 080	30 240

Analyse DH – Lettres doublées

haut

Observation

Avec quatre lettres dont une doublée:

4! / 2! = 12 permutations;

10 avec D et H qui se touchent; et

2 sans contact.

Raisonnement

Avec DH:

Le bloc DH a une position parmi trois possibles;

Ensuite, D (le deuxième) et Z ont deux possibilités; et

Enfin, le bloc DH peut être inversé.

Avec DHD:

Le bloc DHD a une position parmi deux possibles;

Le Z prend la place restante; et

Enfin, le bloc DHD est non permutable.

P_S= 4! / 2! – 3! x 2 – 2! x 1 = 12 – 12 + 2 = 2

[D, H, D, V]

[D, H, V, D]

[D, D, H, V]

[D, D, V, H]

[D, V, D, H]

[V, D, D, H]

[H, D, D, V]

[H, D, V, D]

[V, H, D, D]

[H, V, D, D]

[D, V, H, D]

[V, D, H, D]

Observation

Avec cinq lettres dont une répétée:

5! / 2! = 60 permutations;

42 avec D et H qui se touchent;

dont 6 doubles en DHD; et

18 sans contact.

Raisonnement

Avec DH:

Le bloc DH a une position parmi quatre possibles;

Les trois lettres qui restent: 3! ;

Permutation de DH: facteur 2 ;

Bilan: 4 x 3! x 2 = 4! x 2 = 48

Avec DHD:

Le bloc DHD prend une position parmi trois possibles;

Avec les deux lettres (V et Z), deux fois plus;

Bilan: 3 x 2 = 3! = 6

P_S = 5! / 2! – (4! x 2) + (3!) = 60 – 48 + 6 = 18

[D, D, V, H, Z]

[D, D, V, Z, H]

[D, D, Z, H, V]

[D, D, Z, V, H]

[D, V, D, Z, H]

[D, V, H, Z, D]

[D, Z, D, V, H]

[D, Z, H, V, D]

[H, V, D, D, Z]

[H, V, D, Z, D]

[H, V, Z, D, D]

[H, Z, D, D, V]

[H, Z, D, V, D]

[H, Z, V, D, D]

[V, D, D, Z, H]

[V, H, Z, D, D]

[Z, D, D, V, H]

[Z, H, V, D, D]

[D, H, D, V, Z]

[D, H, D, Z, V]

[D, H, V, D, Z]

[D, H, V, Z, D]

[D, H, Z, D, V]

[D, H, Z, V, D]

[D, D, H, V, Z]

[D, D, H, Z, V]

[V, D, H, D, Z]

[V, D, H, Z, D]

[Z, D, H, V, D]

[D, V, D, H, Z]

[D, Z, D, H, V]

[V, D, D, H, Z]

[V, Z, D, H, D]

[Z, D, D, H, V]

[D, V, Z, D, H]

[D, Z, V, D, H]

[V, D, Z, D, H]

[V, Z, D, D, H]

[Z, D, V, D, H]

[Z, V, D, D, H]

[H, D, D, V, Z]

[H, D, D, Z, V]

[H, D, V, D, Z]

[H, D, V, Z, D]

[H, D, Z, D, V]

[H, D, Z, V, D]

[V, H, D, D, Z]

[V, H, D, Z, D]

[Z, H, D, D, V]

[Z, H, D, V, D]

[V, Z, H, D, D]

[D, V, H, D, Z]

[D, Z, H, D, V]

[Z, D, H, D, V]

[Z, V, H, D, D]

[D, V, Z, H, D]

[D, Z, V, H, D]

[V, D, Z, H, D]

[Z, D, V, H, D]

[Z, V, D, H, D]

Bilan pour k lettres dont une doublée

h = 2 (une lettre doublée)

k	Total	Contact	Double	Sans
4	12	12	2	2
5	60	48	6	18
6	360	240	24	144
7	2 520	1 440	120	1200
8	20 160	10 080	720	10 800
9	181 440	80 640	5 040	105 840

Analyse DH – Lettres répétées

haut

Observation

Avec cinq lettres dont une répétée trois fois:

5! / 3! = 20 permutations;

18 avec D et H qui se touchent; et

2 sans contact.

Raisonnement

Avec DH:

Le bloc DH prend une position parmi quatre possibles;

Ensuite, (D, D et V) ont 3! / 2! possibilités ;

Enfin, le bloc DH peut être inversé;

Bilan: 4 x 3! / 2! x 2 = 4! / 2! x 2 = 24

Avec DHD:

Le bloc DHD a une position parmi trois possibles;

Ensuite, (D, V) multiplie les cas par 2;

Enfin, le bloc DHD est non permutable;

Bilan: 3 x 2! x 1 = 3!

P_S = 5! / 3! – 4! / 2! x 2 – 3! x 1 = 20 – 24 + 6 = 2

D, H, D, D, V

D, H, D, V, D

D, H, V, D, D

D, D, H, D, V

D, D, H, V, D

V, D, H, D, D

D, D, D, H, V

D, D, D, V, H

V, D, D, H, D

D, D, V, D, H

D, V, D, D, H

V, D, D, D, H

H, D, D, D, V

H, D, D, V, D

H, D, V, D, D

H, V, D, D, D

V, H, D, D, D

D, V, H, D, D

D, D, V, H, D

D, V, D, H, D

Bilan pour k lettres dont une répétée h fois

h = 3 (une lette triplée)

h	k	Total	Contact	Double	Sans
3	5	20	24	6	2
	6	120	120	24	24
	7	840	720	120	240
4	6	30	40	12	2
	7	210	240	60	30
	8	1 680	1 680	360	360
5	7	42	60	20	2
	8	336	420	120	36
	9	3 024	3 360	840	504

Bilan

Avec k lettres dont une est répétées h fois, la quantité de permutations où H et D ne se côtoient pas se calcule avec ces formules.

P_Sans = k! – 2(k – 1)! pour h = 1 (sans répétition)

La principale leçon: sans examen détaillé, il est possible de passer à côté des cas en DHD, lesquels ajoutent un troisième terme dans la formule.

Toutes ces valeurs ont été vérifiées par programme.

Haut de page

Retour

Abracadabra et Mississippi

Suite

Choix de cartes Pokémon ou des parfums de glace

Dénombrement – Index

Cette page

http://villemin.gerard.free.fr/Denombre/aaaCAS/Bouquin.htm