Demostración de identidades mediante interpretación combinatoria de coeficientes binomiales

Question

Demostración de identidades mediante interpretación combinatoria de coeficientes binomiales

Matemáticas
combinatoria
Matemáticas discretas
coeficientes binomiales

Anónimo

Dejar $n \in \mathbb{N}$ . Demostrar las identidades
$(\binom{norte}{k}) = (\binom{norte - 1}{k - 1}) + (\binom{norte - 1}{k})$ $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ y $\sum_{k = 0}^{norte} {(\binom{norte}{k})}^{2} = (\binom{2 norte}{norte})$ $\sum^{n}_{k=0}\binom{n}{k}^2 = \binom{2n}{n}$ utilizando únicamente la interpretación combinatoria del coeficiente binomial.

No entiendo exactamente lo que significa con " interpretación combinatoria del coeficiente binomial ". Puedo resolver la primera identidad simplemente usando un coeficiente binomial como este:

(\binom{norte - 1}{k - 1}) + (\binom{norte - 1}{k}) = \frac{(norte - 1)!}{(norte - k)! (k - 1)!} + \frac{(norte - 1)!}{(norte - k - 1)! k!} = \frac{(norte - 1)! k}{(norte - k)! k!} + \frac{(norte - 1)! (norte - k)}{(norte - k)! k!} = \frac{(norte - 1)! [k + (norte - k)]}{(norte - k)! k!} = \frac{(norte - 1)! norte}{(norte - k)! k!} = \frac{norte!}{(norte - k)! k!} = (\binom{norte}{k})

$\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!k!} = \frac{(n-1)!k}{(n-k)!k!} + \frac{(n-1)!(n-k)}{(n-k)!k!} = \frac{(n-1)![k+(n-k)]}{(n-k)!k!} = \frac{(n-1)!n}{(n-k)!k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}$

Y para la segunda identidad, puedo aplicar simetría, luego Vandermonde para obtener:

\sum_{k = 0}^{norte} {(\binom{norte}{k})}^{2} = \sum_{k = 0}^{norte} (\binom{norte}{k}) (\binom{norte}{norte - k}) = (\binom{2 norte}{norte})

$\sum^{n}_{k=0}\binom{n}{k}^2 = \sum^{n}_{k=0}\binom{n}{k}\binom{n}{n-k} = \binom{2n}{n}$

Sin embargo, no entiendo exactamente si el problema requiere este tipo de solución, si no, me gustaría ver una prueba de las identidades usando la interpretación combinatoria del coeficiente binomial .

Respuestas (2)

Demostración de identidades mediante interpretación combinatoria de coeficientes binomiales

rogerl · Answer 1

rogerl

"Usar una interpretación combinatoria" significa usar lo que el símbolo $\dbinom{n}{k}$ medio; es decir, el número de formas de elegir $k$ cosas de $n$ cosas. En cada caso, desea contar las cosas de dos maneras diferentes.

Sugerencias:

$\dbinom{n}{k}$ es el número de formas de elegir $k$ cosas de $n$ . dividir el $n$ cosas en un grupo de $n-1$ y un grupo de $1$ . Si tu eliges $k$ cosas de la $n$ , ¿cuántos podrías haber elegido del primer grupo? ¿De la segunda?
Del mismo modo, considere $2n$ cosas, y dividirlas en dos grupos de $n$ cosas. Si tu eliges $n$ cosas de esos $2n$ , entonces, ¿cuántos habrás elegido del primer grupo? ¿De la segunda?

usuario72151

Veo que @froggie a continuación ha dado un ejemplo para la primera identidad. El segundo implica una suma y un cuadrado, por lo que me confunde. si dividimos

2 n

$2n$ en dos conjuntos de

n

$n$ y elegimos

n

$n$ elementos, podemos elegir todos los elementos del primer conjunto o del segundo conjunto. Esta es una opción. Otra opción es que elijamos algunos elementos del primer conjunto y algunos elementos del segundo conjunto. Donde nuevamente podemos elegir la mitad del primero y el segundo, o no, es decir, más de un conjunto y menos del otro. Supongo que esto corresponde a la suma en la identidad, pero me cuesta formalizar una solución.

