Combinatoire/Exercices/Combinaisons

Combinaisons
Image logo représentative de la faculté
Exercices no4
Leçon : Combinatoire
Chapitre du cours : Combinaisons sans répétition et Combinaisons avec répétition

Exercices de niveau 13.

Exo préc. :Permutations
Exo suiv. :Sommaire
En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Combinaisons
Combinatoire/Exercices/Combinaisons
 », n'a pu être restituée correctement ci-dessus.



Exercice 4-1

modifier

Soient  . Montrer les propriétés suivantes de deux façons : par le calcul et par un raisonnement combinatoire.

a)     ;

b)     et plus généralement,   (identité de Vandermonde) ;

c)     puis   ;

d)     ;

e)   si  ,  .

Déduire de l'égalité d) ci-dessus que  , pour tout   entier ou même complexe.

Exercice 4-2

modifier

Grâce à la question a) de l'exercice précédent, calculer :

 .

Exercice 4-3

modifier

De combien de manières peut-on distribuer   pièces de 1 euro :

  1. à   enfants de sorte que chaque enfant ait au moins un euro ?
  2. à   enfants ? (à présent, un enfant peut ne rien recevoir).
  3. à   filles et   garçons de sorte que chaque fille ait au moins un euro ?
  4. à   filles et   garçons de sorte que chaque fille ait au moins   euros et chaque garçon au moins   euros ?
  5. à   filles et   garçons de sorte que chaque fille ait exactement   euros ?

(Dans chaque cas, on suppose qu'il y a au moins un enfant.)

Exercice 4-4

modifier
  1. Une urne contient   boules distinctes et l'on veut sélectionner   boules. Cette sélection peut se faire de quatre manières différentes (avec ou sans remise de la boule qui vient d'être tirée, en tenant compte ou non de l'ordre dans lequel les   boules ont été sélectionnées). Compléter le tableau suivant en indiquant dans chaque cas le nombre de sélections possibles.
     
  2. Soient   et  . On considère les ensembles :
      ;
      ;
     .
    Vérifier que  ,  ,   et   remplissent les cases du tableau de la question 1.

Exercice 4-5

modifier

Soient  . Combien existe-t-il de  -uplets   tels que   ?

Exercice 4-6

modifier

Soient  . Combien existe-t-il de  -uplets   de somme   tels que   ?

Exercice 4-7

modifier

Pour  , on note   le nombre de surjections de   dans  .

  1. Démontrer que  .
  2. En déduire que  .

Exercice 4-8

modifier

On note   le nombre de Stirling de seconde espèce, égal au nombre de partitions de   en   parties.

  1. Démontrer que   est lié au nombre   de surjections de l'exercice précédent par :  .
  2. En déduire une formule explicite pour  , ainsi qu'une relation de récurrence.
  3. Redémontrer directement cette relation de récurrence.
  4. En utilisant cette relation, démontrer que
     ,
      désigne le polynôme « factorielle décroissante » :  .

Exercice 4-9

modifier

On avance sur la droite réelle, dans le sens positif, en partant de  . Pour tout entier  , on note   le nombre de façons d'effectuer un trajet de longueur   en faisant uniquement des pas de longueur   ou  . Les deux questions suivantes sont indépendantes.

  1. Démontrer que   est égal au  -ième nombre de Fibonacci  , défini par
     .
  2. Exprimer   comme une somme de coefficients binomiaux, en comptant le nombre   de façons d'effectuer un trajet de longueur   avec k pas de longueur   (et les autres de longueur  ).