\input exos
\fiche{Ensembles finis}

%----------------------------------------------------------------------
\ex Permutations de $⟦1,12⟧$

Combien y a-t-il de bijections $f$ de $⟦1,12⟧$ dans lui même possédant :

\qq la propriété : $n$ est pair $⇒ f(n)$ est pair ?
    \reponse{\hbox to 2cm{$(6!)²$,\hfil} $6^6×12^6$.}

\qq la propriété : $n$ est divisible par 3 $⇒ f(n)$ est divisible par 3 ?
    \reponse{\hbox to 2cm{$4!×8!$,\hfil} $4^4×12^8$.}

\qq ces deux propriétés à la fois ?
    \reponse{\hbox to 2cm{$2!2!4!4!$,\hfil} $2²×4²×6^4×12^4$.}

\qq Reprendre les questions précédentes en remplaçant {\it bijection\/} par
    {\it application.}


%----------------------------------------------------------------------
\ex Permutations de couples

On doit placer autour d'une table ronde un groupe de $2n$ personnes, $n$ hommes
et $n$ femmes, qui cons\-ti\-tuent $n$ couples.
Combien existe-t-il de dispositions …

\qq au total ?                                       \reponse{$(2n)!$.}
\qq en respectant l'alternance des sexes ?           \reponse{$2(n!)²$.}
\qq sans séparer les couples ?                       \reponse{$2^{n+1}×n!$.}
\qq en remplissant les deux conditions précédentes ? \reponse{$4×n!$.}

%----------------------------------------------------------------------
\ex Nombre d'opérations

\qq Combien existe-t-il d'opérations internes sur un ensemble à $n$ éléments ?
    \reponse{$n^{n²}$.}
\qq Combien sont commutatives ?
    \reponse{$n^{n(n+1)/2}$.}
\qq Combien ont un élément neutre ?
    \reponse{$n× n^{(n-1)²}$.}
\qq Combien sont commutatives et ont un élément neutre ?
    \reponse{$n× n^{n(n-1)/2}$.}

%----------------------------------------------------------------------
\ex Formule du crible

Soient $A₁,…, A_n$, $n$ ensembles finis.

\qqsq Calculer $\card(A₁∪A₂∪A₃)$ et $\card(A₁∪A₂∪A₃∪A₄)$.
   \sq Suggérer une formule pour $\card(A₁∪…∪A_n)$.
   \label{devine}

\qq Démonstration de la formule : On note $E = ⋃_{i=1}^n A_i$, et
   pour $x∈E$ on pose $f_i(x) = 1$ si $x ∈ A_i$, $f_i(x)=0$ sinon.
\sq Soient $x₁,…,x_n∈ℝ$. Développer complètement $p = (1-x₁)× … × (1-x_n)$.
\sq En considérant la somme $⅀_{x ∈ E} (1-f₁(x))…(1-f_n(x))$,
    démontrer la formule \ref{devine}.

\qq Applications :

\sq Déterminer le nombre d'applications $f : ⟦1,p⟧→⟦1,n⟧$
    non surjectives.
    \reponse{$⅀_{k=1}^n (-1)^k\bin nk(n-k)^p$.}
\sq Déterminer le nombre de permutations d'un ensemble à $n$ éléments ayant
    au moins un point fixe.
    \reponse{$⅀_{k=1}^n \dfrac{(-1)^kn!}{k!}$.}


%----------------------------------------------------------------------
\ex Inégalités pour la formule du crible

Soient $A₁,…,A_n$, $n$ ensembles finis, et $E = ⋃_{i=1}^n A_i$.

\qq Montrer que $\card(E) ⩽ ⅀_{i=1}^n \card(A_i)$. Cas d'égalité ?
\qq Montrer que $\card(E) ⩾ ⅀_{i=1}^n \card(A_i) -
    ⅀_{1⩽i<j⩽n} \card(A_i∩A_j)$. Cas d'égalité ?
    \reponse{Récurrence. Égalité pour $n⩽2$ ou les $A_i$ 3 à 3 disjoints.}

%----------------------------------------------------------------------
\ex Couples $(A,B)$ tels que  $A∪B = E$

Soit $E$ un ensemble fini à $n$ éléments, et
$𝓔 = ⦃ (A,B) ∈ 𝓟(E)² \tq A∪B = E ⦄$. Chercher card($𝓔$).
\reponse{$3^n$.}

