Comentario: voy a esbozar una manera de pensar acerca de la ecuación en cuestión y una manera de demostrar lo que posiblemente va a arrojar un poco de perspicacia. La inducción no es el mejor o el más eficiente método de prueba aquí, pero es poco interesante que $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ puede ser demostrado mediante la inducción donde Pascal Regla se aplica en realidad al final de la prueba, y la prueba también se da la justificación para la combinatoria de la terminología "$n$ elija $k$", representado por $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.
Patrones:
-
Lema 1: Un conjunto con $n$ elementos de ha $n$ subconjuntos que contiene exactamente un elemento siempre $n\geq 1, n\in\mathbb{Z}$.
-
Lema 2: Un conjunto con $n$ elementos de ha $n(n-1)/2$ subconjuntos que contienen exactamente dos elementos siempre $n\geq 2, n\in\mathbb{Z}$.
-
Lema 3: Un conjunto con $n$ elementos de ha $n(n-1)(n-2)/6$ subconjuntos que contienen exactamente tres elementos siempre $n\geq 3, n\in\mathbb{Z}$.
Los tres lemas que pueda ser demostrado con bastante facilidad el uso de la inducción. Es interesante observar el patrón que emerge en los Lemas 1-3. Parece que podemos hacer una conjetura en cuanto a lo del número de $k$-elemento subconjuntos será por un conjunto de con $n$ elementos.
Teorema: Un conjunto con $n$ elementos
$$
\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}
$$
los subconjuntos que contienen exactamente $k$ elementos siempre $0\leq k\leq n$, e $n,k\in\mathbb{Z}$.
Prueba. Al $n=0$, la única opción posible para $k$$k=0$, y cuando $n=k=0$, $\binom{0}{0} = 1$. Esto es cierto debido a que el número de cero-elemento se establece en cero element set es 1 (i.\,e., $\emptyset \subseteq \emptyset$). Los lemas 1-3 satisfacer a los casos al $n=1,2,3$, respectivamente. La prueba procede por inducción en $n$ de la declaración de $P(n):$ Hay $\binom{n}{k}$ diferentes $k$-elemento de los conjuntos de un conjunto de con $n$ elementos para cada $k$ satisfacción $0 \leq k \leq n$.
Suponga $P(\ell)$ es cierto para algunos $\ell \geq 3, \ell \in \mathbb{Z}$, y deje $M$ ser un conjunto con $\ell+1$ elementos. Para mostrar que $P(\ell) \rightarrow P(\ell+1)$, debemos mostrar que el número de $k$-elemento pone en $M$ $\binom{\ell+1}{k}$ por cada $k$ satisfacción $0 \leq k \leq \ell+1$. Al $k=0, \binom{\ell+1}{0}=1$, y al $k=\ell+1, \binom{\ell+1}{\ell+1} = 1$. Deje $k$ satisfacer $1 \leq k \leq \ell$, y corregir algunas $\alpha \in M$. El número de $k$-elemento pone en $M$ que contiene $\alpha$ es el número de conjuntos con $k-1$ elementos en $M \setminus \{ \alpha \}$; desde $\left\vert{M \setminus \{ \alpha \}}\right\vert = \ell$, $\binom{\ell}{k-1}$ estos conjuntos por la hipótesis inductiva. El número de conjuntos de con $k-1$ elementos que no contengan $\alpha$$\binom{\ell}{k}$, también por la hipótesis inductiva. El uso de Pascal de la Identidad, el número de $k$-elemento pone en $M$$\binom{\ell}{k-1}+\binom{\ell}{k} = \binom{\ell+1}{k}$.
Por lo tanto, la declaración de $P(n)$ es cierto para todos los $n \geq 0, n \in \mathbb{Z}$, y el Teorema es por inducción. $\blacksquare$
Añadido: La notación $\binom{n}{k}$ a veces es introducido en la combinatoria por primera introducción del símbolo de Pochhammer, $n^{\underline{k}}$. Una explicación del Teorema anterior con más de combinatoria sabor (ya que tu pregunta está etiquetada combinatorics) puede brevemente proceder de la siguiente manera: Vamos a $A=\{1,2,\ldots,n\}$. Para $k\leq n$, la inyección de $\{1,2,\ldots,k\}\to A$ $k$- elemento de permutación. El número de $k$-elemento de permutaciones de un conjunto de tamaño $n$ está dado por
$$
n^{\underline{k}}=\prod_{i=0}^{k-1}(n-i)=n(n-1)(n-2)\cdot(n-k+1)=\frac{n!}{(n-k)!}.
$$
Desde $\binom{n}{k}$ es, por definición, el número de $k$-elemento de subconjuntos de tamaño $n$ e hay $k!$ maneras de ordenar un conjunto de tamaño $k$, sabemos que $n^{\underline{k}}=\binom{n}{k}\cdot k!$, y esto implica que $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.
