Fiche de mathématiques

École Polytechnique
Concours d'admission 2008
Filière MP
Deuxième composition

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Durée : 4 heures

Dénombrement d'applications entre ensembles finis

On se propose de démontrer quelques propriétés du nombre des applications surjectives d'un ensemble fini sur un autre.
Étant donné deux nombres entiers strictement positifs $k$ et $n$ , on note

$p_{k,n}$ le nombre de parties à $k$ éléments de l'ensemble $\lbrace 1,...,n \rbrace$ , nul si $k > n$ ; on rappelle que $p_{k,n} = \left( \begin{array}{l} n\\ k \end{array} \right)$ pour $k \leq n$ ;

$j_{k,n}$ le nombre d'applications injectives de $\lbrace 1,...,k\rbrace$ dans $\lbrace 1,...,n \rbrace$ , nul si $k > n$ ;

$s_{k,n}$ le nombre d'applications surjectives de $\lbrace 1,...,k \rbrace$ dans $\lbrace 1,...,n\rbrace$ , nul si $k < n$ .

On posera aussi $p_{0,n} = j_{0,n} = 1$ .

Première partie

1. Préciser les valeurs de $j_{n,n}$ et $s_{n,n}$ .

2. Montrer que l'on a $j_{k,n} = \left( \begin{array}{l} n \\ k \end{array} \right) k !$ si $k \le n$ .

Pour tout entier $r > 0$ , on note $P(r)$ (resp. $S(r)$ ) la mattrice ) $r$ lignes et $r$ colonnes de coefficients $P(r)_{k,n} = p_{k,n}$ (resp. $S(r)_{k,n} = s_{k,n}$ ) pour $k,n = 1, \cdots , r$ .

3. a) Montrer que l'on a, pour $k$ et $n > 0$ :
$n^k = \displaystyle \sum_{q = 1, \cdots , n} s_{k,q} p_{q,n}$ .

3. b) Calculer le déterminant de la matrice $A(r)$ de coefficients $A(r)_{k,n} = n^k$ , $k, n = = 1, ... ,r$ .

Deuxième partie

Pour tout entier $d > 0$ , on désigne par $E_d$ l'espace vectoriel des polynômes à une indéterminée, à coefficients complexes, de degré $\leq d$ . On le munit de la base $(X^0 = 1 , X , ... , X^d)$ ; on définit un endomorphisme $T$ de $E_d$ par : $T(P)(X) = P(X+1)$ pour tout $P \in E_d$ .

4. a) Déterminer les coefficients $T_{k,n}$ de la matrice représentant $T$ dans la base indiquée (ici, $0 \leq k,n \leq d$ ).

4. b) Même question pour $T^{-1}$ dont on démontrera l'existence.

4. c) Étant donné deux vecteurs lignes $(a_0,...,a_d)$ et $(b_0,...,b_d)$ satisfaisant $a_0=b_0$ et, pour $n=1,...,d$ , $a_n = \displaystyle \sum_{q=0,...,n} b_q \left( \begin{array}{l} n\\q \end{array} \right)}$ ,
écrire les $b_q$ en fonction des $a_n$ .

4. d) Établir une formule de la forme $s_{k,n} = \displaystyle \sum_{q=1,...,n} \lambda_{n,q} q^k \left( \begin{array}{l} n\\q \end{array} \right)}$ ,
où $0 < n \leq k$ et où les $\lambda_{n,q}$ sont des coefficients à déterminer.

Dans la suite de cette seconde partie, on définit des éléments de $N_k$ de $E_d$ , $k=0,1,...,d$ , par $N_k(X) = \left \lbrace \begin{array}{ll} 1 & \text{ si } k = 0\\ \dfrac{1}{k!} X(X + 1) \cdots (X + k - 1) & \text{ si} k > 0 \\ \end{array} \right.$

5. Vérifier que les $N_k$ forment une base de $E_d$ .

6. Démontrer la formule $T(N_k) = N_k + T(N_{k-1})$ pour $k > 0$

7. a) Déterminer les coefficients $\tilde{T}_{k,q} \, (k,q = 0, \cdots ,d)$ de la matrice représentant l'endomorphisme $T$ dans la base ci-dessus.