%----------------------------------------------------------------------
\ex Parties ne contenant pas d'éléments consécutifs

\qq Combien y a-t-il de parties à $p$ éléments de $⟦1,n⟧$ ne contenant
    pas d'éléments consécutifs ?

    Indication : Si $⦃x₁,…, x_p⦄$ est une telle partie avec
    $x₁ < x₂ < … < x_p$, considérer l'ensemble
    $⦃ x₁-1, …, x_p-p⦄$.

    \reponse{$⦃ x₁-1, …, x_p-p⦄$ est une partie quelconque de $⦃0, …, n-p⦄$,
             donc $N = \dbin{n-p+1}p$.}

\qq Soit $t_n$ le nombre de parties de $⟦1,n⟧$ de cardinal quelconque
   sans éléments consécutifs.

\sq Montrer que $t_{n+2} = t_{n+1} + t_n$, $t_{2n+1} = t_n² + t_{n-1}²$,
    et $t_{2n} = t_n² - t_{n-2}²$.
\sq Calculer $t_{50}$.
    \reponse{32951280099.}

%----------------------------------------------------------------------
\ex Nombre de relations d'équivalence

Soit $R_n$ le nombre de relations d'équivalence sur un ensemble à $n$ éléments.

\qq Trouver une relation de récurrence entre $R_n$ et les $R_k$, $k < n$
    (fixer un élément, et raisonner sur la classe d'équivalence de cet élément).
    \reponse{$R_n = ⅀_{k=0}^{n-1}\bin{n-1}kR_k$ avec $R_0 = 1$.}
\qq Calculer $R_n$ pour $n ⩽ 6$.
    \reponse{1,1,2,5,15,52,203.}


%----------------------------------------------------------------------
\ex Equivalence entre fonctions

Soient $E,F$, deux ensembles non vides. On définit deux relations sur $X = F^E$
par :
$$\eqalign{
  f ∼ g &⇔ ∃φ:F→F \text{ bijective tq } g=φ∘f~;\cr
  f ≡ g &⇔ ( ∀x,y∈E,\ f(x)=f(y)⇔ g(x)=g(y)).\cr
}$$

\qq  Montrer que ce sont des relations d'équivalence.
\qq  Montrer que $f∼g ⇒ f≡g$.
\qq  On suppose $f≡g$. Montrer que $f∼g$ dans les cas suivants :

\sq  $F$ est fini et $f$ est surjective.
\sq  $F$ est fini et $f$ est quelconque.
\sq  $E$ est fini.
\qq  Chercher un contrexemple pour $E = F = ℕ$.

%----------------------------------------------------------------------
\ex Très bon ordre

Soit $E$ un ensemble ordonné dans lequel toute partie non vide possède un
plus grand et un plus petit élément.
Montrer que $E$ est totalement ordonné et fini.

%----------------------------------------------------------------------
\ex Élément maximal

Soit $E$ un ensemble ordonné. Un élément $a ∈ E$ est dit {\it maximal\/}
s'il n'existe pas de $b ∈ E$ tq $b > a$.

\qq   Si $E$ est totalement ordonné, montrer que :
      {\it maximal\/} $⇔$ {\it maximum.}
\qq   $E = ⦃1,2,3,4,5,6⦄$ ordonné par la divisibilité. Chercher les
      éléments maximaux.
\qq   Si $E$ est fini, montrer qu'il existe un élément maximal.
\qq   Si $E$ est fini et n'a qu'un seul élément maximal, montrer que cet
      élément est maximum.

%----------------------------------------------------------------------
\ex Nombres de Catalan

Soient $x₁,…,x_n$, $n$ réels. Pour calculer la somme $x₁+…+x_n$,
on place des parenthèses de façon à n'avoir que des additions de deux nombres
à effectuer. Soit $t_n$ le nombre minimal de manières de placer les parenthèses
(on pose $t₁ = 1$).

\qq Déterminer $t₂,t₃,t₄$.
    \reponse{1,2,5.}
\qq Trouver une relation de récurrence entre $t_n$ et $t₁,…,t_{n-1}$.
    \reponse{$t_n = ⅀_{k=1}^{n-1}\,t_kt_{n-k}$.}

\bye
