Exercices: Nombre de parties d'un ensemble

Lister toutes les parties de l'ensemble $E = \{a, b, c\}$ et vérifier que leur nombre est $2^3$.

Combien l'ensemble $\{1, 2, 3, 4, 5, 6\}$ possède-t-il de parties ?

Combien existe-t-il de mots binaires (composés de $0$ et de $1$) de longueur $8$ ?

Une pizzeria de Marseille propose $7$ ingrédients supplémentaires. Un client choisit n'importe quelle combinaison d'ingrédients (éventuellement aucun).

1. a) Combien de pizzas différentes peut-il composer ?

1. b) Combien de pizzas contiennent au moins un ingrédient ?

Soit $E$ un ensemble à $n$ éléments.

1. a) Établir une bijection entre les parties de $E$ et les mots binaires de longueur $n$.

1. b) Combien de parties de $E$ ont un nombre pair d'éléments pour $n = 5$ ?

Une classe de $30$ élèves doit désigner un comité (de taille quelconque, éventuellement vide ou complet).

1. a) Exprimer le nombre de comités possibles.

1. b) Combien de comités comportent exactement $3$ élèves ?

1. c) Utiliser le principe additif pour exprimer le nombre de comités de $0$ à $2$ élèves.

Soit $E$ un ensemble à $n$ éléments, $n \geq 1$.

1. a) Montrer, à l'aide de la formule du binôme, que $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$.

1. b) Montrer que $\displaystyle\sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0$ et en déduire que $E$ a autant de parties de cardinal pair que de parties de cardinal impair.

Soit $E$ un ensemble à $n$ éléments. On souhaite compter les couples $(A, B)$ de parties de $E$ tels que $A \subset B$.

1. a) Pour chaque élément $x$ de $E$, combien y a-t-il de situations possibles ($x\in A$, $x \in B\setminus A$, $x \notin B$) ?

1. b) En déduire le nombre de couples $(A,B)$.

1. c) Retrouver ce résultat par $\displaystyle\sum_{k=0}^{n}\binom{n}{k}2^{k}$.

Un code est un mot binaire, c'est-à-dire une suite finie de « 0 » et de « 1 ».

1. a) Combien de codes ne contiennent pas deux « 1 » consécutifs pour une longueur $3$ ? Pour une longueur $4$ ?

1. b) On note $c_n$ le nombre de tels codes de longueur $n$. Montrer que $c_{n+2} = c_{n+1} + c_n$.

1. c) Calculer $c_{10}$.