Movatterモバイル変換

[0]ホーム

Aller au contenu

Dénombrement

Ajouter des liens

Un article de Wikipédia, l'encyclopédie libre.

Ne pas confondre avec la notion dedénombrement comme recensement de la population en France sous l'Ancien Régime.

Enmathématiques, ledénombrement est la détermination dunombre d'éléments d'unensemble. Il s'obtient en général par un comptage ou par un calcul de soncardinal à l'aide de techniquescombinatoires.

Perception immédiate

[modifier |modifier le code]

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'undé^{[réf. nécessaire]}. Lesnombres figurés peuvent être ainsi plus facilement repérables.

Symbolisation par une même quantité

[modifier |modifier le code]

Les premières évaluations de quantités n'ont pas nécessairement été exprimées à l'aide d'un nombre ou d'une notationchiffrée. Or, de telles évaluations ont pu être utiles pour suivre l'évolution d'untroupeau, 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 filmIvan le Terrible deSergueï Eisenstein, où avant un combat, les soldats jettent chacun à leur tour une pièce dans un sac.

Comptage

[modifier |modifier le code]

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 peuplesocé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é à unsystème de numération particulier.

Le dénombrement consiste alors à parcourir simultanément lachaine 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.

Calcul

[modifier |modifier le code]

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

Propriétés fondamentales

[modifier |modifier le code]

Principe des tiroirs : si l'on dispose dem ensemble(s) et que l'on y rangen objet(s) avecn > 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'unproduit cartésien : si un arbre comporten branche(s) et que celle(s)-ci comporte(nt) chacunep sous-branche(s), alors cet arbre comporten × p sous-branche(s).
Exemple enprobabilités élémentaires : supposons qu'on tire une carte au hasard dans unjeu de 52 cartes. Si l'on tente d'en deviner l'enseigne (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, 10, etc.), on a 1 chance sur 13 de tomber juste. Enfin, si l'on tente d'en deviner l'enseigne et la valeur, on a une chance sur 52 (4 × 13) de tomber juste.

Dénombrement dans des ensembles finis

[modifier |modifier le code]

Théorèmes fondamentaux

[modifier |modifier le code]

Dans cette section, siA est unensemble fini, on note $\mathrm {card} (A)$ (« cardinal deA ») le nombre de ses éléments. Par exemple, $\mathrm {card} (\{e,f,g\})=3$ .

Théorème 1 — Soit $A {\displaystyle A}$ une partie d'un ensemble fini $E {\displaystyle E}$ .
Alors A est elle-même finie et $\mathrm {card} (A)$ ≤ $\mathrm {card} (E)$ .
Si en outre $\mathrm {card} (A)=\mathrm {card} (E)$ , alors $A=E$ .

Caractérisation des applications injectives — Soit $E {\displaystyle E}$ un ensemble fini, $F {\displaystyle F}$ un ensemble et $f {\displaystyle f}$ une application de $E {\displaystyle E}$ dans $F {\displaystyle F}$ .
On a :

$\mathrm {card} (f(E))$ ≤ $\mathrm {card} (E)$
$f {\displaystyle f}$ est injective $\Leftrightarrow$ $\mathrm {card} (f(E))=\mathrm {card} (E)$

Démonstration

Pour démontrer le point 1, on peut s'intéresser à l'ensemble des éléments de $E {\displaystyle E}$ qui ont une image par $f {\displaystyle f}$ . Si on le note $A {\displaystyle A}$ , alors l'application induite par $f {\displaystyle f}$ de $A {\displaystyle A}$ dans $f(E)$ est une bijection. Comme $A {\displaystyle A}$ est un sous-ensemble de $E {\displaystyle E}$ , il est fini et $\mathrm {card} (f(E))=\mathrm {card} (A)$ ≤ $\mathrm {card} (E)$ .
Le point 2 vient du fait que lorsque $f {\displaystyle f}$ est injective, tous les éléments de $f(E)$ ont un antécédent unique, donc l'application induite de $E {\displaystyle E}$ dans $f(E)$ est une bijection. Donc $\mathrm {card} (f(E))=\mathrm {card} (E)$ . Réciproquement si $\mathrm {card} (f(E))=\mathrm {card} (E)$ , alors $\mathrm {card} (A)=\mathrm {card} (E)$ puis il vient que $A=E$ .

