Permutations et tomographie - X-rays

Avertissement : cette page présente des résultats récents sur les matrices de permutations, en particulier des permutations obtenues à partir de certaines suites parfaites de Skolem (pavages rythmiques parfaits). La reconstruction des matrices à partir des projections sur les bords ou sur les diagonales n'est pour l'instant pas traité.

Une permutation s de l'ensemble fini E = [1, n] est une bijection de E sur E. Le nombre des permutations de E est n! = n×(n-1)×(n-2)×...×3×2×1.
La permutation s est parfois notée [s(1), s(2),...,s(n-1), s(n)].
La matrice binaire A associée à la permutation s est une matrice carrée n×n dont les éléments a_{i, j} valent 1 ou 0 selon que s(i)=j ou non. Tous les éléments des lignes et des colonnes sont donc nuls à l'exception d'un et d'un seul.

On observe quatre directions principales : horizontale (les lignes de la matrice), verticale (les colonnes de la matrice), diagonale Nord-Ouest/Sud-Est (direction de la diagonale principale) et Nord-Est/Sud-Ouest (antidiagonale, perpendiculaire à la direction précédente). La matrice carrée a n lignes, n colonnes, 2×n-1 diagonales et 2×n-1 antidiagonales.

Dans le cas d'une matrice de permutation, les sommes des termes d'une même ligne ou d'une même colonne sont toutes égales à 1.
Ce n'est plus le cas lorsqu'on effectue les sommes selon les diagonales ou les antidiagonales.
Dans tous les cas, la somme de toutes les lignes ou des colonnes, des diagonales ou encore des antidiagonales est la somme de tous les éléments de la matrice (ici c'est n).

L'un des premiers exemples de tomographie discrère a été le problème de la reconstitution d'une matrice binaire à partir de la connaissance des sommes de ses éléments suivant plusieurs directions distinctes.

Vous pouvez construire au hasard des permutations quelconques de [1, n] ou des permutations dont les longueurs des cycles sont données.
Les X-rays seront calculés.

permutations

Nombre d'éléments n =	OU   longueurs des cycles :
Skolem (parfait) n=m×k, ordre m =   k =

La suite A019589 de l'encyclopédie des suites entières donne pour tout ordre n, le nombre de classes de permutations pour la relation d'équivalence décrite ci-après.
À chaque permutation on soustrait l'identité et on range la différence dans l'ordre croissant. Deux permutations donnant cette même différence sont en relation et appartiennent à la même classe.
Par exemple s = (3, 5, 4, 1, 2), on soustrait l'identité (3, 5, 4, 1, 2) - (1, 2, 3, 4, 5) = (2, 3, 1, -3, -3) que l'on ordonne (-3, -3, 1, 2, 3). La permutation s2 = (4, 3, 5, 1, 2) appartient à la même classe.
Les nombres de classes pour n=1, 2, ... sont :

A019589 1, 2, 5, 16, 59, 246, 1105, 5270, 26231, 135036, 713898, 3857113, ...

Les classes de plus grands effectifs sont

{ 0 } ; { -1 1 } { 0 0 } ; { -1 0 1 } ; { -1 0 0 1 } ; { -2 -1 0 1 2 } ; { -2 -1 0 0 1 2 } ; { -3 -2 -1 0 1 2 3 } ; { -3 -2 -1 0 0 1 2 3 } ; { -4 -3 -2 -1 0 1 2 3 4 } ; ...

Les effectifs les plus grands sont alors donnés par la suite :

1, 1, 2, 3, 6, 12, 28, 76, 244, 784, 2544, 9664, 35600,