7. b) Même question pour les coefficients de $T^{-1}$ .

8. Écrire les formules donnant les polynômes $X^k$ , $k = 0, \cdots ,d$ , en fonction des polynômes $N_k$ .
[On pourra utiliser la formule de la question 3. a)].

Troisième partie

Étant donné deux entiers $k$ et $n > 0$ , on désigne par :

$A_{k,n}$ l'ensemble des applications de $\lbrace 1, \cdots ,k\rbrace$ dans $\lbrace 1, \cdots ,n \rbrace$ ;

$B_{k,n}$ l'ensemble des applications surjectives de $\lbrace 1, \cdots ,k \rbrace$ dans $\lbrace 1, \cdots ,n \rbrace$ , ensemble bien entendu vide si $k < n$ ;

$C_{k,n}$ l'ensemble des applications $f : \lbrace 1, \cdots , n \rbrace \to \mathbb{N}$ satisfaisant $f(1) + \cdots + f(n) = k$ ;

$D_{k,n}$ le sous-ensemble du précédent formé des $f$ telles que $f(i) \ge 1$ pour tout $i$ (ici, $n \leq k$ ).

9. Démontrer la " formule du multinôme ", pour $n > 0$ et $k \geq 0$ : $(x_1 + \cdots + x_n)^k = \displaystyle \sum_{f \in C_{k,n}} \dfrac{k!}{f(1)! \cdots f(n)!} x_1^{f(1)} \cdots x_n^{f(n)}$ ,
où $x_1 \cdots, x_n$ sont des nombres réels.
[On pourra procéder par récurrence sur $n$ ].

10. Montrer que $(x_1 + \cdots + x_n)^k = \displaystyle \sum_{\varphi \in A_{k,n}} x_{\varphi(1)} \cdots x_{\varphi(k)}$ .

11. Montrer que, pour $0 < n \leq k$ , on a : $s_{k,n} = \displaystyle \sum_{f \in D_{k,n}} \dfrac{k!}{f(1)! \cdots f(n)!}$ .

Quatrième partie

On considère une série entière à coefficients réels $\displaystyle \sum_{k \geq 0} a_k x^k$ ; on suppose $a_0 = 0$ ; on note $R_1$ son rayon de convergence supposé non nul, et $\varphi(x)$ sa somme. Pour $n$ et $k$ entiers $\geq 0$ , on pose $\alpha_{k,n} = \left \lbrace \begin{array}{cl} \displaystyle \sum_{f \in D_{k,n}} a_{f(1)} \cdots a_{f(n)} & \text{ si } 0 < n \leq k \\ 0 & \text{ si } 0 \leq k < n \\ \end{array} \right. \\ \alpha_{0,k} = \left \lbrace \begin{array}{ccc} 1 & \text{ si } & k = 0 \\ 0 & \text{ si } & k > 0\\ \end{array} \right.$

12. Indiquer un minorant $\rho > 0$ du rayon de convergence de la série entière $\displaystyle \sum_{k \geq 0} \alpha_{n,k}x^k$ où $n \geq 0$ ; déterminer la somme de cette série dans l'intervalle $|x| < \rho$ .

On considère une seconde série entière $\displaystyle \sum_{n\ge 0}b_nx^n$ ; on note $R_2$ son rayon de convergence supposé non nul, et $psi(x)$ sa somme.

13. Montrer que la série entière $\displaystyle \sum_{k\geq 0} \left(\displaystyle \sum_{n\geq 0} b_n \alpha_{n,k} \right) x^k$ a un rayon de convergence non nul, et préciser sa somme au voisinage de 0.

14. On considère la fonction $\theta(x) = e^{(e^x - 1)}$ . Exprimer les coefficients de la série de Taylor de $\theta$ à l'aide des nombres $s_{k,n}$ .

Merci à puisea

pour avoir contribué à l'élaboration de cette fiche

Cette fiche

Télécharger (660 ko)
Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Forum de maths

concours en post-bac
Plus de 329 topics de mathématiques sur "concours" en post-bac sur le forum.