Prueba algebraica y combinatoria de una identidad

Question

Prueba algebraica y combinatoria de una identidad

Estadísticas
Matemáticas
combinaciones
combinatoria
pruebas combinatorias

AC24

Para dos enteros cualesquiera $2 \le k \le n-2$ , ahí está la identidad

(\binom{norte}{2}) = (\binom{k}{2}) + k (norte - k) + (\binom{norte - k}{2}) .

$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$

a) Da una prueba algebraica de esta identidad, escribiendo los coeficientes binomiales en términos de factoriales y simplificando.

b) Dar una prueba combinatoria (e interpretación) de esta identidad.

Para la parte a, convertí las combinaciones en factoriales y traté de hacer que la RHS fuera igual a la LFS, que es $\frac{n!}{2!(n-2)!}$ . Sin embargo, me quedé atascado en el tercer paso con todo el $k$ 'arena $(n-k)!$ 's.

Para la parte b, llegué a decir que eliges 2 niños de n niños para recibir dulces en LHS. veo el $k$ y $n-k$ en cierto modo se dan cuenta unos de otros a la derecha, pero no puedo explicar esto con palabras.

Soy bastante nuevo en las pruebas matemáticas y cualquier ayuda es apreciada. ¡Gracias!

Respuestas (3)

Prueba algebraica y combinatoria de una identidad

Brian M Scott · Answer 1

AYUDA: Para (a), tienes

(\binom{k}{2}) + k (norte - k) + (\binom{norte - k}{2}) = \frac{k!}{2! (k - 2)!} + k (norte - k) + \frac{(norte - k)!}{2! (norte - k - 2)!} .

$\binom{k}2+k(n-k)+\binom{n-k}2=\frac{k!}{2!(k-2)!}+k(n-k)+\frac{(n-k)!}{2!(n-k-2)!}\;.$

Comience haciendo muchas cancelaciones:

\begin{aligned} \frac{norte!}{(norte - 2)!} & = norte (norte - 1) \\ \frac{k!}{(k - 2)!} & = k (k - 1), y \\ \frac{(norte - k)!}{(norte - k - 2)!} & = (norte - k) (norte - k - 1) . \end{aligned}

$\begin{align*} \frac{n!}{(n-2)!}&=n(n-1)\\ \frac{k!}{(k-2)!}&=k(k-1)\;,\text{ and }\\ \frac{(n-k)!}{(n-k-2)!}&=(n-k)(n-k-1)\;. \end{align*}$

Una vez que hayas hecho eso, el álgebra se vuelve muy sencillo.

Para (b), suponga que hay $k$ chicos y $n-k$ chicas. Entonces $\binom{k}2$ es el número de maneras de elegir dos niños, $\binom{n-k}2$ es el número de maneras de elegir dos niñas, y $k(n-k)$ es el número de formas de elegir ... ¿cuáles?

rogerl · Answer 2

La parte (a) es sencilla:

\begin{aligned} (\binom{k}{2}) + k (norte - k) + (\binom{norte - k}{2}) & = \frac{k!}{(k - 2)! 2!} + k (norte - k) + \frac{(norte - k)!}{2! (norte - k - 2)!} \\ = \frac{k (k - 1)}{2} + k (norte - k) + \frac{(norte - k) (norte - k - 1)}{2} \\ = \frac{k^{2} - k + 2 norte k - 2 k^{2} + {norte}^{2} - 2 norte k - norte + k^{2} + k}{2} \\ = \frac{norte (norte - 1)}{2} = (\binom{norte}{2}) . \end{aligned}

$\begin{align*} \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2} &= \frac{k!}{(k-2)!2!} + k(n-k) + \frac{(n-k)!}{2!(n-k-2)!} \\ &= \frac{k(k-1)}{2} + k(n-k) + \frac{(n-k)(n-k-1)}{2} \\ &= \frac{k^2-k+2nk-2k^2 + n^2 - 2nk - n + k^2 + k}{2} \\ &= \frac{n(n-1)}{2} = \dbinom{n}{2}. \end{align*}$

chirivía alegre · Answer 3

La parte (b) también es sencilla. El LHS mide cuántas maneras hay de elegir 2 bolas de n. Esto es lo mismo que contar las formas de elegir 2 de los primeros k, o 2 de los últimos nk, o uno en los primeros k y uno en los últimos nk.

Prueba algebraica y combinatoria de una identidad

AC24

Respuestas (3)

Brian M Scott

rogerl

chirivía alegre

Demostrar la identidad (k2)(k2)k \choose 2 + (kk−2)(kk−2)k \choose k-2 + k2k2k^2 = (2k2)(2k2)2k \choose 2, donde k≥2k ≥2k\geq2 usando una prueba combinatoria.

¿Cuál es la prueba combinatoria para la fórmula de S(n,k)S(n,k)S(n,k) - Números de Stirling de segunda especie?

Probabilidad de sacar 3 bolas rojas en 9 intentos en cualquier orden

Cómo probar que (nr)(nr)n \choose r = n+1−rrn+1−rr\frac{n+1-r}{r} (nr−1)(nr−1)n \choose r -1 sin usar la expansión factorial de (nr)(nr)n \choose r? [cerrado]

Una pregunta combinatoria sobre números pares e impares

¿Por qué surge esta relación de recurrencia en la que nnn elige kkk? [duplicar]

Números de Stirling de segunda clase con restricciones

¿De cuántas maneras se pueden dar 5 premios a un grupo de 20 personas con restricciones?

Forma cerrada para encontrar el número de rutas en un tablero nxm

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k