Corollaire — Soit $f {\displaystyle f}$ une application injective d'un ensemble $E {\displaystyle E}$ dans un ensemble $F {\displaystyle F}$ .
si $f(E)$ est fini, alors $E {\displaystyle E}$ est fini et $\mathrm {card} (E)=\mathrm {card} (f(E))$ .

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 $f {\displaystyle f}$ est $f(E)$ .

Théorème — Soit E et F deux ensembles finis tels que $\mathrm {card} (E)=\mathrm {card} (F)$ . Si $f {\displaystyle f}$ est une application de $E {\displaystyle E}$ dans $F {\displaystyle F}$ on a :
$f {\displaystyle f}$ est injective $\Leftrightarrow$ $f {\displaystyle f}$ est surjective $\Leftrightarrow$ $f {\displaystyle f}$ est bijective.

Propriétés

[modifier |modifier le code]

Cardinal de l'union de deux ensembles finis disjoints — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis disjoints avec $\mathrm {card} (E)=k$ et $\mathrm {card} (F)=n$ .
Alors on a $\mathrm {card} (E\cup F)=\mathrm {card} (E)+\mathrm {card} (F)=n+k$ .

Démonstration

En effet soient $f {\displaystyle f}$ une bijection de $E {\displaystyle E}$ dans $[\![1,k]\!]$ et $g {\displaystyle g}$ une bijection de $F {\displaystyle F}$ dans $[\![1+k,n+k]\!]$ , alors on peut construire $h {\displaystyle h}$ l'application de $E\cup F$ dans $[\![1,n+k]\!]$ dont la restriction à $E {\displaystyle E}$ est $f {\displaystyle f}$ et celle à $F {\displaystyle F}$ est $g {\displaystyle g}$ . Comme $h {\displaystyle h}$ est une bijection, c'est une injection et le corollaire de caractérisation conclut que $\mathrm {card} (h(E\cup F))=\mathrm {card} ([\![1,n+k]\!])=n+k$ .

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

Cardinal de l'union de $n {\displaystyle n}$ ensembles finis deux à deux disjoints — Soit $(E_{i})_{i=1}^{n}$ une famille de $n {\displaystyle n}$ ensembles finis deux à deux disjoints.
Alors on a $\mathrm {card} (\bigcup _{i=1}^{n}E_{i})=\sum _{i=1}^{n}(\mathrm {card} (E_{i}))$ .

Cardinal du complémentaire — Soit $E {\displaystyle E}$ un ensemble fini, $A\subset E$ , et ${\overline {A}}$ son complémentaire dans $E {\displaystyle E}$ .
Alors on a $\mathrm {card} (A)+\mathrm {card({\overline {A}})} =\mathrm {card} (E)$ .

Démonstration

Démonstration : $A {\displaystyle A}$ et ${\overline {A}}$ sont deux ensembles finis d'intersection vide et $A\cup {\overline {A}}=E$ . La première propriété permet de conclure.

Cardinal de l'union de deux ensembles finis — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis.
Alors on a $\mathrm {card} (E\cup F)=\mathrm {card} (E)+\mathrm {card} (F)-\mathrm {card} (E\cap F)$ .

Démonstration

Démonstration : Comme $A\cap B$ et $A-B$ sont complémentaires dans $A {\displaystyle A}$ , la propriété précédente s'applique et on a $\mathrm {card} (A\cap B)$ + $\mathrm {card} (A-B)=\mathrm {card} (A)$ . Ce même raisonnement s'applique pour $B-A$ et $A\cap B$ . Remarquons enfin que $A-B$ , $A\cap B$ et $B-A$ forment une partition de $A\cup B$ . L'identité se déduit des trois résultats précédents.

Cardinal de laréunion disjointe de deux ensembles finis — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis de cardinaux respectifs $n {\displaystyle n}$ et $k {\displaystyle k}$ .
Alors $E\sqcup F$ est finie de cardinal $\mathrm {card} (E\sqcup F)=\mathrm {card} (E)+\mathrm {card} (F)=n+k$ .

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

