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]

Question

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]

Matemáticas
combinaciones
combinatoria
prueba alternativa
pruebas combinatorias
coeficientes binomiales

ankit

como probar eso $n \choose r$ = $\frac{n+1-r}{r}$ $n \choose r-1$ sin utilizar la expansión factorial de $n \choose r$ .

matemáticas duras

La brevedad extrema de su publicación invita a la confusión sobre qué, en lugar de "la expansión factorial", usaría para definir los coeficientes binomiales. Incluya esta configuración esencial para el problema en el cuerpo de su pregunta.

Respuestas (6)

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]

La brevedad extrema de su publicación invita a la confusión sobre qué, en lugar de "la expansión factorial", usaría para definir los coeficientes binomiales. Incluya esta configuración esencial para el problema en el cuerpo de su pregunta.

JMoravitz · Answer 1

El lado izquierdo cuenta claramente el número de formas de elegir $r$ objetos fuera de $n$ total.

El lado derecho cuenta igual, pero su lógica es la siguiente:

Elegir $r-1$ primero los objetos.
De los restantes $n-(r-1)$ objetos, elija uno de ellos para llenar el espacio vacío restante.
Reconoce que para cada elección de $r$ objetos, este método ha contado cada uno con un total de $r$ veces, así que divide por $r$ para dar cuenta de la simetría del problema.

Esto da un total de $\binom{n}{r-1}(n-(r-1))\cdot\frac{1}{r}=\frac{n+1-r}{r}\binom{n}{r-1}$ formas de seleccionar $r$ objetos fuera de $n$ total.

Por principios fundamentales, si dos expresiones cuentan correctamente el número de resultados del mismo escenario, entonces deben ser iguales.

No obtuve el punto número (3). ¿Podría por favor elaborar?
@Supermario A medida que avanzamos a través del principio de multiplicación, normalmente esperamos contar cada resultado exactamente una vez, sin embargo, en este caso, si hubiéramos aplicado el principio de multiplicación para los dos primeros pasos, de hecho, hemos contado cada resultado un total de $r$ veces. ( por ejemplo, haber escogido $\{a,b,c\},\{d\}$ da el mismo resultado que $\{a,b,d\},\{c\}$ y $\{a,c,d\},\{b\}$ etc... ). Dado que cada uno se contó el mismo número de veces, si dividimos por el número de veces que se contó cada uno es como si hubiéramos contado cada uno solo una vez, que es lo que pretendíamos.

Tomas Andrews · Answer 2

Es más fácil verlo si lo escribes así:

(\binom{norte}{r}) r = (\binom{norte}{r - 1}) (norte + 1 - r)

$\binom{n}{r}r=\binom{n}{r-1}(n+1-r)$

El lado izquierdo cuenta el número de formas de seleccionar $r$ elementos, luego seleccione uno de esos $r$ .

El lado derecho es el número de formas de seleccionar $r-1$ elementos y, a continuación, seleccione un elemento más de la $n-(r-1)=n-r+1$ elementos restantes.

Puede probar el teorema inductivamente en $n$ , usando $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$ , la identidad del triángulo de Pascal.

me saltaré el caso $n=1$ .

si es cierto para $n$ , entonces para $r\geq 1$ tenemos:

\begin{aligned} r (\binom{norte + 1}{r}) & = r (\binom{norte}{r - 1}) + r (\binom{norte}{r}) \\ (*) & = r (\binom{norte}{r - 1}) + (norte - r + 1) (\binom{norte}{r - 1}) \\ = (norte + 1) (\binom{norte}{r - 1}) \end{aligned}

$\begin{align}r\binom{n+1}{r} &=r\binom{n}{r-1} + r\binom{n}{r}\\ &= r\binom{n}{r-1}+(n-r+1)\binom{n}{r-1}\tag{*}\\ &= (n+1)\binom{n}{r-1} \end{align}$

donde la sustitución $(*)$ está permitida por la hipótesis de inducción.

Por otro lado, si $r>1$ , entonces:

