Preuve du nombre de combinaisons

Ce que tu as écrit n'a pas grand sens.
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.

Tu fixes une partie $A$ de cardinal $k$ et tu l'écris $A=\{x_1,\dots,x_k\}$. Tu peux le faire chez toi mais si je le fais de mon côté, nous n'obtiendrons certainement pas la même numérotation (moi, je vais numéroter les nombres pairs par ordre décroissant et intercaler les impairs rangés par ordre lexicographique de leur nom en finnois ; c'est l'occasion de revoir la numération en finnois).

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.

Si, comme l'a écrit un_kiwi, « le but est de montrer que $\binom{n}k=\frac{n!}{k!(n-k)!}$ », je préfère une surjection de $E$ sur $F$ à la bijection proposée. Bien sûr, cette surjection ne donne pas une bijection entre $E$ et $\mathfrak{S}_k\times F$ et je ne sais pas en faire une sans faire de choix.

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.

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,\ldots,k\}\to A$)

Il est bien sûr que ceci n'est pas du tout la même chose, et beaucoup plus naturel, que d'énumérer $A$ dans l'ordre croissant ! (:D

on obtient moins qu'une bijection entre $\mathfrak S_k\times F$ et $E$

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 ?