Dénombrement

détermination du nombre d'éléments d'un ensemble

En mathématiques, le dénombrement est la détermination du nombre d'éléments d'un ensemble. Il s'obtient en général par un comptage ou par un calcul de son cardinal à l'aide de techniques combinatoires.

Perception immédiate

modifier

Face à une collection d'au plus quatre objets, l'être humain, avant même l'acquisition du langage, et certains animaux[1] semblent avoir une notion immédiate de la quantité présentée sans énumération. Ce phénomène est appelé subitisation[2].

Il peut être étendu au-delà de quatre dans certaines configurations, comme les points sur les faces d'un [réf. nécessaire]. Les nombres figurés peuvent être ainsi plus facilement repérables.

Symbolisation par une même quantité

modifier

Les premières évaluations de quantités n'ont pas nécessairement été exprimées à l'aide d'un nombre ou d'une notation chiffrée. Or, de telles évaluations ont pu être utiles pour suivre l'évolution d'un troupeau, d'une production manufacturée, des récoltes ou d'une population humaine, notamment dans les corps d'armée. En l'absence de système de numération, il est possible de représenter chaque élément d'une collection, par exemple, à l'aide d'une encoche sur un morceau de bois ou un os. Un autre exemple est visible dans le film Ivan le Terrible de Sergueï Eisenstein, où avant un combat, les soldats jettent chacun à leur tour une pièce dans un sac.

Comptage

modifier

L'évaluation d'une quantité d'objets à l'aide d'un terme particulier nécessite l'établissement d'une liste de termes qui puisse être apprise et transmise. Certains peuples océaniens parcourent ainsi une vingtaine de parties du corps selon un ordre fixe (mais dépendant de la localisation du peuple)[3]. Chaque langue a développé un système de désignation des premiers nombres entiers, éventuellement lié à un système de numération particulier.

Le dénombrement consiste alors à parcourir simultanément la chaine numérique et la collection d'objets de façon que chaque objet ne soit considéré qu'une seule fois. La compréhension de cette technique de dénombrement est décomposée en cinq principes[4] :

  • principe d'adéquation unique : chaque mot n'est associé qu'à un et un seul élément de la collection ;
  • principe d'ordre stable : les mots-nombres sont toujours récités dans le même ordre ;
  • principe du cardinal : pour désigner la taille d'une collection, il suffit d'énoncer le dernier mot-nombre utilisé ;
  • principe d'abstraction : les objets peuvent être de natures différentes ;
  • principe de non pertinence de l'ordre : les objets peuvent être parcourus dans n'importe quel ordre.

Pour des grandes quantités ou pour des ensembles abstraits et en particulier pour des ensembles mathématiques, le dénombrement se fait à l'aide d'opérations arithmétiques ou de considérations combinatoires..

Propriétés fondamentales

modifier
  • Principe des tiroirs : si l'on dispose de m ensemble(s) et que l'on y range n objet(s) avec n > m, alors au moins un de ces ensembles contiendra plusieurs objets.
    Exemple : dans une classe de 20 élèves, si tous sont nés la même année, alors plusieurs d'entre eux sont forcément nés le même mois.
  • Cardinal d'un produit cartésien : si un arbre comporte n branche(s) et que celle(s)-ci comporte(nt) chacune p sous-branche(s), alors cet arbre comporte n × p sous-branche(s).
    Exemple en probabilités élémentaires : supposons qu'on tire une carte au hasard dans un jeu de 52 cartes. Si l'on tente d'en deviner la couleur (trèfle, carreau, cœur ou pique), on a 1 chance sur 4 de tomber juste. Par ailleurs, si l'on tente d'en deviner la valeur (as, roi, dame, valet, etc.), on a 1 chance sur 13 de tomber juste. Enfin, si l'on tente d'en deviner la couleur et la valeur, on a une chance sur 52 (4 × 13) de tomber juste.

Dénombrement dans des ensembles finis

modifier

Théorèmes fondamentaux

modifier

