Ensembles finis, dénombrement -...

PCSI2

N.Véron-LMB-dec 2012

Exercices-Chapitre 10: ensembles finis, dénombrement, sommes ♦♦♦♦ éléments de correction en ligne

���� Ensembles finis, dénombrement

1.1 Soit n un entier naturel. a) Déterminer le nombre de solution de l'équation x+y = n dans �².

b) Déterminer le nombre de solution de x1+x2+...xp = n dans Ep où E={0,1}

c) Déterminer le nombre de solutions de x1+x2+...xp = n dans �p

1.2 Soit n∈�*, E un ensemble fini de cardinal n et F un ensemble fini de cardinal n+1.

a) Déterminer le nombre de surjections de E sur {a,b}. b) Déterminer le nombre de surjections de F sur E. c) Quel est le nombre d'applications non surjectives de E dans E?

♦♦♦♦ 1.3 Soit E un ensemble fini de cardinal n. a) Dénombrer les couples (A,B) de P(E) tels que A⊂B. b) Dénombrer les couples (A,B) de P(E) tels que A⊄B et B⊄A.

♦ 1.4 Soit E un ensemble et f une application de E dans E. f est idempotente si et seulement si fοf=f. a) Donner un exemple d'application idempotente distincte de IdE. b) Montrer que si f est idempotente et si f est injective ou surjective alors f=IdE. c) Montrer l'équivalence: f est idempotente ⇔ ∀x∈f(E), f(x)=x d) On suppose E fini de cardinal n, déduire de ce qui précède le nombre d'applications idempotentes de E dans E.

���� Avec les coefficients binomiaux

2.1 Calcul de n

k 1

nkk=

∑

a) En transformant le terme général de la somme

b) En calculant de deux manières différentes A ( E )

card(A)∈∑P

c) En dérivant de deux manières différentes la fonction polynôme p(x) = (1+x)n

2.2 Soit n et k deux entiers tels que 0≤k≤n, démontrer que: k

i 0

2n n n

k i k i=

= − ∑

a) En utilisant un ensemble de cardinal 2n. b) En développant (1+x)2n de deux manières différentes.

2.3 Calculer les sommes suivantes:

A= nn n n n... ( 1)

0 1 2 n

− + − + −

B=

0 2 k n

n

2k≤ ≤

∑ C= k

0 2 k n

n( 1)

2k≤ ≤

−

∑

D=n

k 0

nsin(k )

k=

θ

∑ E=

n

k 1

nk²

k=

∑ F=n

k p

k

p=

∑

♦♦♦♦ 2.4 On définit la suite u par u0=1 et ∀n∈�*, un=

n 1

pp 0

nu

p

−

=

∑ .

Montrer que pour tout n∈�, un est un entier naturel impair.

♦♦♦♦ 2.5 Montrer que ∀(p,q)∈�², q

k 0

p k p q 1

p p 1=

+ + += +

∑