TD2 ECS : Sommes, Produits et combinatoire élémentaire.

Exercice 1

1. Montrer que : $\sum \limits_{k=0}^{E(n/2)} {{n}\choose {2k}} = \sum \limits_{k=0}^{E((n-1)/2)} {{n}\choose {2k+1}}=2^{n-1}$, $n\in \mathbb N^*$
2. Calculer les sommes :
   2
   
   1. $\sum \limits_{k=0}^{n-p} {{p+k}\choose {p}} $, avec 0 ≤ p ≤ n
   2. $\sum \limits_{k=0}^n k {{n}\choose {k}}$
   3. $\sum \limits_{k=0}^n \frac{{{n}\choose {k}}}{k+1} $
   4. $\sum \limits_{k=0}^n {{n}\choose {k}}^2 $
   5. $\sum \limits_{k=0}^{E(n/3)} {{n}\choose {3k}}$

Exercice 2
Calculer les produits suivants:

1. $\prod \limits_{k=1}^n \left( \frac{1}{1+k} \right)$
2. $\prod \limits_{k=1}^n \cos\left( \frac{a}{2^k} \right)$, avec a ∈ ]0, 2π]

Exercice 3
Calculer les sommes suivantes :
2

1. $\sum \limits_{k=0}^n \frac{1}{k(k+1)}$.
2. $\sum \limits_{k=0}^n k k!$.
3. $\sum \limits_{k=0}^n \frac{1}{k(k+1)(k+2)}$.
4. $\sum \limits_{k=0}^n \frac{k}{(k+1)!}$.
5. $\sum \limits_{k=0}^n k^p$ ; avec p ∈ {2, 3, 4}
   (Sans utiliser la récurrence)

Exercice 4
Soit ${(a_n)}_{n\in \mathbb N}$ et ${(B_n)}_{n\in \mathbb N}$ deux suites réelles, On définit les suites ${(A_n)}_{n\in \mathbb N}$ et ${(b_n)}_{n\in \mathbb N}$ pour tout $n\in \mathbb N $, A_n = ∑_k = 0ⁿa_k et b_n = B_n + 1 − B_n.

1. Montrer que pour tout $n\in \mathbb N^*$ : ∑_k = 0ⁿB_ka_k = A_nB_n − ∑_k = 0^n − 1A_kb_k.
2. Application : pour tout réel x calculer ∑_k = 0ⁿkx^k.
3. En utilisant la dérivé retrouver la somme ∑_k = 0ⁿkx^k pour tout réel x.

Exercice 5
Calculer les sommes suivantes:

1. $\sum \limits_{ 1\leq i,j \leq n} ij$.
2. $\sum \limits_{1\leq i<j \leq n} j$.
3. $\sum \limits_{1\leq i,j \leq n} min(i,j)$ et $\sum \limits_{1\leq i,j \leq n} max(i,j)$
4. $\sum \limits_{1\leq i,j \leq n} |i-j|$
5. $\sum \limits_{1\leq i<j \leq n} \frac{i}{j}$.

Exercice 6
Pour E un ensemble fini, déterminer le cardinal de AΔB.

Exercice 7
Soit E un ensemble à n éléments, et A ⊂ E un sous-ensemble à p ’éléments. Quel est le nombre de parties de E qui contiennent un et un seul éléement de A ?

Exercice 8
Soit E un ensemble fini de cardinal n, et A une partie de E, déterminer le nombre des parties de E disjointe de A

Exercice 9
Soit E un ensemble fini de cardinal n, déterminer le cardinal de l’ensemble {(X, Y) ∈ P(E)²  :  X ⊂ Y}

Exercice 10
Soit E un ensemble fini de cardinal n, déterminer le cardinal de l’ensemble {(X, Y) ∈ P(E)²  :  X ∩ Y = ∅}

Exercice 11
Soit E un ensemble fini de cardinal n ≥ 1, déterminer le nombre des parties de E de cardinal pair.

Exercice 12

1. (principe des bergers) Soient E, F deux ensembles avec F ensemble fini, et f une surjection de E sur F vérifiant :
   ∀y ∈ F,  Card(f^− 1(y)) = p
   Montrer que E est alors un ensemble fini et Card(E) = pCard(F).
2. (principe des tiroirs) Soient α₁, α₂, …, α_p,  p élements distincts d’un ensemble E, répartis entre une famille de n sous-ensembles de E. Si n < p montrer qu’il existe au moins un ensemble de la famille contenant au moins deux éléments parmi les α_i.(on pourra raisonner par l’absurde)

Exercice 13
On se propose de calculer le nombre S(n, p) de surjections de {1, …, n} sur {1, …, p}, où net p sont des entiers naturels non nuls.

1. Des cas particuliers :
   
   1. Calculer S(n, p) pour p > n.
   2. Calculer S(n, n).
   3. Calculer S(n, 1).
   4. Calculer S(n, 2).
   5. Calculer S(n + 1, n).
2. Démontrer que, pour tout n > 1 et tout p > 1, on a la relation S(n, p) = p(S(n − 1, p) + S(n − 1, p − 1)).
3. En déduire un algorithme pour calculer S(n, p).
4. Démontrer que $S(n,p)=\sum\limits_{k=0}^{n}(-1)^{p-k}{{p}\choose {k}} k^n$.