Les permutations de cloches

I. Introduction

Le “change ringing” c’est l’art de faire sonner un ensemble de cloches de différentes tailles et timbres de façon mélodieuses. Il a été inventé au 17 ème siècle en même temps que les hautes tours circulaires dans les églises.  

Les sonneurs de cloches se sont rendus compte que l’amplitude de rotation des cloches était plus grande avec une longue corde et qu’il était donc plus facile de contrôler le tempo des sons de cloches, ce qui permettait de faire des combinaisons de cloches plus complexes basées sur les permutations mathématiques appelées “change”. 

Cependant, les contraintes physiques des cloches font qu’elles doivent être éloignées les unes des autres et donc qu’il faut obligatoirement un sonneur par cloche. De plus seulement deux cloches peuvent changer d’ordre entre deux permutations  

Plusieurs algorithmes existent pour énumérer toutes les permutations en respectant cette contrainte.  

Pour cela nous allons expliquer en détail les algorithmes classiques : Plain Hunt et Plain Bob. Puis nous allons montrer que ces algorithmes sont corrects et enfin vous montrer quelques animations animations.

Plan:

I. Explication des différents algorithmes utilisés pour énumérer les permutations.

II.Preuve par récurrence que les algorithmes sont corrects.

III. Illustration des algorithmes par un programme.

I. Explication des différents algorithmes utilisés pour énumérer les permutations.

1. Plain hunt

Plain hunt est la façon la plus simple de permuter les cloches. Toutes les autres "changes" sont une variation de plain hunt

L'algorithme consiste à intervertir successivement les deux éléments successifs entre eux puis

  • de répéter la même opération sur les n-1 premières ou dernières cloches ( càd on "fixe" soit la première soit la dernière cloche ). Si n est impair
  • de repéter la même opération sur les n-2 cloches du centre (càd que l'on fixe la première ET la dernière cloche ) Si n est pair
L'algorithme de plain hunt sur 6 cloches. source : Wikipédia.com
Plain hunt minimus (4 cloches)
Source: tadhill.com

Le problème c'est que Plain hunt est assez limité en nombre de cloches maximal et on n'entend très peu de permutations avant de revenir à l'originelle (seulement 2n permutations en moyenne). Cependant en modifiant légèrement cet algorithme on peut avoir accès à beaucoup plus, voire à toutes les permutations. C'est le cas de plain bob

2. Plain bob

L'algorithme de plain bob est un peu plus complexe que celui de plain hunt, mais malgré tout il reste l'un des plus ancien et l'une des plus simples modifications de celui-ci

En effet plain bob commence comme plain hunt sauf qu'à la 2n-1 ème permutation on change tout :

  • Si n est pair on fixe les deux premières cloches et on échange deux à deux les autres
  • Sinon on fixe aussi la dernière cloche et on échange les n-3 cloches du centre deux à deux
Plain bob mineur (6 cloches) Pour plus de lisibilité la dernière ligne d'une colonne est répétée sur la première ligne de la suivante Source : Wikipedia.com
Plain bob mimimus (4 cloches)
Source: tadhill.com

II-Preuve par récurrence que les algorithmes utilisés sont correctes:

Pour démontrer que les algorithmes fonctionnent, nous prouvons que toutes les permutations sont obtenues une et une seule fois.

1- On trouve une relation de récurrence pour le nombre de permutation d'un ensemble à n éléments (les cloches pour notre cas).

Pn représente le nombre de permutation avec n étant le nombre d'éléments.

Cas de base : n = 1, avec un seul élément il ne peut qu'exister qu'une seule permutation. Donc P1 = 1.

Etape par hypothèse de récurrence :

Soit un ensemble avec n+1 éléments {a1,a2,..........,an+1}. Avec a1 nous avons |Pn| permutations possibles. De même que pour a2, a3,....,an+1. Donc Pn+1 = Pn+Pn+.......+Pn n+1 fois. D'une autre manière, Pn+1 = (n+1).Pn.

2- En utilisant la relation de récurrence précédente avec P1 = 1 et Pn+1 = (n+1).Pn, nous pouvons en déduire que :

Pn = n.Pn-1 = n.(n-1).Pn-2 = n(n-1).Pn-3 = ........ = n!

Pour résultat nous aurons:

P1 = 1, Pn+1 = (n+1).Pn et Pn = n! avec n >= 2.

III-Illustration des algorithmes par un programme.

Les Animations

1.Animation sur plain hunt avec le nombre de cloches :

Chaque cloche est représentée par un numéro parce que c'est plus lisible et on peut suivre les permutations plus facilement. Le nombre minimal des cloches est 3, et le nombre maximal est 12.
Pour faire le plain hunt, il suffit de rentrer un numéro entre 3 et 12 et de cliquer sur submit.


2.Animation sur plain bob avec le nombre de cloches: 

Chaque cloche est représentée par un numéro parce que c'est plus lisible et on peut suivre les permutations plus facilement. Le nombre minimal des cloches est 4, et le nombre maximal est 12.
Pour faire le plain bob, il suffit de rentrer un numéro entre 4 et 12 et de cliquer sur submit.

3. Animations sur plain hunt et plain bob avec des cloches:

Ici, on représente les permutations avec les cloches. Chaque cloche sonne dépendant de sa position. Si la position de la cloche est 1 (si on regarde les animations d'avant), la cloche va suivre les permutations de la cloche numéro 1 etc.
Pour faire fonctionner l'animation, il faut rentrer un numéro entre 3 et 12, puis de choisir la permutation souhaitée et de cliquer finalement sur le bouton "play".

Bibliographie :

https://en.wikipedia.org/wiki/Change_ringing

https://en.wikipedia.org/wiki/Plain_hunt

https://www.nagcr.org/pamphlet.html

https://images.math.cnrs.fr/Permutations-jonglistiques.html

0 Cliquer pour recommander cet article