Sujet : Algèbre, Ensembles et applications, Dénombrement

[http://mp.cpgedupuydelome.fr] édité le 10 septembre 2013 Enoncés 1 Dénombrement Exercice 7 [ 01535 ] [correction] ? p nPour n∈N et p∈N, on note Σ le nombre de n uplets (x ,...,x )∈N tels1 nn que x +··· +x =p.1 nExercice 1 [ 01529 ] [correction] p p0 1 2a) Déterminer Σ , Σ , Σ , Σ et Σ .n n n 1 2Soient E et F deux ensembles finis de cardinaux respectifs n et p. b) EtablirCombien y a-t-il d’injections de E dans F ? ? p 0 1 p∀n∈N ,∀p∈N, Σ = Σ + Σ +··· + Σn+1 n n n c) En déduire que ! Exercice 2 [ 01530 ] [correction] n +p− 1pΣ =nSoient E ={1,...,n} et F ={1,...,p} avec n6p∈N. p Combien y a-t-il d’applications strictement croissantes de E vers F ? Exercice 8 [ 01536 ] [correction] Exercice 3 [ 01531 ] [correction] Soit E un ensemble à n éléments. Combien existe-t-il de relation d’ordre total sur un ensemble E à n éléments? a) Soit X une partie à pts de E. Combien y a-t-il de parties Y de E disjointes de X? b) Combien y a-t-il de couples (X,Y ) formés de parties disjointes de E? Exercice 4 [ 01532 ] [correction] On trace dans un plan n droites en position générale (i.e. deux d’entre elles ne sont jamais parallèles ni trois d’entre elles concourantes). Combien forme-t-on Exercice 9 [ 01537 ] [correction] ainsi de triangles? Soit E un ensemble à n éléments. Combien y a-t-il de parties X et Y de E telles que X⊂Y ? Exercice 5 [ 01533 ] [correction] Soient p,q∈N et n∈ [0,p +q].