Preuve du nombre de combinaisons
Bonjour/bonsoir
J'aurais besoin d'aide pour exhiber des bijections.
Soient $n$ et $k$ deux entiers tels que $0\le k \le n$ ; j'ai deux ensembles $E$ et $F$ respectivement définis par $E := \{ (x_1,\ldots ,x_k) \in \{1,\ldots ,n\}^k\mid \forall i,j\in \{1,\ldots ,k\},\ x_i \ne x_j \}$ et $F := \{ A \subset \{ 1,\ldots ,n\}\mid |A|= k\}$. Le but est de montrer que $\dbinom k n = \dfrac{n!}{ k!(n-k)!}$ en exhibant :
1. une bijection entre $E$ et $\mathfrak{S}_k \times F$.
2. une bijection entre $F \times \mathfrak{S}_k \times \mathfrak{S}_{n-k}$ et $\mathfrak{S}_n$.
Pour la 1., j'ai pensé à l'application $\varphi : \mathfrak{S}_k \times F \to E$ définie par $\varphi\big( \sigma , \{ x_1,\ldots ,x_k\} \big) = \big( x_{\sigma(1)},\ldots ,x_{\sigma(k)} \big)$, mais je ne suis pas hyper convaincu. Je proposerais comme réciproque l'application $\psi $ donnée par $\psi\big( a_{1},\ldots ,a_k \big) = \big( {\rm Id}, \{ a_{1},\ldots ,a_k \} \big)$.
Je n'ai pas d'idée pour la 2.
Merci d'avance ;-)
J'aurais besoin d'aide pour exhiber des bijections.
Soient $n$ et $k$ deux entiers tels que $0\le k \le n$ ; j'ai deux ensembles $E$ et $F$ respectivement définis par $E := \{ (x_1,\ldots ,x_k) \in \{1,\ldots ,n\}^k\mid \forall i,j\in \{1,\ldots ,k\},\ x_i \ne x_j \}$ et $F := \{ A \subset \{ 1,\ldots ,n\}\mid |A|= k\}$. Le but est de montrer que $\dbinom k n = \dfrac{n!}{ k!(n-k)!}$ en exhibant :
1. une bijection entre $E$ et $\mathfrak{S}_k \times F$.
2. une bijection entre $F \times \mathfrak{S}_k \times \mathfrak{S}_{n-k}$ et $\mathfrak{S}_n$.
Pour la 1., j'ai pensé à l'application $\varphi : \mathfrak{S}_k \times F \to E$ définie par $\varphi\big( \sigma , \{ x_1,\ldots ,x_k\} \big) = \big( x_{\sigma(1)},\ldots ,x_{\sigma(k)} \big)$, mais je ne suis pas hyper convaincu. Je proposerais comme réciproque l'application $\psi $ donnée par $\psi\big( a_{1},\ldots ,a_k \big) = \big( {\rm Id}, \{ a_{1},\ldots ,a_k \} \big)$.
Je n'ai pas d'idée pour la 2.
Merci d'avance ;-)
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Par contre, si on définit $a_1,\ldots,a_k$ par $A=\{a_1,\ldots,a_k\}$ avec $a_1<a_{i+1}$ pour $1\leq i <k$ (autrement dit, on numérote les éléments de $A$ dans l'ordre croissant), alors ça a bien un sens de poser $\varphi(\sigma,A)=(a_{\sigma(1)},\ldots,a_{\sigma(k)})$.
PS. Tu peux utiliser la même idée pour le 2), en considérant $A$ et son complémentaire.
Pourtant, pour définir $\varphi(\sigma,A)=(x_{\sigma(1)},\dots,x_{\sigma(k)}$, il est indispensable de connaître précisément l'application $\{1,\dots,k\}$ pour pouvoir calculer qui est $x_{\sigma(1)}$. Comme tu as laissé un choix au lecteur, tu n'as pas déterminé une application.
Ce que propose GaBuZoMeu (malgré la coquille $a_i<a_{i+1}$ que tu as repérée), c'est une façon de numéroter les éléments de toute partie $A$ qui ne laisse pas de choix au lecteur : comme $A$ hérite de l'ordre naturel sur $\N$, il y a une unique bijection croissante $\{1,\dots,k\}\to A$, $k\mapsto a_k$. L'ambiguïté de la notation $A=\{x_1,\dots,x_k\}$ étant levée, on peut définir $\varphi$ comme tu l'as fait.
NB : Il me semble plus naturel de procéder en sens inverse : à une $k$-liste ordonnée $(x_1,\dots,x_k)$ de $E$, on associe la partie $\{x_1,\dots,x_k\}$ de $F$. Chaque partie a $|\mathfrak{S}_k|$ antécédents, ce qui permet d'appliquer le lemme des bergers. Plus naturel parce que cette application ne repose pas sur le choix d'un ordre sur $\{1,\dots,n\}$ qui n'a pas de rôle dans les cardinaux de $E$ et $F$ GaBuZoMeu a choisi $<$, il aurait pu prendre $>$ : il y a un certain arbitraire là-dedans.
Au fait, comment justifies-tu que "chaque partie a $|\mathfrak S_k|$ antécédents", sauf à cacher sous le tapis cette bijection pas naturelle entre $E$ et $\mathfrak S_k\times F$ ?
L'ensemble $\{1,2,\dots,n\}$ peut être remplacé par n'importe quel ensemble de cardinal $n$. L'application $p:E\to F$, $(x_1,\dots,x_k)\mapsto\{x_1,\dots,x_k\}$ est bien définie sans qu'il soit besoin de définir un ordre sur $E$ (variante de présentation : un élément de $E$ est une application $x:\{1,\dots,k\}\to E$, alors $p(x)=x(\{1,\dots,k\})$). Pour dénombrer les antécédents d'une partie $A$, on choisit un antécédent arbitraire $b$ de $A$ (c'est une bijection $b:\{1,\dots,k\}\to A$) et on vérifie que les autres sont les $b\circ\sigma$ avec $\sigma\in\mathfrak{S}_k$ (en effet, si $p(x)=p(b)$, alors $b^{-1}\circ x$ est une bijection de $\{1,\dots,k\}$ dans lui-même). Pas besoin d'introduire un ordre sur $A$ mais on obtient moins qu'une bijection entre $\mathfrak{S}_k\times F$ et $E$.
Résumé : $\mathfrak{S}_k$ opère (à droite) librement sur $E$ et $F$ s'identifie au quotient $E/\mathfrak{S}_k$.
La bijection $\mathfrak{S}_k\times F\to E$ repose sur la construction d'une section de $p$ : celle que tu construis utilise l'ordre sur l'ensemble de départ. Bien sûr, l'ordre sur $\{1,\dots,n\}$ est naturel, mais le dénombrement parle d'ensembles et pas d'ensembles ordonnés.
Je ne vois toujours pas pourquoi on a besoin de 1) pour avoir ce que @un_kiwi veut démontrer ?
Pour moi 2) suffit.
Ben, comme tu fais ton choix de $b$ pour chaque $A$ (tu veux compter les antécédents pour chaque $A$, n'est-ce pas ?), on obtient bien une bijection entre $\mathfrak S_k\times F$ et $E$, non ?
Soit $X$ un ensemble de cardinal $n$ et soient $f,g:\{1,\dots,k\}\to X$ tel que $f(\{1,\dots,k\})=g(\{1,\dots,k\})$. Il existe une unique permutation $\sigma\in\mathfrak{S}_k$ tel que $f=g\circ\sigma$ : comme $f$ et $g$ sont des injections entre deux ensembles de même cardinal, ce sont des bijections et $\sigma=g^{-1}\circ f$. Ainsi, les fibres de $p:E\to F$ sont les orbites de $\mathfrak{S}_k$, qui agit librement.
En réalité, ceci ne fait guère que repousser la poussière sous le tapis. Pour dénombrer les orbites, j'ai du mal à me passer du choix d'un élément de l'orbite qui donne ipso facto un ordre sur la partie en question. Différences avec « ton » choix : les bijections orbitales $G/G_f\to G\cdot f$ existent dans un cadre plus large et n'utilise pas la nature de $f$ ; plus spécifiquement, je finis par choisir un ordre partie par partie alors que tu choisis un ordre globalement sur $X$.
Surtout, l'application $p:E\to F$ n'exige aucun choix : les choix interviennent seulement dans la preuve et le choix d'un autre antécédent ici ou là n'altère pas l'application $p$. En revanche, la définition d'une bijection $E\simeq\mathfrak{S}_k\times F$ dépend du choix initial de l'ordre.