Règle de la somme

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En analyse combinatoire, la règle de la somme ou principe d'addition est un principe de base du dénombrement. C'est l'idée que si nous avons a façons de faire quelque chose et b façons d'en faire une autre, mais que nous ne pouvons pas faire les deux en même temps, alors il y a a + b façons de choisir une de ces actions.

Un exemple simple[modifier | modifier le code]

Une femme a décidé d'effectuer un achat dans une boutique aujourd'hui, soit dans le nord de la ville, soit dans le sud de la ville. Si elle va dans le nord, elle peut aller soit dans un boutique de mode, de décoration ou chez un joaillier (3 options). Si elle se rend dans le sud de la ville, alors elle a le choix entre une boutique de chaussures et un chapelier (2 options).

Au final il y a 3+2=5 magasins possibles où cette personne pourra effectuer un achat aujourd'hui.

Formalisation[modifier | modifier le code]

De façon plus formalisée, la règle de la somme a trait à la théorie des ensembles. Elle établit que la somme des tailles d'une collection finie d'ensembles deux à deux disjoints est la taille de la réunion de ces ensembles. Ainsi, si S_{1}, S_{2},..., S_{n} sont des ensembles deux à deux disjoints, alors nous avons:

|S_{1}|+|S_{2}|+\cdots+|S_{n}| = |S_{1} \cup S_{2} \cup \cdots \cup S_{n}|

Principe d'inclusion-exclusion[modifier | modifier le code]

Le principe d'inclusion-exclusion peut être considéré comme une généralisation de la règle de la somme, au sens où il dénombre également le nombre d'éléments dans la réunion de plusieurs ensembles , sans que ces ensembles doivent être disjoints. Il établit que si A1, ..., An sont des ensembles finis, alors


\begin{align}
\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.
\end{align}

Note et référence[modifier | modifier le code]

Voir aussi[modifier | modifier le code]