Une démonstration élégante du nombre d'arrangements de p parmi n ${A}_{n}^{p}$ — Les-mathematiques.net The most powerful custom community solution in the world

Une démonstration élégante du nombre d'arrangements de p parmi n ${A}_{n}^{p}$

Modifié (18 May) dans Combinatoire et Graphes

Amis ou amoureux des maths, 
je voudrais ici vous faire part d'une démonstration que j'ai établie sur le nombre d'arrangements A(n,p) ou bien le nombre d'injections d'un ensemble de p éléments vers un ensemble de n éléments. Je ne l'ai trouvée dans aucune publication. Veuillez me faire part de vos remarques.
Bien à vous

Soit $E$ un ensemble à $p$ éléments et soit $F$ un ensemble à $n$ éléments ($p\leq n$).
$\textbf{Soit $G$ l'ensemble des injections de $E$ dans $F$. } \newline \textbf{Soient } ( \Phi_{1},\Phi_{2} )\in G^{2}  \textbf{ et } a_{p} \in E \newline\textbf{Soit $R$ une relation définie comme suit} \newline \Phi_{1}\ R\ \Phi_{2} \Leftrightarrow \Phi_{1}(a_{p})=\Phi_{2}(a_{p}) \newline \newline R \textbf{ est une relation d'équivalence. On a donc} \newline \textbf{ Card }  \overline{\Phi}_{1} = \textbf{ Card }  \overline{\Phi}_{2}=  {A}_{n-1}^{p-1} \newline R \textbf{ quotiente $G$, et on a donc Card}(G)=n \times \textbf{Card }   \overline{\Phi}_{1}  \newline \textbf{Ainsi Card}(G)= {A}_{n}^{p} = n\times {A}_{n-1}^{p-1}=n(n-1)\cdots {A}_{n-p+1}^{1} .$

Réponses

  • Modifié (17 May)
    Bonjour.
    $a_p$ n'est pas défini.
    Qu'est-ce qui justifie la fin de l'avant-dernière ligne ?
    Cordialement.
  • Modifié (17 May)
    $ {a}_{p}$ est un élément quelconque de $E$, la fin ... $ {A}_{n}^{p} =   n\times {A}_{n-1}^{p-1} =  n\times (n-1)\cdots {A}_{n-p+1}^{1}  $ 

    PS : j'ai pas trouvé le moyen de modifier le post d'origine.
  • Bonjour,

    > PS : j'ai pas trouvé le moyen de modifier le post d'origine

    La roue dentée en haut à droite de ton message.

    Cordialement,
    Rescassol

  • Modifier le post d'origine est une très mauvaise idée. Comment un type qui lit la discussion peut-il s'y retrouver si le souci soulevé par gerard0 a été corrigé ?

    Je ne sais pas si ce que je lis est la version originale, ou la version corrigée, donc je ne cherche plus à suivre.

  • Personnellement, je trouve que si l'idée est bonne, la rédaction est tout sauf élégante, à partir du premier "On a donc" ("donc" pour lequel aucune justification n'est donnée)
    504, c'est trop !
  • Modifié (17 May)
    Il reste toujours une absence de preuve à l'avant dernière ligne.
    Et finalement, ce n'est qu'une réécriture de la traditionnelle preuve par récurrence,
    Cordialement.
    NB. Si tu es lycéen, ou en L1 d'une petite fac, c'est bien d'avoir trouvé ça seul.
  • Modifié (17 May)
    @gerard0 Merci pour les encouragements (je suis un amoureux des maths :) ) .

    @Mediat Il me semble évident que le nombre d'injections f de E dans F , telle que f(a)=b pour a et b fixé est égal au nombre d'injections de E\(a) sur F\(b).
  • Alors pourquoi ne pas le dire ainsi (pour toutes les classes), sans un "donc" fautif, tel qu'on le lit, ce serait vrai pour toutes les relations d'équivalence
    504, c'est trop !
  • Bonjour0
    Veux-tu nous rappeler cette preuve que tu cites par récurrence . Merci
    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Modifié (17 May)
    Ce n'est que l'écriture mathématique de l'idée intuitive : Pour faire un arrangement, il y a d'abord à choisir un premier terme (n choix), puis un deuxième (n-1 choix puisqu'il doit être différent du premier), puis ..
    Je ne vois pas l'intérêt de l'écrire ici. J'en ai vu des versions "injection", si ça t'amuse d'en rédiger une ...
    Cordialement.
  • Modifié (17 May)
    Gebrane n 'a pas de chance avec gerard0.
    Je voulais comprendre seulement  cette phrase  "Et finalement, ce n'est qu'une réécriture de la traditionnelle preuve par récurrence,"

    J'ai pensé que tu as pensé à cette preuve  :  Soient deux ensembles E dans F de cardinaux respectifs p et n avec n≥ p.
     Soit I(n,p) le nombre injections de E dans F. On a : I(n,1)=n
    On montre par récurrence que I(p,n)=(np+1)*I(p,n−1).

    -------------------------------------------------------------------------------------------------------------------------------
    Citation en cours
  • Oui, c'est cela, ou plutôt la récurrence sur n, basée sur l'idée de séparer un élément du nouvel ensemble pour retomber sur des arrangements de n-1 éléments.
  • Modifié (18 May)
    @gebrane Oui, c'est bien cette méthode qui m'avait été enseignée (il y'a longtemps). On considérait les injections ayant les mêmes images sur le ss ensemble $ E \setminus  \{ a_{p}  \} $ (je galère avec Latex).
    De là, on en déduisait la formule de récurrence que tu évoques. En fait, on aurait pu définir une autre relation f R g ssi f et g ont la même image sur la restriction  $ E \setminus  \{ a_{p}  \} $  .

    Mais je ne trouvais pas cette méthode évidente. Mon idée est de faire intervenir une relation d'équivalence pour partitionner I(E,F) l'ensemble des injections de E vers F en des classes de même cardinal. Et cette évaluation me permet d'établir une "formule de récurrence".
  • Modifié (18 May)
    gebrane a dit :
    On montre par récurrence que I(p,n)=(np+1)*I(p,n−1).
    Plus précisément.
    On montre directement (lemme des bergers) une relation de récurrence, par exemple $I(p,n) = n*I(p-1,n-1)$ ou encore $I(p,n) = I(p-1,n) * (n-p+1)$
    puis par récurrence sur $n$ (ou sur $p$) que $I(p,n)=n(n-1)...(n-p+1)$.
  • Modifié (18 May)
    Je connaissais aussi cette démonstration qui selon moi, n'en est pas vraiment une.
    Bâtissons une injection.
    On prend le premier élément de E => on peut lui donner n images possibles
    On prend le deuxième élément de E => on peut lui donner n-1 images possibles
    ..
    On prend le pième élément de E => on peut lui donner n-p+1 images possibles
    Le nombre de possibilités vaut alors n*(n-1)*..(n-p+1).
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!