Règle de la somme

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En analyse combinatoire, la règle de la somme^{[réf. nécessaire]} ou principe d'addition^{[réf. souhaitée]} 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.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (décembre 2017).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Un exemple simple

Une personne 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 une boutique de vêtements, soit dans un magasin de bricolage, soit chez un chapelier (3 options). Si elle se rend dans le sud de la ville, alors elle a le choix entre une boulangerie et une épicerie (2 options).

Finalement, il y a 3 + 2 = 5 magasins possibles où elle pourra effectuer un achat aujourd'hui.

Formalisation

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, \dots , S n$ sont des ensembles deux à deux disjoints, alors :

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

.

Principe d'inclusion-exclusion

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 les éléments dans la réunion de plusieurs ensembles, sans que ces ensembles doivent être disjoints. Il établit que si $A 1, \dots , A n$ sont des ensembles finis, alors

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{1\leq i<j<k\leq 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{aligned}}

Référence

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Rule of sum » (voir la liste des auteurs).

Portail des mathématiques