COMBINATOIRE ANALYSE

Carte mentale

Élargissez votre recherche dans Universalis

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


L'analyse combinatoire est l'ensemble des techniques qui servent, en mathématiques, à compter (ou dénombrer) certaines structures finies, ou à les énumérer (établir des listes exhaustives de structures considérées), enfin à démontrer leur existence pour certaines valeurs des paramètres dont elles dépendent. Ces structures sont très variées ; leur seul trait commun c'est d'être finies. En revanche, les problèmes qu'on se pose sur ces structures sont très divers, et les techniques mathématiques qu'on utilise pour résoudre ces problèmes, très différentes. Par exemple, si on veut dénombrer les arbres de n sommets, on établit une correspondance biunivoque entre l'ensemble de ces arbres et l'ensemble de certaines suites qu'on sait compter. Mais, si l'on veut démontrer l'existence d'une famille infinie de codes correcteurs, on utilise des résultats fins sur les anneaux de polynômes à coefficients dans un corps fini. Pourtant, dans les deux cas, on dit qu'on s'occupe d'analyse combinatoire. Dans le foisonnement des sujets dits de nature combinatoire, on a donc dû faire un choix et laisser de côté des objets importants.

Dénombrements élémentaires

Dans les opérations élementaires de dénombrement, on utilise un langage très proche du réel. On parle de choisir un objet de m façons différentes, on dit qu'il n'y a qu'un nombre n de possibilités... Considérons ainsi l'exemple suivant. Une urne contient 10 boules numérotées de 1 à 10 ; on tire successivement deux boules de l'urne sans remettre la première après tirage. Combien y a-t-il de tirages croissants, c'est-à-dire de façons de tirer deux boules dont les numéros vont en croissant ? Pour déterminer ce nombre, on raisonne de la façon suivante. Si la première boule a été tirée et que son numéro est i (1 ≤ i ≤ 10), pour obtenir un tirage croissant, on peut choisir le numéro j de la seconde de 10 − i façons différentes. Enfin, pour obtenir un tirage croissant, on peut choisir soit un tirage commençant par le numéro 1, soit un tirage commençant par 2, [...]

1 2 3 4 5

pour nos abonnés,
l’article se compose de 9 pages




Écrit par :

Classification


Autres références

«  COMBINATOIRE ANALYSE  » est également traité dans :

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithmique/#i_26304

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☛ http://www.universalis.fr/encyclopedie/paul-erdos/#i_26304

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☛ http://www.universalis.fr/encyclopedie/pierre-de-fermat/#i_26304

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

  • Écrit par 
  • Georges C. ANAWATI, 
  • Roshdi RASHED
  • , Universalis
  •  • 22 470 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☛ http://www.universalis.fr/encyclopedie/islam-la-civilisation-islamique-les-mathematiques-et-les-autres-sciences/#i_26304

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 ludi […] Lire la suite☛ http://www.universalis.fr/encyclopedie/litterature-numerique/#i_26304

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☛ http://www.universalis.fr/encyclopedie/percy-alexander-macmahon/#i_26304

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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/george-polya/#i_26304

PROBABILITÉS CALCUL DES

  • Écrit par 
  • Daniel DUGUÉ
  •  • 12 208 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 e […] Lire la suite☛ http://www.universalis.fr/encyclopedie/calcul-des-probabilites/#i_26304

SZEMERÉDI ENDRE (1940- )

  • Écrit par 
  • Bernard PIRE
  •  • 361 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☛ http://www.universalis.fr/encyclopedie/endre-szemeredi/#i_26304

Voir aussi

Pour citer l’article

Dominique FOATA, « COMBINATOIRE ANALYSE », Encyclopædia Universalis [en ligne], consulté le 09 septembre 2019. URL : http://www.universalis.fr/encyclopedie/analyse-combinatoire/