Terme

Ensemble équipotents

Définition

2 ensembles E et F sont dits équipotents (écrit \(E\sim F\)) s'il existe une bijection \(\varphi\) de \(E\to F\)

Terme

Propriétés de la relation d’équipotence

Définition

Réflextive, symétrique et transitive

Terme

Équipotence et cardinal

Définition

E et F ont le m\^eme cardinal \(\iff E\sim F\)

Terme

Définition d’un ensemble fini

Définition

E est fini si \(E=\varnothing\) ou s'il existe \(n\in\mathbb{N}\), tel que \(E \sim [\![1;n]\!]\)

Terme

Lemnes fondamentaux sur les ensemble finis

Définition

Il existe une injection de \([\![1;n]\!] \to [\![n,m]\!] \iff n\leq m\) et Il existe une bijection de \([\![1;m]\!] \to [\![1,n]\!] \iff n=m\)

Terme

Cardinalité et surjectivité, injectivité, bijectivité

Définition

Soit \(f:E\to F\) une application. Si \(f\) est injective, Card(E)\(\leq\)Card(F). Si \(f\) est surjective, Card(E)\(\geq\)Card(F). Si Card(E)=card(F), \(f\) est bijective \(\iff\) f est injective \(\iff\) f est surjective

Terme

Propriétés d’un sous-ensemble d’un enemble fini \(A\subset E\)

Définition

A est fini, de cardinal inférieur ou égal à E et si le cardinal est égal à celui de E, A = E

Terme

\(Card(A\cup B\)

Définition

\(\card(A\cup B) = \card(A) + \card(B) - \card(A\cap B)\)

Terme

\(\card(A\setminus B)\)

Définition

\(\card(A\setminus B) = \card(A) - \card(A\cap B)\)

Terme

Lemme des bergers

Définition

Compter les éléments de E revient à compter les éléments de l’application réciproque

Terme

Principe des tiroirs

Définition

Soit \(E,F\) 2 ensembles finis tel que \(card(E) \geq \card(F)\) alors il n'existe pas d'affectation injective de \(E\to F\), i.e soit \(f:E\to F\), \(\exists y\in F,\) tel que \(f^{-1}(\{y\})\) contient 2 éléments.

Terme

Nombre d'applications de X vers Y

Définition

Le nombre d'applications de X vers Y, de cardinaux respectifs \(n,p\geq 1\) est \(p^n\)

Terme

Cardinal des parties d’un ensemble

Définition

\(2^n\)

Terme

Définition d’un arrangement

Définition

Un arrangement parmi $n$ objets est une suite de \(p\) objets distincts pris parmi les \(n\) objets donnés.

Terme

Nombre d’arrangements

Définition

\(A^p_n = n(n-1)\dots(n-p+1) = \frac{n!}{(n-p)!}\)

Terme

Nombre de bijections entre 2 ensembles de même cardinal

Définition

\(n!\)

Terme

Combinaison

Définition

On appelle combinaison de \(n\) éléments de \(X\) pris \(p\) à \(p\) toute partie de \(X\) à \(p\) éléments. On le note \(C^p_n\). L'ordre n'a pas d'importance.

Terme

Nombre de combinaisons

Définition

Le nombre de parties à \(p\) éléments de \(X\) est \(C^p_n = \frac{n!}{p!(n-p)!} = \frac{A^p_n}{p!}\).

Terme

Valeurs importantes des combinaisons

Définition

\(C^0_n = 1\), \(C^n_n = 0\), \(C^1_n = n\)

Terme

Propriété de symétrie des combinaisons

Définition

\(C^{n-p}_n = C^p_n\)

Terme

Triangle de Pascal des combinaisons

Définition

\(C^p_n + C^{p+1}_n = C^{p+1}_{n+1}\)

Terme

Nombre de parties d'un ensemble

Définition

\(\sum^n_{k=0} C^p_n = 2^n\)