Prueba de la fórmula del coeficiente binomial.

Question

¿Cómo podemos demostrar que el número de formas de elegir $k$ elementos entre $n$ es $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ con $k\leq n$ ? Esto es un hecho aceptado en todos los libros pero no he podido encontrar una prueba.

Answer 1

Bien, primero hagamos secuencias ( pedido listas de elementos distintos) de longitud $k$ de la $n$ hay un conjunto de elementos. $n$ formas de elegir el primer elemento, $n-1$ formas de elegir el segundo, ..., $n-k+1$ formas de elegir el $k$ elemento. Así que hay $$n(n-1)\cdots (n-k+1) = \frac{n!}{(n-k)!}$$ tales secuencias.

Pero queremos contar desordenado listas, es decir, para cada secuencia, queremos identificar el $k!$ permutaciones de sus elementos (cada uno de los cuales se ha contado por separado anteriormente) como la misma lista. Por lo tanto, el número de listas desordenadas es $$\frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{k!(n-k)!}.$$

Answer 2

Obsérvese que dado $n$ objetos $\{a_i\}$ y $n$ posiciones, hay $n$ posibles posiciones para $a_n$ . Una vez que hayamos colocado $a_n$ Hay $n-1$ puestos restantes para $a_{n-1}$ . Una vez que hayamos colocado $a_n$ y $a_{n-1}$ Hay $n-2$ puestos que quedan para $a_{n-2}$ y así sucesivamente. Así, hay $$ n(n-1)(n-2)\cdots3\cdot2\cdot1=n! $$ posibles formas de organizar el $n$ artículos.

Supongamos que dividimos el $n$ artículos en $k$ objetos blancos y $n-k$ objetos negros. Para cada disposición de los objetos blancos y negros que parezca igual, hay $k!$ reordenamientos de los objetos blancos y $(n-k)!$ reordenamientos de los objetos negros. Dado que hay $n!$ reajustes de la $n$ objetos, debe haber $$ \frac{n!}{k!(n-k)!}=\binom{n}{k} $$ disposiciones de la $k$ blanco y $n-k$ objetos negros que parecen diferentes.

Answer 3

Quizás te ayude repasar primero la fórmula de permutación $\frac {n!}{\left( n-k \right)!}$ y luego pensar en la adaptación que necesitamos si vamos a prescindir del orden. Así es más fácil.

Answer 4

En primer lugar, para $k\leq n$ debemos construir un $k$ -permutación de un $n$ -conjunto de elementos. Podemos elegir el primer elemento de $n$ maneras, el segundo punto en $n-1$ formas, cualquiera que sea la elección del primer elemento,..., y el $k$ a la partida de $n-(k-1)$ formas, cualquiera que sea la elección de la primera $k-1$ artículos. Por el Principio de Multiplicación el $k$ se puede elegir en $n(n-1)\cdots (n-k+1)$ formas. Podemos reescribir esto como $${n(n-1)\cdots (n-k+1)(n-k)!\over (n-k)!}={n!\over (n-k)!}.$$ Así, $P(n,k)={n!\over (n-k)!}$ . Por un $k$ -permutación de un conjunto $S$ de $n$ elementos, tenemos una disposición ordenada de $k$ de la $n$ elementos. Dado que nos preocupa el número de formas en que podemos elegir $k$ de la $n$ elementos queremos el número de arreglos desordenados (subconjuntos). Como cada arreglo tiene una longitud $k$ podemos permutarlas en $k!$ maneras. Así que el número de arreglos desordenados de los elementos de S es ${n!\over k!(n-k)!}$ . Así, para $k\leq n$ $$C(n,k)={n!\over k!(n-k)!}.$$

Answer 5

Tal vez valga la pena mencionar un método de solución que puede parecer un poco rebuscado, pero que es un excelente ejemplo introductorio a la teoría de funciones generadoras para lo cual el libro Generación de funciones por Herbert S. Wilf es muy recomendable.

Escribe $\dbinom{n}{k}$ para el número de elección $k$ objetos fuera de $n$ . Consideremos el polinomio $$ (1 + x_{1}) (1 + x_{2}) \cdots (1 + x_{n}) $$ en el $n$ indetermina $x_{1}, \dots, x_{n}$ . Es fácil convencerse de que este polinomio tiene exactamente $\dbinom{n}{k}$ monomios de grado $k$ . Si ahora se pone $x_{1} = \dots = x_{n} = x$ , donde $x$ es otra indeterminada, cada uno de estos monomios se reduce a $x^{k}$ de modo que se obtiene que $$ (1 + x)^{n} = \sum_{k = 0}^{n} \dbinom{n}{k} x^{k}. $$ Ahora usa Teorema de Taylor para polinomios para obtener la fórmula requerida.

Permítanme subrayar que esto puede parecer totalmente exagerado en este escenario relativamente sencillo. Pero el método tiene un enorme potencial.