Dans cette section, si A est un ensemble fini, on note   (lire « cardinal de A ») le nombre de ses éléments. Par exemple,  .

Théorème 1 — Soit   une partie d'un ensemble fini  .
Alors A est elle-même finie et   .
Si en outre  , alors  .

Caractérisation des applications injectives — Soit   un ensemble fini,   un ensemble et   une application de   dans  .
On a :

  1.   
  2.   est injective    

Corollaire — Soit   une application injective d'un ensemble   dans un ensemble  .
si   est fini, alors   est fini et  .

Ce corollaire n'est en fait que l'application de la caractérisation des applications injectives dans le cas particulier où l'ensemble d'arrivée de   est  .

Théorème — Soit E et F deux ensembles finis tels que  . Si   est une application de   dans   on a :
  est injective     est surjective     est bijective.

Propriétés

modifier

Cardinal de l'union de deux ensembles finis disjoints —  Soient   et   deux ensembles finis disjoints avec   et  .
Alors on a  .

Par récurrence, on généralise cette propriété à une famille d'ensembles finis disjoints deux à deux :

Cardinal de l'union de   ensembles finis deux à deux disjoints —  Soit   une famille de   ensembles finis deux à deux disjoints.
Alors on a  .

Cardinal du complémentaire —  Soit   un ensemble fini,  , et   son complémentaire dans  .
Alors on a  .

Cardinal de l'union de deux ensembles finis —  Soient   et   deux ensembles finis.
Alors on a  .

Cardinal de la réunion disjointe de deux ensembles finis — Soient   et   deux ensembles finis de cardinaux respectifs   et  .
Alors   est finie de cardinal  .

Ce résultat peut se généraliser à plus de deux ensembles.

Cardinal de la réunion disjointe de   ensembles finis — Soit   une famille d'ensembles finis.
 

Cardinal du produit cartésien de deux ensembles finis — Soient   et   deux ensembles finis de cardinaux respectif   et  .
Alors   est fini de cardinal  .

Plus généralement, pour une suite d'ensembles finis :

Cardinal du produit cartésien d'une suite d'ensembles finis — Soit   une famille d'ensembles finis.
Alors  

Cardinal de l'ensemble des parties d'un ensemble fini — Soit   un ensemble fini de cardinal  .
Comme   est en correspondance biunivoque avec l'ensemble des applications de   dans  , alors   est un ensemble fini et on a  .

Cardinal de l'ensemble des correspondances de   dans   — Soient   et   deux ensembles finis.
L'ensemble des correspondances de   dans  , noté habituellement  , s'identifie à   donc est fini de cardinal  .

Cardinal de l'ensemble des applications de   dans   — Soient   et   deux ensembles finis de cardinaux respectifs   et  .
L'ensemble des applications de   dans  , souvent noté  , est fini de cardinal   avec la convention 00=1 si   et   sont tous deux vides.

Cette propriété justifie la notation plus courante  .

Cardinal de l'ensemble des surjections de   dans   — Soient   et   deux ensembles finis de cardinaux respectifs   et  .
L'ensemble des surjections de   dans  , noté habituellement  , a pour cardinal la somme suivante:
 .
Cette somme est nulle si  .

Les applications injectives, qui jouent un rôle important en combinatoire, sont traitées de manière plus approfondie dans les paragraphes suivants.

Notes et références

modifier
  1. Certaines observations sont relatées dans le premier chapitre de l'Histoire universelle des chiffres de Georges Ifrah, page 22, Éditions Robert Laffont, Paris 1981.
  2. (en) Usha Goswami, Cognitive development: The learning brain, New York, Psychology Press, .
  3. Georges Ifrah, Histoire universelle des chiffres, page 46, Éditions Robert Laffont, Paris 1981.
  4. D'après les travaux de R. Gellman et C. R. Gallistel, cités dans l'article de Roger Bastien « L'acquisition du nombre chez l'enfant ».

Voir aussi

modifier

Sur les autres projets Wikimedia :