\begin{aligned} (norte + 1 - r + 1) (\binom{norte + 1}{r - 1}) & = (norte + 2 - r) (\binom{norte}{r - 1}) + (norte + 2 - r) (\binom{norte}{r - 2}) \\ (*) & = (norte + 2 - r) (\binom{norte}{r - 1}) + (r - 1) (\binom{norte}{r - 1}) \\ = (norte + 1) (\binom{norte}{r - 1}) \end{aligned}

$\begin{align}(n+1-r+1)\binom{n+1}{r-1} &=(n+2-r)\binom{n}{r-1}+(n+2-r)\binom{n}{r-2}\\ &=(n+2-r)\binom{n}{r-1}+(r-1)\binom{n}{r-1}\tag{*}\\ &=(n+1)\binom{n}{r-1} \end{align}$

donde nuevamente, la sustitución es permitida por la hipótesis de inducción.

Entonces los dos valores son iguales. Tienes que lidiar con el cuidado donde $r=1$ por separado.

Entonces

r (\binom{norte + 1}{r}) = ((norte + 1) - r + 1) (\binom{norte + 1}{r - 1})

$r\binom{n+1}{r}=((n+1)-r+1)\binom{n+1}{r-1}$

y la inducción está hecha.

En realidad, estaba tratando de probar esta fórmula recursiva que estás probando a partir de la que pedí. Pero primero necesitaba probar lo que se pregunta en la pregunta.
De hecho, me gusta más esta explicación que la mía porque evita el argumento de "dividir para tener en cuenta la simetría" con el que tantas personas parecen tener problemas. +1
Sí, trate siempre de evitar la división en los argumentos de conteo, a menos que sea absolutamente necesario. :) @JMoravitz
@ThomasAndrews ¡Guau! Excelente prueba por doble conteo. ¿Podemos cumplir nuestra tarea sin usar el hecho de que $n \choose r$ representa el número de formas de seleccionar $r$ objetos fuera $n$ ? Usando el hecho de que $n \choose r$ representa el $r+1$ el término en el $n$ fila del triángulo de Pascal o algún otro hecho.

epi163sqrt · Answer 3

Aquí hay una respuesta basada en las dos identidades binomiales.

\begin{aligned} (1) & (\binom{norte}{r}) & = (\binom{norte}{norte - r}) \\ (2) & (\binom{norte}{r}) & = (\binom{norte - 1}{r - 1}) \frac{norte}{r} \end{aligned}

$\begin{align*} \binom{n}{r}&=\binom{n}{n-r}\tag{1}\\ \binom{n}{r}&=\binom{n-1}{r-1}\frac{n}{r}\tag{2} \end{align*}$

Empezamos por el lado derecho y obtenemos
$\begin{aligned} \frac{norte + 1 - r}{r} (\binom{norte}{r - 1}) & = \frac{norte + 1 - r}{r} (\binom{norte}{norte + 1 - r}) & \to (1) \\ = \frac{norte + 1 - r}{r} \cdot \frac{norte}{norte + 1 - r} (\binom{norte - 1}{norte - r}) & \to (2) \\ = \frac{norte}{r} (\binom{norte - 1}{norte - r}) \\ = \frac{norte}{r} (\binom{norte - 1}{r - 1}) & \to (1) \\ = (\binom{norte}{r}) & \to (2) \end{aligned}$ $\begin{align*} \frac{n+1-r}{r}\binom{n}{r-1}&=\frac{n+1-r}{r}\binom{n}{n+1-r}\qquad &\rightarrow (1)\\ &=\frac{n+1-r}{r}\cdot \frac{n}{n+1-r}\binom{n-1}{n-r}\qquad &\rightarrow (2)\\ &=\frac{n}{r}\binom{n-1}{n-r}\\ &=\frac{n}{r}\binom{n-1}{r-1}&\qquad\rightarrow (1)\\ &=\binom{n}{r}&\quad\rightarrow (2) \end{align*}$

Félix Marín · Answer 4

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

Un enfoque posible es la introducción de una 'técnica' de Función Generadora . Esencialmente, solo implica la identidad. $\ds{\left.\sum_{r = 1}^{\infty}{n \choose r}z^{r} \,\right\vert_{\ \verts{z}\ <\ 1}\ =\ \pars{1 + z}^{n} - 1}$ . A continuación, desarrollaré este enfoque:

\begin{aligned} \sum_{r = 1}^{\infty} \frac{norte + 1 - r}{r} (\binom{norte}{r - 1}) z^{r} = \sum_{r = 0}^{\infty} \frac{norte - r}{r + 1} (\binom{norte}{r}) z^{r + 1} = (norte + 1) z \sum_{r = 0}^{\infty} (\binom{norte}{r}) \frac{z^{r}}{r + 1} - z \sum_{r = 0}^{\infty} (\binom{norte}{r}) z^{r} \\ = & (norte + 1) z \sum_{r = 0}^{\infty} (\binom{norte}{r}) z^{r} \int_{0}^{1} t^{r} d t - z {(1 + z)}^{norte} \\ = & (norte + 1) z \int_{0}^{1} {(1 + z t)}^{norte} d t - {(1 + z)}^{norte + 1} + {(1 + z)}^{norte} \\ = (norte + 1) z \frac{{(1 + z)}^{norte + 1} - 1}{(norte + 1) z} - {(1 + z)}^{norte + 1} + {(1 + z)}^{norte} = {(1 + z)}^{norte} - 1 = \sum_{r = 1}^{\infty} (\binom{norte}{r}) z^{r} \end{aligned}

$\begin{align} &\sum_{r = 1}^{\infty}\color{#f00}{{n + 1 - r \over r}{n \choose r - 1}}z^{r} = \sum_{r = 0}^{\infty}{n - r \over r + 1}{n \choose r}z^{r + 1} = \pars{n + 1}z\sum_{r = 0}^{\infty}{n \choose r}{z^{r} \over r + 1} - z\sum_{r = 0}^{\infty}{n \choose r}z^{r} \\[5mm] = &\ \pars{n + 1}z\sum_{r = 0}^{\infty}{n \choose r}z^{r}\int_{0}^{1}t^{r}\,\dd t - z\pars{1 + z}^{n} \\[5mm] = &\ \pars{n + 1}z\int_{0}^{1}\pars{1 + zt}^{n}\,\dd t - \pars{1 + z}^{n + 1} + \pars{1 + z}^{n} \\[5mm] & = \pars{n + 1}z\,{\pars{1 + z}^{n + 1} - 1 \over \pars{n + 1}z} - \pars{1 + z}^{n + 1} + \pars{1 + z}^{n} = \pars{1 + z}^{n} - 1 = \sum_{r = 1}^{\infty}\color{#f00}{n \choose r}z^{r} \end{align}$

Asinomás · Answer 5

Considere el gráfico bipartito donde los vértices en el lado izquierdo son los $k$ -conjuntos y vértices en el otro son $(k+1)$ -conjuntos y conectamos dos si uno contiene al otro.

Como los vértices del lado izquierdo tienen grado $n-k$ y los vértices de la derecha tienen grado $k+1$ obtenemos la igualdad deseada al contar el número de aristas.

graham kemp · Answer 6

$\dbinom nr\dbinom r 1$ cuenta todas las formas distintas de seleccionar $r$ de $n$ elementos y luego $1$ de aquellos $r$ . Así producir conjuntos de tamaño $r-1$ , $1$ , y $n-r$ elementos de un conjunto de $n$ elementos.
$\dbinom{n}{r-1}\dbinom {n-r+1}1$ todas las formas distintas de seleccionar $r-1$ de $n$ elementos y luego $1$ de los restantes $n-r+1$ elementos. Así producir conjuntos de tamaño $1$ , $r-1$ , y $n-r$ elementos de un conjunto de $n$ elementos.
Estos recuentos deben ser iguales.

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]

ankit

matemáticas duras

Respuestas (6)

JMoravitz

Alumno

JMoravitz

Tomas Andrews

ankit

Tomas Andrews

JMoravitz

Tomas Andrews

ankit

epi163sqrt

Félix Marín

Asinomás

graham kemp

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

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?

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Demuestra que ∑k=0r(n+kk)=(n+r+1r)∑k=0r(n+kk)=(n+r+1r)\sum\limits_{k=0}^r\binom{ n+k}k=\binom{n+r+1}r usando argumentos combinatorios. [duplicar]

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

¿De cuántas maneras puedo pasar del 1 al 10 en el siguiente diagrama?

Una pregunta combinatoria sobre números pares e impares