Sujet du DM n°4 - Sébastien Godillon

DM no 4 de mathématiques
à rendre au plus tard le lundi 17 novembre
Problème 1
Soient E et F deux ensembles finis de cardinaux respectifs n = card(E) > 1 et p = card(F ) > 1. Ce
problème propose d’étudier le nombre Sn,p de surjections de E vers F .
1. Donner la valeur de Sn,p lorsque n < p.
2. Donner la valeur de Sn,p lorsque n = p.
3. Donner la valeur de Sn,1 .
4. On suppose p = 2 pour cette question.
(a) Rappeler l’expression de card(F E ).
(b) Dénombrer les applications de E vers F qui ne sont pas surjectives.
(c) En déduire la valeur de Sn,2 .
5. On suppose n > p pour cette question et on fixe un élément x ∈ E.
(a) Calculer, en fonction de Sn−1,p , le nombre de surjections f : E → F telles que la restriction
f |E\{x} : E \ {x} → F est surjective.
(b) Calculer, en fonction de Sn−1,p−1 , le nombre de surjections f : E → F telles que la
restriction f |E\{x} : E \ {x} → F n’est pas surjective.
(c) En déduire que Sn,p = pSn−1,p + pSn−1,p−1 .
6. A l’aide des questions précédentes et en s’inspirant du triangle de Pascal, construire un tableau
présentant les valeurs de Sn,p pour n et p compris entre 1 et 6.
7. En dénombrant
les applications de E vers F de deux manières différentes, démontrer que
P
pn = pk=1 kp Sn,k .
Problème 2
Une puce monte un escalier par sauts successifs de une ou deux marches. Pour tout entier n > 1, on
note un le nombre de façons dont elle peut enchaîner des sauts d’une ou deux marches pour atteindre
la n-ième marche (on suppose que la puce est au départ sur la marche numéro 0).
1. Cette question propose de déterminer une expression de un en fonction de n.
(a) Montrer que u1 = 1 et u2 = 2.
(b) Calculer u3 , u4 et u5 .
(c) Démontrer que ∀n > 3, un = un−1 + un−2 .
(d) En déduire une expression de un en fonction de n pour tout n > 1.
2. Cette question propose de calculer une certaine somme de coefficients binomiaux. On fixe
n > 1 et on note k le nombre de sauts de deux marches effectués par la puce pour atteindre
la n-ième marche.
(a) Montrer que k ∈ 0, 1, 2, . . . , b n2 c .
(b) Calculer, en fonction de k, le nombre total de sauts nécessaires pour atteindre la n-ième
marche.
(c) Déterminer le nombre de façons dont la puce peut enchaîner n − 2k sauts d’une marche
et k sauts de deux marches pour atteindre la n-ième marche.
Pbn/2c
(d) En déduire une expression de la somme k=0 n−k
k .
BCPST 1A lycée Hoche 2014-2015
Sébastien Godillon
1 sur 1

Download Report