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

jippy13

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} .$

gerard0

Bonjour.

$a_p$ n'est pas défini.

Qu'est-ce qui justifie la fin de l'avant-dernière ligne ?

Cordialement.

jippy13

$ {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.

Rescassol

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

lourrran

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.

Médiat_Suprème

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)

gerard0

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.

jippy13

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

Médiat_Suprème

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

gebrane

Bonjour0
Veux-tu nous rappeler cette preuve que tu cites par récurrence . Merci

gerard0

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.

gebrane

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)=(n−p+1)*I(p,n−1).

gerard0

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.

jippy13

@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".

JLapin

gebrane a dit :

On montre par récurrence que I(p,n)=(n−p+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)$.

jippy13

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