Exo Maths X MP #41 - Dénombrement des fonctions aux itérés s'annulant

Publié

Révisé

December 31, 2020

Il y a 4 années

Exercice d'oral de maths de Polytechnique filière MP tombé en 2020.

Dénombrer les fonctions $f$ de $[[1, n]]$ dans $[[0, n]]$ telles que :

\forall k \in [[1, n]], \exists k^{'} \in N, f^{\circ k^{'}} (k) = 0

où $f^{\circ k^{'}}$ désigne $f$ composée $k^{'}$ fois avec elle-même.

Merci à Arthur Dremeaux d'avoir partagé l'exercice qu'il a eu à l'oral de l'X ! Pour partager les tiens, contacte Lucas Willems.

Correction

Bravo à Othmane Hadi (MP, Al-Khansaa) d'avoir réussi à résoudre cet exercice et merci à lui d'avoir rédigé une correction !

Rejoins le groupe Facebook Exos Maths X MP pour te préparer à l'X.

Plaçons nous dans un cadre plus général. Si $E$ et $F$ sont deux ensembles disjoints de cardinal $n, m \in N$ , on note :

A (E, F) t (n, m) = {f : E \to E \cup F ∣ \forall x \in E, \exists i \geq 0, f^{i} (x) \in F} = Card (A (E, F))

Soit $f \in A (E, F)$ . Si $x \in f^{- 1} (F)$ , alors $f (x) \in F$ . Si $x \in E \ f^{- 1} (F)$ , alors $\exists i \geq 0, f^{i} (x) \in F$ équivaut à $\exists j \geq 0, f^{j} (x) \in f^{- 1} (F)$ . Ainsi :

f \in A (E, F) ⟺ f_{∣ E \ f^{- 1} (F)} \in A (E \ f^{- 1} (F), f^{- 1} (F))

Pour dénombrer $A (E, F)$ , il suffit donc de faire une disjonction de cas sur le cardinal de $f^{- 1} (F)$ :

Il n'y a aucune application $f \in A (E, F)$ telle que $Card (f^{- 1} (F)) = 0$ i.e. $f^{- 1} (F) = \emptyset$ .
Il y a $m^{n}$ applications $f \in A (E, F)$ telles que $Card (f^{- 1} (F)) = n$ i.e. $f^{- 1} (F) = E$ .
Soit $k \in [[1, n - 1]]$ . Il y a $(k n) m^{k}$ applications $f : E \to F$ telles que $Card (f^{- 1} (F)) = k$ . Il y a donc $(k n) m^{k} t (n - k, k)$ applications $f \in A (E, F)$ telles que $Card (f^{- 1} (F)) = k$ .

Ainsi :

t (n, m) = m^{n} + k = 1 \sum n - 1 (k n) m^{k} t (n - k, k)

Montrons par récurrence forte sur $l = m + n$ que :

\forall n, m \in N^{*}, t (n, m) = m (m + n)^{n - 1}

Initialisation : $l = 2$ . $n = m = 1$ . Soit $E = {1}$ et $F = {2}$ . Il y a une seule application $f \in A (E, F)$ , celle qui envoie $1$ sur $2$ . Or, $1 (1 + 1)^{0} = 1$ .

Hérédité. Supposons que $t (n, m) = m (m + n)^{n - 1}$ pour tout $n, m \in N^{*}$ tels que $n + m \leq l$ . Soit $n, m \in N^{*}$ tels que $n + m = l + 1$ .

Pour tout $k \in [[1, n - 1]]$ , $n - k + k = n < n + m$ . Donc par hypothèse de récurrence :

t (n, m) = m^{n} + k = 1 \sum n - 1 (k n) m^{k} k n^{n - k - 1}

Comme $k (k n) = n (k - 1 n - 1)$ :

t (n, m) = m^{n} + k = 1 \sum n - 1 (k - 1 n - 1) n^{n - k} m^{k} = m [m^{n - 1} + k = 1 \sum n - 1 (k - 1 n - 1) n^{(n - 1) - (k - 1)} m^{k - 1}] = m [k = 1 \sum n (k - 1 n - 1) n^{(n - 1) - (k - 1)} m^{k - 1}] = m (m + n)^{n - 1}

Conclusion. Nous avons donc bien :

\forall n, m \in N^{*}, t (n, m) = m (m + n)^{n - 1}

Ainsi, $t (n, 1) = (1 + n)^{n - 1}$ .

Exos Maths X MP

Prépare-toi aux oraux de maths de Polytechnique filière MP en résolvant les exercices tombés les années précédentes.