Accueil / Combinatoire / Suites / Permutations et tomographie
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é.
Description
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 ai, 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.
Application
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.
Les X-rays seront calculés.
Nombres de classes
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,
À 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,
Autres pages ou documents du site
Tomographie page de liens
Hexagrilles
Permutations et dérangements
Suites de Skolem
Puzzle de Dudley Langford
Pavages rythmiques parfaits
Bijections de Nn sur N.
Hexagrilles
Permutations et dérangements
Suites de Skolem
Puzzle de Dudley Langford
Pavages rythmiques parfaits
Bijections de Nn sur N.
Documents - références - compléments - liens utiles
On the X-rays of permutations Cecilia Bebeacua, Toufik Mansour, Alexander Postnikov, Simone Severini - arXiv:math/0506334 - X-rays of permutation are interesting in the context of Discrete Tomography since many types of integral matrices can be written as linear combinations of permutation matrices.
Perfect Skolem sets Gustav Nordh - arXiv:math/0506155 - The problem of deciding which sets of the form A = {1,...,n} are Skolem sets was solved by Thoralf Skolem in the late 1950's. We study the natural generalization where A is allowed to be any set of n positive integers.
Integer sequence A019589 Number of nondecreasing sequences which are differences of two permutations of 1,2,...,n.
Perfect Skolem sets Gustav Nordh - arXiv:math/0506155 - The problem of deciding which sets of the form A = {1,...,n} are Skolem sets was solved by Thoralf Skolem in the late 1950's. We study the natural generalization where A is allowed to be any set of n positive integers.
Integer sequence A019589 Number of nondecreasing sequences which are differences of two permutations of 1,2,...,n.
Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
© (Copyright) Jean-Paul Davalan 2002-2014Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.