Estoy estudiando combinatoria y me encontré con la identidad $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$ $ he leído la prueba algebraica y no recurrir a mí. ¿Hay un truco contar elegante que podemos utilizar para llegar a esta identidad?
Esta pregunta ya tiene respuestas:
- Demostrar $\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (4 respuestas )
Respuestas
¿Demasiados anuncios?
¿Qué se obtiene cuando usted toma una secuencia de unos y ceros de longitud $n+1$ $k+1$ los que y quitar la derecha $1$ y todo a la derecha?
Ejemplo: $100100\rightarrow 100$
Usted consigue una secuencia que tiene $k$ que, la longitud varía entre $k$y $n$ dependiendo de la secuencia real.
De hecho, esta función es una biyección entre las secuencias de longitud $n+1$ y $k+1$ los y las secuencias de longitud $n$ o menos y $k$ los.
Esto establece $\binom{n+1}{k+1}=\sum\limits_{j=k}^{n}\binom{j}{k}$
Austin Mohr
Puntos
16266
Prefiero omitir el cero términos y probar $$ \sum_{k = p}^n \binom{k}{p} = \binom{n+1}{p+1}. $$
Supongamos que tenemos $n+1$ personas de pie en una línea, de modo que nos podemos referir a la Persona 1, Persona 2, ..., Persona $n+1$.
En la parte derecha, se cuenta el número de comités de tamaño $p+1$ que puede ser formado a partir de estos $n+1$ de la gente.
El lado izquierdo cuenta la misma cosa, pero lo hace en los casos.
El primer caso es que la Persona $p+1$ es el más grande numeradas persona en el comité. Esto significa que debemos elegir el resto de $p$ a los miembros del comité de la primera $p$ de personas en línea, que se puede hacer en $\binom{p}{p}$ maneras.
El segundo caso es que la Persona $p+2$ es el más grande numeradas persona en el comité. Esto significa que debemos elegir el resto de $p$ a los miembros del comité de la primera $p+1$ de personas en línea, que se puede hacer en $\binom{p+1}{p}$ maneras.
Continuando de esta manera, el último caso sería que la Persona $n+1$ es el más grande numeradas persona en el comité. Esto significa que debemos elegir el resto de $p$ a los miembros del comité de la primera $n$ de personas en línea, que se puede hacer en $\binom{n}{p}$ maneras.
Suma más de estos casos, produce el deseo de identidad.
Markus Scheuer
Puntos
16133
Aquí es otro enfoque combinatorio utilizando entramado de caminos.
Podemos interpretar $\binom{n+1}{p+1}$ como el número de entramado de caminos de longitud $n+1$ contiene $p+1$ horizontal $(1,0)$-pasos y $n-p$ vertical $(0,1)$-pasos.
Esto es válido porque no se $\binom{n+1}{p+1}$ opciones para seleccionar $p+1$ pasos en dirección horizontal dejando el resto de la $n-p$ pasos para la dirección vertical.
$$ $$
Vamos a considerar todas las rutas de$(0,0)$$(p+1,n-p)$. Sabemos que hay $\binom{n+1}{p+1}$ caminos diferentes.
Por otro lado cada uno de estos caminos tiene que cruzar la línea vertical que va a través de $(p,0)$. Los puntos de cruce se $(p,0), (p,1), \ldots, (p,n-p)$. De esta manera podemos particionar el conjunto de entramado de caminos en conjuntos que contengan $\binom{k}{p}$ elementos con $p\leq k \leq n$ constitutivo de la identidad
\begin{align*} \sum_{k=0}^n\binom{k}{p}=\binom{n+1}{p+1}\qquad\quad n\geq 0 \end{align*}
Graham Kemp
Puntos
29085
El RHS cuenta las formas de seleccionar lugares de $p+1$ en una línea de $n+1$ lugares.
El LHS cuenta las formas de seleccionar una línea de $p$ lugares, sumado sobre todos los valores de $k$ $k: 0\leq k\leq n$ lugares. (Más estrictamente, $k: p\leq k\leq n$, puesto que no hay ninguna manera de hacer esto para $k<p$).
Interpretación de $k+1$ como la posición del último, o $(p+1)^{st}$, lugar, notamos que estos dos contar formas de realizar la misma tarea exacta. Ergo son equivalentes.
$$\sum_{k=p}^n \dbinom{k}{p} = \binom{n+1}{p+1}$$
