Prueba de que los coeficientes binomiales son enteros - interpretación combinatoria

Question

Para cualquier enteros $k \le n$ aquí es inyectiva grupo homomorphism $$S_k \times S_{n-k} \rightarrow S_n$$ such that a tuple $(\sigma, \tau)$ permutes $\{1,...,n\}$ by letting $\sigma$ act on $\{1,...,k\}$ and $\tau$ act on $\{k+1,...,n\}$.

Por Lagrange del teorema, $k!(n-k)! = |S_k \times S_{n-k}|$ divide $|S_n| = n!$, lo $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ es un número entero.

En los comentarios de algunos pregunta desde hace varios meses (que no puedo encontrar ahora) se preguntó si podemos encontrar una combinatoria interpretación de este resultado - que los cosets de $S_k \times S_{n-k}$ $S_n$ debe corresponder naturalmente a las formas de elección de $k$ elementos de un conjunto de $n$.

Para mí no existe una clara correspondencia y me gustaría saber si alguien tiene una interpretación en ese sentido.

Answer 1

Sea $X$ el conjunto de subconjuntos de elemento de $k$ ${1, \ldots, n}$. $S_n$ actúa en $X$ (aplicar una permutación a $k$ distintos números resultado otra $k$ números distintos) y debe quedar claro que esta acción es transitiva. Así la relación de estabilizador de órbita dice que para cualquier opción $x \in X$ allí es un natural bijection $X \simeq S_n/\operatorname{Stab}(x)$ $\operatorname{Stab}(x)$ dónde están las permutaciones en $S_n$ $x$ que.

Si nosotros no $x = {1, \ldots, k} \in X$ $\operatorname{Stab}(x) = Sk \times S{n - k}$ por lo tanto el $X \simeq S_n/(Sk \times S{n - k})$.