COMBINATOIRE ANALYSE

Carte mentale

Élargissez votre recherche dans Universalis

Existence et construction de modèles

Un certain nombre de modèles ont été tout particulièrement étudiés, c'est le cas des carrés latins, sans doute parce qu'un mathématicien célèbre comme Euler fit à leur sujet une conjecture malheureuse et qu'il fallut attendre 177 ans pour prouver son inexactitude. En introduisant des notions comme celle d'orthogonalité, on a pu établir des liens étroits entre les carrés latins et certaines géométries finies, ou encore avec d'autres modèles comme les blocs incomplets équilibrés, ce qui a permis souvent d'étudier le même objet avec des optiques différentes.

Un carré latin d'ordre n est une matrice carrée A = (aij), 1ijn dont les coefficients aij sont 1, 2, ...n et dans laquelle chaque entier k apparaît une et une seule fois dans chaque ligne et chaque colonne (1 ≤ k  n). Il existe naturellement un carré latin d'ordre n pour tout ≥ 1. Par exemple, la table de multiplication d'un groupe fini d'ordre n est un carré latin. En fait, un carré latin peut être considéré comme la table de multiplication d'un système algébrique dont la loi est seulement supposée simplifiable. Soit ln le nombre de carrés latins d'ordre n ; jusqu'à ce jour, on a pu déterminer les valeurs exactes de ln pour 1 ≤ ≤ 8. Pour calculer l8, on a dû recourir à l'usage d'ordinateurs, mais même avec ceux-ci, en l'absence de nouvelles méthodes, on ne peut espérer aller bien loin dans cette direction. En revanche, l'orthogonalité a permis de trouver des résultats plus intéressants. Soit A = (aij) et B = (bij), deux carrés latins d'ordre n ; on dit qu'ils sont orthogonaux si tous les n2 couples (aijbij), où ij = 1, 2, ..., n, sont distincts. Par exemple, les deux carrés latins d'ordre 4 indiqués ci-dessous sont orthogonaux :

Soit C la matrice ayant pour coefficients les couples (aijbij) ; dans C tous les n2 couples (1, 1), (1, 2), ..., (nn) apparaissent une et une seule fois. Dans l'exemple ci-dessus, on obtient la matrice :

On dit parfois que C est un carré gréco-latin. On s'est alors posé le problème de savoir s'il existe une paire de carrés latins orthogonaux pour tout n. Avec un peu de patience, il est facile de construire de telles paires pour n = 3, 4 et 5 et même pour des entiers supérieurs à 6. C'est Euler qui en 1782 formula ce problème en termes récréatifs. Supposons, en effet, que, dans six régiments donnés, on relève, dans chacun, six officiers, tous de grades différents, et qu'on veuille disposer ces trente-six officiers dans un carré de six cases de côté, de sorte que dans chaque ligne et dans chaque colonne il y ait un représentant de chaque régiment et un représentant de chaque grade. Une telle disposition est-elle possible ? La réponse est non, et ce n'est qu'en 1900 que Tarry démontra cette impossibilité par une analyse très systématique de tous les cas possibles. Le problème des trente-six officiers était donc impossible. Si l'on numérote de 1 à 6 les six régiments et les six grades, chacun des officiers peut être repéré par un couple (ij), où 1 ≤ i, ≤ 6 ; le premier indice i désigne son régiment et le second j son grade. Vouloir un représentant de chaque régiment (resp. grade) dans chaque ligne et chaque colonne et vouloir quand même disposer les trente-six officiers, c'est chercher à satisfaire aux trois exigences :

– Les premiers indices i forment un carré latin ;

– Les seconds indices j forment un carré latin ;

– Les deux carrés latins ainsi formés sont orthogonaux.

L'impossibilité du problème des trente-six officiers démontrée par Tarry équivaut donc à l'impossibilité de construire deux carrés latins d'ordre 6 orthogonaux. Euler n'ayant pu réussir à construire de couples de carrés latins orthogonaux d'ordre n pour des entiers de la forme n = 4 k + 2, conjectura qu'il n'existait pas de couples de carrés latins orthogonaux d'ordre n pour tout n de la forme 4 k + 2. À l'exception du seul cas n = 6, sa conjecture s'est révélée complètement erronée et, en 1959, Bose, Shrikhande et Parker démontrèrent qu'il existe en effet un couple de carrés latins orthogonaux d'ordre n pour tout n différent de 2 et 6. Avant cette date, cependant, on savait construire un couple de carrés latins orthogonaux pour tout n non congru à 2 modulo 4. Une des méthodes qui s'est révélée des plus fécondes a été de considérer pour tout n ≥ 3, de la forme pr, où p est un nombre premier et > 0, le corps fini Fn ayant n éléments. Désignons par xo = 0, x1, ..., xn-1 les n éléments de Fn et formons les matrices A1, A2, ... [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 9 pages

Médias de l’article

Nombres de Stirling

Nombres de Stirling
Crédits : Encyclopædia Universalis France

tableau

Arbre de sept sommets

Arbre de sept sommets
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article


Écrit par :

Classification

Autres références

«  COMBINATOIRE ANALYSE  » est également traité dans :

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 833 mots
  •  • 3 médias