Cardinal de la réunion disjointe de $n {\displaystyle n}$ ensembles finis — Soit $E_{i}$ une famille d'ensembles finis.
$\mathrm {card} (E_{1}\sqcup E_{2}\sqcup E_{3}\,\dots \,\sqcup E_{n})=\sum _{i=1}^{n}\mathrm {card} (E_{i}).$

Cardinal duproduit cartésien de deux ensembles finis — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis de cardinaux respectif $n {\displaystyle n}$ et $k {\displaystyle k}$ .
Alors $E\times F$ est fini de cardinal $\mathrm {card} (E\times F)=\mathrm {card} (E)\times \mathrm {card} (F)=nk$ .

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

Cardinal du produit cartésien d'une suite d'ensembles finis — Soit $E_{i}$ une famille d'ensembles finis.
Alors $\mathrm {card} (E_{1}\times E_{2}\times E_{3}\,\dots \,\times E_{n})=\prod _{i=1}^{n}\mathrm {card} (E_{i}).$

Cardinal de l'ensemble des parties d'un ensemble fini — Soit $E {\displaystyle E}$ un ensemble fini de cardinal $k {\displaystyle k}$ .
Comme ${\mathcal {P}}(E)$ est en correspondance biunivoque avec l'ensemble des applications de $E {\displaystyle E}$ dans $\left\{0,1\right\}$ , alors ${\mathcal {P}}(E)$ est un ensemble fini et on a $\mathrm {card} ({\mathcal {P}}(E))=2^{\mathrm {card} (E)}=2^{k}$ .

Cardinal de l'ensemble descorrespondances de $E {\displaystyle E}$ dans $F {\displaystyle F}$ — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis.
L'ensemble des correspondances de $E {\displaystyle E}$ dans $F {\displaystyle F}$ , noté habituellement $\mathrm {Corr} (E,F)$ , s'identifie à ${\mathcal {P}}(E\times F)$ donc est fini de cardinal $\ \mathrm {card} (\mathrm {Corr} (E,F))=2^{\mathrm {card} (E)\times \mathrm {card} (F)}=2^{nk}$ .

Cardinal de l'ensemble desapplications de $E {\displaystyle E}$ dans $F {\displaystyle F}$ — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis de cardinaux respectifs $k {\displaystyle k}$ et $n {\displaystyle n}$ .
L'ensemble des applications de $E {\displaystyle E}$ dans $F {\displaystyle F}$ , souvent noté ${\mathcal {F}}(E,F)$ , est fini de cardinal $\ \mathrm {card} ({\mathcal {F}}(E,F))=\mathrm {card} (F)^{\mathrm {card} (E)}=n^{k}$ avec laconvention 0⁰=1 si $E {\displaystyle E}$ et $F {\displaystyle F}$ sont tous deux vides.

Cette propriété justifie la notation plus courante $F^{E}$ .

Cardinal de l'ensemble dessurjections de $E {\displaystyle E}$ dans $F {\displaystyle F}$ — Soient $E {\displaystyle E}$ et $F {\displaystyle F}$ deux ensembles finis de cardinaux respectifs $k {\displaystyle k}$ et $n {\displaystyle n}$ .
L'ensemble des surjections de $E {\displaystyle E}$ dans $F {\displaystyle F}$ , noté habituellement $\mathrm {Surj} (E,F)$ , a pour cardinal la somme suivante:
$\ \mathrm {card} (\mathrm {Surj} (E,F))=\sum _{i=0}^{n}(-1)^{i}{\frac {n!}{i!(n-i)!}}(n-i)^{k}$ .
Cette somme est nulle si $\mathrm {card} (E)<\mathrm {card} (F)$ .

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 |modifier le code]

↑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.
↑(en)Usha Goswami,Cognitive development: The learning brain, New York, Psychology Press,2008.
↑Georges Ifrah,Histoire universelle des chiffres, page 46, Éditions Robert Laffont, Paris 1981.
↑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 |modifier le code]

Sur les autres projets Wikimedia :

dénombrement,sur leWiktionnaire

Portail des mathématiques

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Dénombrement&oldid=222145962 ».

Catégories :

Catégories cachées :

[8]ページ先頭