rogerl

Estás en el camino correcto. supongamos que eliges

k

$k$ de los elementos del primer conjunto. ¿Cuántos entonces elegirás del segundo? Así que juntos hay

(\binom{n}{k}) (\binom{n}{n - k}) = {(\binom{n}{k})}^{2}

$\binom{n}{k}\binom{n}{n-k} = \binom{n}{k}^2$ formas de elegir

2 k

$2k$ elementos donde

k

$k$ de ellos provienen del primer conjunto. ¿Puedes terminarlo desde allí?

usuario72151

Entonces, si elijo

k

$k$ elementos del primer conjunto, entonces necesito elegir

n - k

$n-k$ elementos del segundo conjunto, para haber elegido

n

$n$ elementos. Ya has mostrado esto, usando la simetría del coeficiente binomial, tienes

{(\binom{n}{k})}^{2}

$\binom{n}{k}^2$ . Ahora, necesito incluir la suma de alguna manera. Supongo que esta es la parte, donde hacemos todas las combinaciones, como elegir 1 elemento del primer conjunto, y

n - 1

$n-1$ elementos del segundo, 2 elementos del primero, y

n - 2

$n-2$ elementos del segundo, y así sucesivamente. Sin embargo, todavía no sé cómo lo escribiré concretamente como prueba.

usuario72151

@rogerl Sí, también obtuve la misma parte y también tengo problemas para finalizar la prueba de la segunda parte. ¿Qué dice sobre el comentario anterior y cómo debe finalizarse?

rogerl

Bueno, creo que está bastante hecho usando el comentario anterior. Algo como: para cada

k

$k$ , elegir

k

$k$ del primer grupo; entonces debes elegir

n - k

$n-k$ del segundo, dando

{(\binom{n}{k})}^{2}

$\binom{n}{k}^2$ . Sumando todo lo posible

k

$k$ (de

0

$0$ a

n

$n$ ) da el resultado.

ranita · Answer 2

Creo que lo que quieren decir es un argumento como el siguiente (para la primera identidad). Dejar $X$ frijol $n$ -conjunto de elementos. Entonces $\binom{n}{k}$ es el numero de $k$ -subconjuntos de elementos de $X$ . Si $x\in X$ es un elemento fijo de $X$ , entonces puedo dividir el $k$ -subconjuntos de elementos de $X$ en dos clases: las que contienen $x$ y los que no. El $k$ -subconjuntos de elementos que no contienen $x$ son precisamente los $k$ -subconjuntos de elementos de $X-\{x\}$ , y aquí están $\binom{n-1}{k}$ tales conjuntos. Entonces $k$ -subconjuntos de elementos de $X$ que contienen $x$ son todos de la forma $\{x\}\cup Y$ , dónde $Y$ es un $k-1$ -subconjunto de elementos de $X-\{x\}$ ; hay $\binom{n-1}{k-1}$ tales conjuntos. Así, en total, hay $\binom{n-1}{k} + \binom{n-1}{k-1}$ total $k$ -subconjuntos de elementos de $X$ , demostrando que

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

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$

Tenga en cuenta que esto se hizo simplemente utilizando la interpretación de los coeficientes binomiales como el número de subconjuntos de un tamaño dado de un conjunto más grande; no usamos la fórmula para los coeficientes binomiales en absoluto. Creo que esto es lo que están pidiendo.

Demostración de identidades mediante interpretación combinatoria de coeficientes binomiales

Anónimo

Respuestas (2)

rogerl

usuario72151

rogerl

usuario72151

usuario72151

rogerl

ranita

¿Trayectorias de coeficientes binomiales?

Prueba combinatoria (y algebraica) de una identidad que involucra números Lah

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Problema combinatorio: bolas negras y blancas divididas en k grupos con límites, y luego seleccionando una secuencia de solo bolas negras.

Número de rutas en una cuadrícula de S a M

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

Explicación combinatoria de por qué n2=(n2)+(n+12)n2=(n2)+(n+12)n^2 = {n \elegir 2} + {n+1 \elegir 2}

Extraer coeficientes para resolver la relación de recurrencia

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2