[<] Dénombrements avancés [>] Démonstrations combinatoires

 
Exercice 1  3961  

(Calcul par anagramme)

Soient p, q et n des entiers naturels.

  • (a)

    Un mot est constitué de p fois le caractère A et q fois le caractère B. Combien peut-on constituer d’anagrammes de ce mot?

  • (b)

    On suppose p1. En considérant les symboles «  1   » et «  +   », combien existe-t-il de familles (x1,,xp)p vérifiant x1++xp=n ?

 
Exercice 2  3960   Correction  
  • (a)

    Combien existe-t-il de suites strictement croissante de p entiers choisis dans {1,,n}?

  • (b)

    Application: Combien existe-t-il de suite (x1,,xp) avec

    x1++xpn et x1,,xp*.
  • (c)

    Même question avec

    x1++xp=n et x1,,xp*.

Solution

  • (a)

    Une suite strictement croissante de p entiers dans {1,,n} est entièrement déterminée par le choix de ses éléments qu’il suffit alors d’ordonner. Il y en a donc

    (np).
  • (b)

    À chaque suite (x1,,xp) vérifiant x1++xpn et x1,,xp* on peut associer une suite strictement croissante (y1,,yp) d’éléments de {1,,n} en posant

    yk=x1++xk.

    Inversement, à une suite (y1,,yp) comme au dessus correspond une unique suite (x1,,xp) comme voulue avec

    x1=y1,xk=yk-yk-1 pour k2.

    Il y a donc autant de suites (x1,,xp) vérifiant x1++xpn et x1,,xp* que de suite strictement croissantes de p éléments dans {1,,n}, soit

    (np).
  • (c)

    La condition x1++xp=n est remplie quand x1++xpn mais pas x1++xpn-1. Le nombre de suite cherché est donc

    (np)-(n-1p)=(n-1p-1).
 
Exercice 3  3930   

(Calcul par les familles croissantes)

Soient n et p*.

Il existe 11 1 Voir le sujet 4437 où l’on a simplement opéré un glissement sur l’ensemble des valeurs en considérant 0;n au lieu de 1;n+1. (n+pp) familles croissantes de longueur p constituées d’éléments de 0;n.

  • (a)

    Combien existe-t-il de familles (x1,,xp)p vérifiant x1++xpn?

  • (b)

    Même question avec la condition x1++xp=n.

 
Exercice 4  1535   

(Calcul par récurrence)

Soient n et p*. On note Cnp le nombre de familles (x1,,xp)p vérifiant la condition x1++xp=n.

  • (a)

    Établir

    Cnp+1=k=0nCkp.
  • (b)

    En déduire

    Cnp=(n+p-1n).

[<] Dénombrements avancés [>] Démonstrations combinatoires



Édité le 08-11-2019

Bootstrap Bootstrap 3 - LaTeXML [LOGO] - Powered by MathJax Powered by MathJax