TD dénombrement

dimanche 9 février 2020
par  JL
popularité : 18%

PDF - 136.2 ko
TD dénombrement
  • Corrigé de l’exercice 6 :

    1. On peut effectuer $\binom{20}4=4845$ prélèvement différents.
    2.a) 4 bonnes parmi les 16 : $\binom{16}4=1820$.
    2.b) La négation est toutes les pièces sont bonnes soit $\binom{20}4 - \binom{16}4=3025$
    2.c) 1 mauvaise et 3 bonnes : $4\cdot\binom{16}3=2240$.
    2.d) Soit 4, soit 3, soit 2 mauvaises (exclusivement) donc $1 + 4\cdot16+\binom 42\binom{16}2=785$.

  • Corrigé de l’exercice 13 : Formule du crible

    Par récurrence sur n :
    - C’est évident $n=1$ et vrai pour $n=2$ d’après le cours.
    - Si, pour un $n\geqslant2$, c’est vrai au rang $n-1$, alors

    $$|A_1\cup\dotsb\cup A_n|=|(A_1\cup\dotsb\cup A_{n-1})\cup A_n|$$


    donc par le cas $n=2$,

    $$|A_1\cup\dotsb\cup A_n|=|A_1\cup\dotsb\cup A_{n-1}| + |A_n| - |(A_1\cup\dotsb\cup A_{n-1})\cap A_n|$$


    soit

    $$|A_1\cup\dotsb\cup A_n|=|A_1\cup\dotsb\cup A_{n-1}| + |A_n| - |(A_1\cap A_n)\cup\dotsb\cup (A_{n-1}\cap A_n)|$$


    Par HR,

    $$S_1=|A_1\cup\dotsb\cup A_{n-1}| = \sum_{k=1}^{n-1}{(-1)^{k+1}\sum_{1\leqslant i_1 < \dotsb < i_k\leqslant n-1}{|A_{i_1}\cap\dotsb\cap A_{i_k}|}}$$


    contient tous les termes de la formule finale ne faisant pas intervenir $A_n$ (les intersections ont alors au plus $n-1$ termes) ; et, toujours par HR,

    $$S_2=|A_n| - |(A_1\cap A_n)\cup\dotsb\cup (A_{n-1}\cap A_n)|\\ =|A_n|-\sum_{k=1}^{n-1}{(-1)^{k+1}\sum_{1\leqslant i_1 < \dotsb < i_k\leqslant n-1}{|A_{i_1}\cap\dotsb\cap A_{i_k}\cap A_n|}}\\ =|A_n|+\sum_{k=1}^{n-1}{(-1)^{k+2}\sum_{1\leqslant i_1 < \dotsb < i_k < i_{k+1}=n}{|A_{i_1}\cap\dotsb\cap A_{i_k}\cap A_{i_{k+1}}|}}\\ = |A_n|+\sum_{\ell=2}^{n}{(-1)^{\ell+1}\sum_{1\leqslant i_1 < \dotsb < i_{\ell-1} < i_{\ell}=n}{|A_{i_1}\cap\dotsb\cap A_{i_\ell}|}}\\ =\sum_{k=1}^{n}{(-1)^{k+1}\sum_{1\leqslant i_1 < \dotsb < i_{k-1} < i_{k}=n}{|A_{i_1}\cap\dotsb\cap A_{i_k}|}} $$

    contient tous les termes de la formule finale faisant intervenir $A_n$.
    Donc, comme $|A_1\cup\dotsb\cup A_n|=S_1+S_2$, la récurrence est établie.

  • Corrigé de l’exercice 14 : Théorème de Lagrange


    - 1. La relation est réflexive car $e_G\in H$, symétrique car $y^{-1}*x=\left(x^{-1}*y\right)^{-1}$ et $H$ stable par passage à l’inverse, et transitive car $x^{-1}*z=\left(x^{-1}*y\right)*\left(y^{-1}*z\right)$ et $H$ stable par $*$.
    - 2. $cl(x)=xH=\{x*h\ ;\ h\in H\}$ a comme cardinal $|H|$ car on a une bijection $h\mapsto x*h$ de $H$ dans $cl(x)$ (vu que $x$ est inversible).
    - 3. Comme les classes d’équivalence forment une partition de $G$, si on a $p$ classes, on obtient $|G| = p|H|$ donc $|H|$ divise $|G|$.
    - 4. L’ordre $n$ de $x\in G$ est le cardinal du sous-groupe $\left\{x^k\ ;\ k\in\mathbb Z\right\}=\left\{e_G, x, x^2, \dotsc, x^{n-1}\right\}$ (il suffit de poser la division euclidienne de $k$ par $n$, les éléments sont deux à deux distincts par minimalité de $n$.)

  • Corrigé de l’exercice 16

    Soit $A$ un anneau fini intègre. On veut montrer que si $a\neq0_A$, alors $a$ est inversible.
    Or l’application $x\mapsto ax$ de $A$ dans $A$ est injective par intégrité. En effet c’est un morphisme de groupe additif car pour tout $x, x’$, $a(x+x’)=ax+ax’$ et si $ax=0_A$ alors, comme $a\neq0_A$ et $A$ est intègre, $x=0_A$ : le noyau est réduit à $\{0_A\}$.
    Mais comme $A$ est fini, c’est aussi une bijection. Donc $1_A$ admet un antécédent : l’inverse de $a$.

  • Corrigé de l’exercice 18 : Bazar bizarre

    Pour les cartes présentant un objet de la bonne couleur, il y a 5 possibilité pour cet objet, puis 4 pour le deuxième qui n’a ni sa couleur ni celle du premier objet, donc 3 couleurs possible. Il y en a donc $5\times 4\times 3 = 60$.
    Pour les autres, on choisit 2 objets parmi les 5 puis des couleurs pour chacun parmi les 3 qui ne sont pas celles des objets (pour être sûr qu’il n’en reste qu’un à attraper) soit $\binom 5 2\times 3\times 2=60$.
    Il y a donc $120$ cartes possibles (mais seulement $60$ dans la boite.)


Documents joints

Script Bazar bizarre

Commentaires

Publications

Derniers articles publiés