Fiche de mathématiques
> >

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

Partager :
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)},

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)},

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^kn \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}.
Publié le
ceci n'est qu'un extrait
Pour visualiser la totalité des cours vous devez vous inscrire / connecter (GRATUIT)
Inscription Gratuite se connecter
Merci à
puisea Posteur d'énigmes
pour avoir contribué à l'élaboration de cette fiche


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1291 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !