El clarificar uno las fórmulas relacionados con Teorema del binomio.

Question

Puede alguien por favor aclararme esta fórmula, realmente no entiendo, sé que el lado izquierdo es para contar el número de subconjuntos con un máximo de elementos de un conjunto de n elementos de j, pero el lado derecho solo no entiendo incluso con aclaración de libro.

$$\sum_{j=0}^k{n\choose{j}}=\sum^k_{j=0}{n-j-1\choose{k-j}}2^j$$

Ty.

Answer 1

Usted puede probar la fórmula por medio de la inducción, pero si usted quiere entender que se vea en el triángulo de Pascal. El lado izquierdo es la suma de los primeros a $k+1$ términos en el $n^{\rm th}$ fila (contando las filas de$0$), mientras que el lado derecho es la suma de los términos de la diagonal a partir de la cero término en el $(n-k-1)^{\rm st}$ fila $k^{\rm th}$ plazo de la $(n-1)^{st}$ fila, ponderado adecuadamente por los poderes de la $2$.

Ahora, podemos reducir una suma a los otros por el uso repetido del hecho de que cuando se $0 < l < m$ tenemos $${m \choose l} = {m-1 \choose l-1} + {m-1 \choose l},$$ es decir, la suma de cualquier término no en el límite se obtiene sumando los dos términos anteriores. De esta manera, podremos multiplicar la suma por $2$ cada vez que se mueve de un nivel (porque cada término anterior contribuye tanto a la izquierda y a la derecha en el siguiente nivel), en el extremo dejando sólo la suma de los dos lados del triángulo (según lo determinado por la diagonal y la fila original) multiplicado por los poderes de la $2$. Si podemos deshacernos de la mano izquierda que se hacen pero que muy sencillo porque todos los términos en el límite del triángulo de Pascal se $1$ y sumando sobre todos los poderes de $2$ da, precisamente, $2^k$ como el último término de la suma en el lado derecho.

Answer 2

Creo que quiso decir que el lado izquierdo es el número de subconjuntos de un $n$-elemento de conjunto que tienen en la mayoría de $k$ elementos, no en la mayoría de $j$ elementos. El hecho de que lo estuviera mirando de esa manera sugiere que usted puede ser que desee una combinatoria explicación en lugar de una expresión algebraica. He encontrado uno, pero es un poco implicadas.

Para $m\in\Bbb Z^+$ deje $[m]=\{1,2,\ldots,n\}$. Supongamos que $n,k\in\Bbb Z^+$, e $0\le k\le n$.

La proposición. Si $S\subseteq[n]$, e $|S|\le k$, no es exactamente una $j\in\{0,1,\ldots,k\}$ tal que $$|S\cap[n-j-1]|=k-j\tag{1}$$ and $n-j\noen S$. $(1)$ just says that exactly $k-j$ members of $S$ are smaller than $n-j$.

Prueba. Vamos $J=\{j\in\{0,1,\ldots,k\}:n-j\notin S\}$; $|\{0,1,\ldots,k\}|=k+1>|S|$, por lo $J\ne\varnothing$. Deje $\ell=k+1-|S|$; claramente $|J|\ge\ell>0$. Por lo tanto, hay un $j\in J$ tal que $|[j]\cap J|=\ell$: $j$ es el $\ell$-ésimo miembro de $J$ a contar desde el elemento más pequeño de $J$. Por lo tanto, el conjunto de $$\{n,n-1,n-2,\ldots,n-j\}\tag{2}$$ contains exactly $\ell$ members of $[n]\setminus S$. The set in $(2)$ has cardinality $j+1$, it contains $$j+1-\ell=j+1-(k+1-|S|)=|S|-(k-j)$$ members of $S$, and the other $k-j$ members of $S$ are therefore smaller than $n-j$. If $j\,'\J\setminus\{j\}$, the set $\{n,n-1,\ldots,n-j\,'\}$ does not contain exactly $\ell$ members of $[n]\setminus S$ and hence does not contain exactly $|S|-(k-j\,')$ members of $S$, and the number of elements of $S$ smaller than $n-j\,'$ is therefore not $k-j\,'$. Thus, $j$ is the unique element of $\{0,1,\ldots,k\}$ with the desired properties. In the sequel I'll denote this element by $j_S$. $\dashv$

Ahora, considere el $j$ plazo en la parte derecha de la identidad, $$\binom{n-j-1}{k-j}2^j\;;$$ I claim that it gives the number of $S\subseteq[n]$ such that $|S|\k le$ and $j_S=j$. Since for each subset of $S$ of $[n]$ of cardinality at most $k$ there is a unique $j\in\{0,1,\ldots,k\}$ such that $j_S=j$, proving this claim would show that the righthand side also just counts those subsets of $[n]$.

Para demostrar que el reclamo, supongamos que $S\subseteq[n]$, $|S|\le k$, y $j_S=j$. A continuación, la definición de $j_S$ asegura que $S$ tiene exactamente $k-j$ elementos en $[n-j-1]$; estos $k-j$ elementos más pequeños que $n-j$ puede ser elegido en $\binom{n-j-1}{k-j}$ maneras. La definición de $j_S$ también se asegura de que $n-j\notin S$, por lo que el resto de $S$ puede ser cualquier subconjunto de la $j$-element set $\{n,n-1,n-2,\ldots,n-j+1\}$, y $2^j$ dichos subconjuntos. Por lo tanto, no se $\binom{n-j-1}{k-j}2^j$ conjuntos de $S\subseteq[n]$ tal que $|S|\le k$$j_S=j$, como se reivindica.