« Utilisateur:RM77/DMs » : différence entre les versions
Contenu supprimé Contenu ajouté
m →DM 7, Exo 2 : mwai... |
|||
Ligne 150 :
par conséquent, f est bijective. CQFD.
== Maths, -> 11/11/07 ==
=== DM8, Exercice 1 : Dénombrement des surjections===
On note <math>E\,</math> un ensemble fini et <math>A_1, A_2, ..., A_n\,</math> <math>n</math> parties de <math>E\,</math>.
## Exprimer <math>Card(A_1\cup A_2\cup A_3)\,</math> en fonction des cardinaux de <math>A_1, A_2, A_3\,</math> et de leurs intersections.
## Faire de même pour <math>Card(A_1\cup A_2\cup A_3\cup A_4)\,</math>.
## Pour tout entier <math>k</math> tq <math>1\le k\le n</math>, on note : <math>a_k = \sum_{1\le i_1<i_2<...<i_k\le n} Card(A_{i_1}\cap A_{i_2} \cap ...\cap A_{i_k})</math> où la somme porte sur tous les ''k''-uplets <math>(i_1,i_2,...,i_k)\,</math> d'entiers tq : <math>1\le i_1<i_2<...<i_k\le n\,</math>. Mq <math>Card \bigcup_{i=1}^n A_i = \sum_{k=1}^n (-1)^{k-1}a_k</math>.
# On note <math>E\,</math> et <math>F\,</math> deux ensembles finis de cardinaux respectifs ''n'' et ''p'' avec <math>1\le n\le p\,</math>, <math>\mathcal{S}(F,E)</math> l'ensemble des surjections ''f'' de <math>F\,</math> vers <math>E\,</math>, et <math>\mathcal{S}_n^p</math> le cardinal de <math>\mathcal{S}(F,E)</math>.
## Déterminer <math>\mathcal{S}_1^p</math>, <math>\mathcal{S}_2^p</math> et <math>\mathcal{S}_p^p</math>.
## Mq <math>\binom{n}{1} \mathcal{S}_1^p + \binom{n}{2} \mathcal{S}_2^p + \binom{n}{3} \mathcal{S}_3^p + ... + \binom{n}{n} \mathcal{S}_n^p = n^p</math>. On pourra pour cela classer les applications ''f'' de <math>F\,</math> vers <math>E\,</math> suivant le cardinal de <math>f(F)\,</math>.
## Mq <math>\mathcal{S}_n^p = n(\mathcal{S}_n^{p-1} + \mathcal{S}_{n-1}^{p-1})</math>. On pourra pour cela choisir un élément ''a'' de <math>F\,</math> et étudier les images <math>f(a) \mbox{ et } f(F-\left \{a\right \})</math> par ''f''. En déduire la valeur de <math>\mathcal{S}_n^{n+1} \mbox{ et } \mathcal{S}_n^{n+2}</math>.
## En utilisant la question 1.3, mq :
##: <math>\mathcal{S}_n^p = n^p -\binom{n}{1}(n-1)^p +\binom{n}{2}(n-2)^p -\binom{n}{3}(n-3)^p +...+(-1)^{n-1}\binom{n}{n-1}</math>
## Rédiger un programme Maple renvoyant <math>\mathcal{S}_n^p</math> pour des valeurs données de ''n'' et ''p''. Calculer <math>\mathcal{S}_5^{10}</math>.
## Rédiger un programme Maple renvoyant le tableau à deux dimensions des <math>\mathcal{S}_n^p</math> pour <math>0\le n\le p\le q\,</math> où l'entier ''q'' est donné. Calculer la valeur de <math>\mathcal{S}_n^p</math> pour <math>0\le n\le p\le 5\,</math>. On présentera les résultats sous la forme d'un tableau à double entrée.
## Donner le nombre de ''n''-uplets <math>(A_1, A_2,...A_n)\,</math> de parties de <math>F\,</math> réalisant une ''partition'' de <math>F\,</math> en ''n'' parties i-e tq : aucun <math>A_i\,</math> n'est vide, la réunion des <math>A_i\,</math> est <math>F\,</math>, et les <math>A_i\,</math> sont deux à deux disjoints.
| |||