Dans le chapitre « Algorithmes combinatoires »  : […] Entrent dans la catégorie des problèmes combinatoires , en informatique, les problèmes qui consistent à déterminer, pour une donnée  d , si est satisfaite une condition : où : ( a ) S( d ) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d  ; ( b ) Q est une condition facilement vérifiable algorithmiquement (c'est-à-dire en un temps polynomial […] Lire la suite

ERDÖS PAUL (1913-1996)

  • Écrit par 
  • Jean-Louis NICOLAS
  •  • 966 mots

Mathématicien brillant et hors du commun, lauréat du prix Wolf en 1983. Né le 26 mars 1913 à Budapest et décédé le 20 septembre 1996 à Varsovie, Paul Erdös fut un enfant prodige et, à l'âge de quatre ans, il savait déjà compter avec des nombres de trois chiffres et avait redécouvert les nombres négatifs. Il fut élevé par ses parents, professeurs de mathématiques, comme un fils unique, ses deux sœu […] Lire la suite

FERMAT PIERRE DE (1601-1665)

  • Écrit par 
  • Catherine GOLDSTEIN, 
  • Jean ITARD
  • , Universalis
  •  • 4 157 mots

Dans le chapitre « Théories des nombres »  : […] Comme algébriste, Fermat garde toute son originalité, en particulier dans sa méthode d'élimination des radicaux dans une équation et dans son mémoire de 1661 sur les équations de la division des arcs de cercle en parties égales. Il fait apparaître dans ce mémoire, pour la première fois, une analogie entre fonctions circulaires et fonctions exponentielles. Mais le domaine où il triomphe est celui d […] Lire la suite

ISLAM (La civilisation islamique) - Les mathématiques et les autres sciences

  • Écrit par 
  • Georges C. ANAWATI, 
  • Roshdi RASHED
  • , Universalis
  •  • 22 471 mots
  •  • 1 média

Dans le chapitre « L'analyse combinatoire »  : […] L'activité combinatoire a commencé par se manifester comme telle, mais d'une manière dispersée, chez les linguistes, d'une part, et chez les algébristes, d'autre part. Ce n'est que plus tard que se fera la liaison entre les deux courants, et que l'analyse combinatoire se présentera comme un instrument mathématique applicable aux situations les plus diverses : linguistiques, philosophiques, mathém […] Lire la suite

LITTÉRATURE NUMÉRIQUE

  • Écrit par 
  • Jean CLÉMENT, 
  • Alexandra SAEMMER
  •  • 4 340 mots

Dans le chapitre « Une littérature générée »  : […] Les premiers essais de littérature numérique sont aussi anciens que l’informatique elle-même. Dès les années 1940, Alan Turing, logicien et pionnier de l’informatique, découvre les potentialités de l’ordinateur dans le domaine de la combinatoire en programmant des Lettres d ’ amour sous forme de « cadavres exquis », ce montage ludique de phrases ou de dessins inventé par les surréalistes. Mais c’ […] Lire la suite

MACMAHON PERCY ALEXANDER (1854-1929)

  • Écrit par 
  • Bernard PIRE
  •  • 217 mots

Mathématicien britannique, spécialiste de l'analyse combinatoire. Né le 26 septembre 1854 à Malte, Percy MacMahon était le fils d'un brigadier général qui le destinait à une carrière dans l'armée. Après des études à l'école militaire de Woolwich, il sert comme officier à Malte et en Inde pendant cinq ans, puis revient en Angleterre où il enseigne la physique et les mathématiques dans diverses inst […] Lire la suite

PÓLYA GEORGE (1887-1985)

  • Écrit par 
  • Jean-Pierre KAHANE
  •  • 1 908 mots

George Pólya est une des grandes figures mathématiques du xx e  siècle : par l'étendue et la variété de son œuvre, par sa personnalité, par sa popularité. Héritier de la tradition hongroise, homme d'esprit et de culture, passionné par la science et par l'enseignement, il fut l'un des grands savants européens que la guerre amena aux États-Unis. Au cours de sa longue vie active — il donna encore un […] Lire la suite

PROBABILITÉS CALCUL DES

  • Écrit par 
  • Daniel DUGUÉ
  •  • 12 212 mots
  •  • 6 médias

Dans le chapitre « Problèmes de scrutin »  : […] On donne le nom de problème de scrutin à un ensemble de questions qui relient le calcul des probabilités à l'analyse combinatoire (cf.  analyse combinatoire ). Le plus simple de ces problèmes est le suivant : Une urne contient 2 n bulletins, n au nom de A et n au nom de B. On dépouille le scrutin (bien entendu, à chaque opération les bulletins restants ont une probabilité égale d'être extraits) […] Lire la suite

SZEMERÉDI ENDRE (1940- )

  • Écrit par 
  • Bernard PIRE
  •  • 362 mots
  •  • 1 média

Endre Szemerédi est un mathématicien hongrois né le 21 août 1940 à Budapest. Il est connu pour ses recherches en analyse combinatoire. Endre Szemerédi fréquente la faculté de médecine pendant un an, puis travaille dans une usine avant de commencer tardivement des études supérieures de mathématiques à l'université Eötvös Loránd à Budapest, où il obtient un master de sciences en 1965. Son talent mat […] Lire la suite

Voir aussi

Pour citer l’article

Dominique FOATA, « COMBINATOIRE ANALYSE », Encyclopædia Universalis [en ligne], consulté le 26 juin 2022. URL : https://www.universalis.fr/encyclopedie/analyse-combinatoire/