5.1 Introduction et les 8 cas triviaux

Dans ce chapitre, nous sommes intéressés à résoudre les problèmes d’occupation. De manière générale, le problème s’énonce comme suit:

Combien y a-t-il de façon de placer $\displaystyle k$ boules dans des urnes ?

Les problèmes d’occupation consistent donc à déterminer le nombre de façons de placer $\displaystyle k$ boules dans des urnes. Nous parlons des problèmes d’occupation au pluriel, car il s’agit en fait d’un ensemble de $\displaystyle 30$ problèmes tournant autour de la même question. Ceci est du au fait que, comme pour les problèmes de choix d’objets, la question de placer des boules dans des urnes peut être interprétée de différentes façons, et de plus, certaines contraintes peuvent être ajoutées. Dans un certain sens, les problèmes d’occupation généralisent le problème de choisir des objets, mais en même temps, ils les traitent de manière différente. Les problèmes d’occupation incluent aussi la question de compter des fonctions ayant certaines propriétés, comme l’injectivité ou la surjectivité.

Dans les problèmes d’occupation, nous sommes donc amené à nous poser les questions suivantes:

1. 1.
   ​

   Les boules sont-elles différentes ou identiques ?

2. 2.
   ​

   Les urnes sont-elles différentes ou identiques ?

3. 3.
   ​

   Le nombre d’urne est-il fixé ou non ?

4. 4.
   ​

   Les urnes peuvent-elles contenir un nombre quelconque de boule ou bien doivent-elles en contenir au moins une, au plus une ou exactement une ?

5. 5.
   ​

   Est-ce que l’ordre des boules dans les urnes est importante ?

Chacune de ces questions a deux options, sauf pour la quatrième, qui en a quatre. On a donc en théorie un total de $\displaystyle 2^{4}\times 4=64$ problèmes. En réalité, heureusement, ce nombre est largement réduit en remarquant que plusieurs combinaisons de réponses n’ont pas de sens. Par exemple, la question de l’ordre des boules dans les urnes n’a de sens que si les boules sont différentes et que les urnes peuvent potentiellement contenir plus d’une boule. Aussi, le cas où le nombre d’urnes n’est pas fixé n’a de sens que si les urnes doivent contenir au moins un élément ou exactement un élément ; autrement, il y aurait une infinité de possibilités. En excluant ces cas qui ne font pas de sens, on est donc ramené à un total de $\displaystyle 30$ cas.

Une autre bonne nouvelle est que parmi ces $\displaystyle 30$ cas, certains sont complètement triviaux. Il y en a $\displaystyle 8$ qui entrent dans cette catégorie.

Trois problèmes ont toujours une seule option. Il s’agit des problèmes suivants:

1. 1.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans des urnes identiques si chaque urne doit contenir exactement une boule ?

2. 2.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules identiques dans des urnes distinctes si chaque urne doit contenir exactement une boule ?

3. 3.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules identiques dans des urnes identiques si chaque urne doit contenir exactement une boule ?

Trois autres problèmes ont exactement une option si $\displaystyle k=n$ et n’en ont aucune autrement. Il s’agit des problèmes suivants:

1. 1.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques si chaque urne doit contenir exactement une boule ?

2. 2.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules identiques dans $\displaystyle n$ urnes différentes si chaque urne doit contenir exactement une boule ?

3. 3.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules identiques dans $\displaystyle n$ urnes identiques si chaque urne doit contenir exactement une boule ?

Finalement, deux problèmes ont une option si $\displaystyle k\leq n$ et n’en ont aucune autrement. Il s’agit des deux problèmes suivants:

1. 1.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules différentes dans $\displaystyle n$ urnes identiques si chaque urne doit contenir au plus une boule ?

2. 2.
   ​

   Combien y a-t-il de façons de placer $\displaystyle k$ boules identiques dans $\displaystyle n$ urnes identiques si chaque urne doit contenir au plus une boule ?

Il nous reste donc un total de $\displaystyle 22$ problèmes qui sont plus intéressants et varient en niveau de difficulté. Nous allons les étudier plus en détail dans les sections qui suivent.