Aller au contenu

Combinatoire/Exercices/Combinaisons

Leçons de niveau 13
Une page de Wikiversité, la communauté pédagogique libre.
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.



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.

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

.

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.)

  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.

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

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

Pour , on note le nombre de surjections de dans .

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

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 » : .

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 ).