Dénombrement

mpsi_quatre
mpsi_quatre
dans Combinatoire et Graphes
Bonjour

J'ai beaucoup de mal avec les démonstrations par combinatoire.

Pour les exemples ci-dessous, je ne sais même pas par où commencer pour le 1...

Comment faut-il rédiger ce genre de question?68400

Réponses

  • GaBuZoMeu
    GaBuZoMeu
    Pour 1 : les sommes partielles $k_1$, $k_1+k_2$, ..., $k_1+k_2+\cdots+k_{p-1}$ forment une partie à $p-1$ éléments de $\{1,\ldots,n-1\}$. Réciproquement, étant donné une partie à $p-1$ éléments de $\{1,\ldots,n-1\}$ ...
  • mpsi_quatre
    mpsi_quatre
    C'est fait exprès de s'arrêter à $k_{p-1}$ et pas $k_p$?
  • Poirot
    Poirot
    Oui, car une fois que tu disposes de $k_1, \dots, k_{p-1}$ la valeur de $k_p$ est imposée par la condition $k_1 + \dots + k_p = n$.
  • mpsi_quatre
    mpsi_quatre
    Ok, je vois que (*) $\{k_1,\dots,k_1+\dots+k_{p-1}\}\in\mathcal P_{p-1}(n-1)$ (dans le cours on note $\mathcal P_k(n)$ les parties de $[|1,n|]$ à $k$ éléments).

    Réciproquement, soit $A=\{a_1,\dots,a_{p-1}\}\in\mathcal P_{p-1}(n-1)$
    Que souhaite on faire ? Ecrire $A$ sous forme de (*)?
  • GaBuZoMeu
    GaBuZoMeu
    Pour commencer si tu indexes, par $1,\ldots,p$ les éléments d'une partie à $p-1$ éléments, tu es mal parti !
    La recette est simple : établir une bijection entre deux ensembles (celui que l'on veut dénombrer, et un autre que l'on sait déjà dénombrer). Cette recette vaut aussi pour les questions 2, 3 et 4.
  • mpsi_quatre
    mpsi_quatre
    J'ai modifié la coquille d'indexation mais je ne vois pas quelle application explicite (avec ensemble de départ d'arrivée et formule) je dois vérifier qu'elle est bijective. Pourrais-je avoir l'application pour le 1? J'imagine que ça a un lien avec la somme $k_1+k_2+\cdots+k_{p-1}$ mais je ne trouve pas l'expression entière de l'application
  • GaBuZoMeu
    GaBuZoMeu
    je ne vois pas quelle application explicite (avec ensemble de départ d'arrivée et formule) je dois vérifier qu'elle est bijective.
    À croire que tu n'as pas lu mon message.
  • mpsi_quatre
    mpsi_quatre
    Si mais comme il n'y a pas d'application explicite j'ai du mal l’interprété car j'ai essayé de considerer l'application qui va de $\mathcal P_{p-1}(n-1)$ dans $\mathcal P_{p-1}(n-1)$ et qui à $\{k_1,...,k_{p-1}\}$ donne $\{k_1,...,k_1+...+k_{p-1}\}$
  • GaBuZoMeu
    GaBuZoMeu
    M'enfin, réfléchis un peu !
    Qu'est-ce qu'on veut compter ? Le nombre de $p$ listes $(k_1,\ldots,k_p)$ d'entiers strictement positifs tels que $k_1+k_2+\cdots+k_p=n$.
    Dans mon premier message, je dis explicitement comment associer à une telle liste une partie à $p-1$ éléments de l'ensemble $\{1,\ldots,n-1\}$. Et j'ajoute "Réciproquement, étant donné une partie à $p-1$ éléments de $\{1,\ldots,n-1\}$ ... " !
    Je m'en voulais un petit peu d'avoir complètement spoilé la question 1) ...

    PS. Et dans mon message suivant, j'avais indiqué :
    "La recette est simple : établir une bijection entre deux ensembles (celui que l'on veut dénombrer, et un autre que l'on sait déjà dénombrer)."
  • Chaurien
    Chaurien
    Désolé mais je vais remettre en cause l'énoncé, ce qui est mal vu de certains, mais bon.

    Je commencerai par la question 3. Étant donnée une $p$-partie de $\{1,2,...,n \}$, il y a une seule manière de disposer ses éléments selon une liste (suite) strictement croissante. Le nombre de $p$-listes (ou $p$-suites) strictement croissantes de $\{1,2,...,n \}$ est donc exactement le nombre de $p$-parties de $\{1,2,...,n \}$, c'est tout simplement .$(_{p}^{n})$. C'est pour moi un fait de base, d'une évidence frappante, qu'il est extrêmement maladroit de prétendre prouver par on ne sait quel détour.

    Ensuite la question 4. Toute $p$-suite croissante (au sens large) $(x_1,x_2,...,x_p)$ de $\{1,2,...,n \}$ peut être « étirée » en une suite strictement croissante $(y_1,y_2,...,y_p)$ de $\{1,2,...,n+p-1 \}$ en faisant : $y_i:=x_i+i-1$, d'où immédiatement le nombre de ces suites.

    En regardant les différences, on peut ensuite traiter les questions 1 et 2.

    Bonne journée,
    Fr. Ch.

    NB. Quelqu'un sait-il faire les crochets ajourés en LaTeX ?

    [small]C'étaient mémorables festins
    C'étaient délectables nuits blanches
    Je priais que mon cœur ne flanche
    A l'été de la Saint Martin[/small]
  • Rescassol
    Rescassol
    Bonjour,

    Comme ça $[\![crochet]\!]$ ?

    Cordialement,

    Rescassol
  • Chaurien
    Chaurien
    Merci Rescassol pour ces beaux crochets ajourés.
    Fr. Ch.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

Lirone93 +2 Invités