Dénombrement.

Salut à tous !

Enoncé : On considère un protocole informatique qui distribue chaque tâche reçue au hasard vers un des $n$ processeurs d'un ordinateur.
Déterminer en fonction du nombre $k$ de tâches reçues, la probabilité que tous les processeurs aient à exécuter au moins une tâche.

Ma solution :
- Modélisation : On regarde la décomposition de l'entier $k$ en somme de nombre compris entre $0$ et $k$.
On va regarder combien de possibilités totales il y a. Ce problème est équivalent à remplir $n$ boîtes avec $k$ boules.
On dessine les boules
_ _ _ _ _ _ _
Et on dit que les boîtes sont crées par séparations,
|_ _ _ | _ _
Ici trois boîtes : la 1ère ne contient rien, la deuxième 3 boules, la troisième 2 boules.
Ce qui nous donne $C_{n+k}^{n}$ possibilités.

Ensuite déterminons le nombre de décompositions sans $0$.
Déjà il est nécessaire que $k \ge n$.
Ensuite, il s'agit de mettre 1 bâton dans chaque boîte puis les $k-n$ restant dans les $n$ boîtes.
En reprenant la formule ci-dessus cela donne $C_{k}^{n}$ possibilités.

- Résolution : $P$ uniforme sur l'univers de la décomposition.
$P(A) = C_{k}^{n}/C_{n+k}^{n}$

Qu'en dites-vous ?

Réponses

  • Bonjour,
    Ton résultat est inexact: il est en effet facile de se convaincre que si $n=1$, alors $\Pr (A)= 1$, ce qui est différent de $\dfrac{k}{k+1}$.
    En notant $\forall i \in [n]:=\{1,2,...n\},\: A_i$ l'événement $\text{"le processeur}\: i \text{ a recu au moins une tâche"}$, il vient avec la "formule du crible":
    $\Pr (A)=\Pr \left(\displaystyle{\bigcap_{i=1}^n A_i}\right) =1- \Pr \left(\displaystyle{\bigcup_{i=1}^n \overline {A_i}}\right)$ $=\displaystyle{ \sum_{I \subset [n]} (-1)^{\#I}\Pr \left(\bigcap _{s \in I}\overline{ A_s }\right)}= \displaystyle{ \sum _{i=0}^n\binom ni (-1)^i \left(1-\dfrac in \right)^k}= \dfrac{\displaystyle{\sum_{i=0}^n (-1)^{n-i} \binom ni i^k}}{n^k}$
    Le numérateur de la fraction ainsi obtenue est le nombre de surjections d'un ensemble de cardinal $k$ sur un ensemble de cardinal $n$; Il est aussi égal à $ n! \mathcal S(k,n)$ où $\mathcal S(k,n)$ désigne le $\text{"nombre de Stirling de deuxième espèce"}$ apparaissant ligne $k$, colonne $n$ du tableau triangulaire infini dont les huit premières lignes (numérotées de $0$ à $7$) sont:
    $$\begin {array} {cccccccc} 1\\0&1\\0&1&1\\0&1&3&1\\0&1&7&6&1\\0&1&15&25&10&1\\0&1&31&90&65&15&1\\0&1&63&301&350&140&21&1\\ \end{array} \:\: \text{avec: } \boxed{\:\mathcal S(k,n) = n\mathcal S(k-1,n) + \mathcal S(k-1,n-1)} $$
  • Pas mal, merci.
Connectez-vous ou Inscrivez-vous pour répondre.