¿Cómo resuelvo esta prueba combinatoria que involucra factorial (n)_k?

Question

¿Cómo resuelvo esta prueba combinatoria que involucra factorial (n)_k?

factorial
Matemáticas
redacción de pruebas
pruebas combinatorias

Intrepidez

Dejar $n$ y $k$ ser enteros positivos con $n \ge k$ . Dé una demostración combinatoria de que
${norte}_{k} = (norte - 1)_{k} + k (norte - 1)_{k - 1},$ $n_k = (n-1)_k + k(n-1)_{k-1},$ dónde $n_k$ es un factorial descendente: $n_k$ = $n(n-1)(n-2)\ldots(n-k+1)$ .

Sé $n_k = n \cdot (n-1)_{k-1}$ . Por ejemplo $10_4 = 10 \cdot 9_3$ , lo que equivale a: $10 \cdot 9 \cdot 8 \cdot 7 = 10 \cdot (9 \cdot 8 \cdot 7)$ .

Sin embargo, estoy completamente perdido sobre cómo extrapolar $n_k = (n-1)_k + k(n-1)_{k-1}$ de $n_k = n \cdot (n-1)_{k-1}$ .

Puedo resolver ejemplos numéricos en mi cabeza y tiene mucho sentido, pero me falta algo y no sé qué es lo que me falta.

Darij Grinberg

Pista: Dividir el

n

$n$ factor en

(n - k) + k

$\left(n-k\right) + k$ .

Respuestas (2)

¿Cómo resuelvo esta prueba combinatoria que involucra factorial (n)_k?

Grises · Answer 1

$n_k$ representa el número de arreglos de $n$ elementos en grupos de $k$ (el orden es relevante aquí). Divida esos arreglos en dos clases: aquellos donde un elemento en particular es parte del grupo y aquellos donde este elemento no es parte del grupo. El número de este último es $(n-1)_k$ porque tú eliges entre los demás. El número del primero es $k(n-1)_{k-1}$ porque eliges $k-1$ entre los restantes $(n-1)$ y aquí están $k$ posibles ubicaciones para el elemento fijo.

Pensé que se suponía que debías dar una prueba combinatoria, no algebraica.

Abhinav · Answer 2

No sé la notación que ha utilizado (todavía soy nuevo en combinatoria). Así que usaré notación factorial simple.

\frac{norte!}{(norte - k)!}

$\frac{n!}{(n-k)!}$

= \frac{((norte - k) + k) \cdot (norte - 1)!}{(norte - k)!}

$=\frac{{((n-k)+k)}\cdot{(n-1)!}}{(n-k)!}$

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

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

= (norte - 1)_{k} + k (norte - 1)_{k - 1}

$=(n-1)_k +k(n-1)_{k-1}$

¿Cómo resuelvo esta prueba combinatoria que involucra factorial (n)_k?

Intrepidez

Darij Grinberg

Respuestas (2)

Grises

Grises

Abhinav

Prueba combinatoria del teorema factorial y binomial descendente

Prueba combinatoria sobre factoriales decrecientes y sumas de factoriales decrecientes

Prueba con respecto a factoriales.

Identidad del coeficiente binomial de prueba: ∑nk=0kk!nk(nk)=n∑k=0nkk!nk(nk)=n\sum_{k=0}^n\frac{kk!}{n^k}\binom{ n}{k}=n

Derivar una identidad combinatoria

Demostración (casos e inducción): Encuentra el conjunto de enteros positivos tal que n!≥n3n!≥n3n! \geqn^3

Cómo probar esta identidad de conjuntos múltiples mediante prueba combinatoria

Demostrar una identidad factorial interesante (que cae)

Factoriales... ¿Cómo lo hacen?

¿Es un mal estilo matemático usar el mismo símbolo de índice en diferentes objetos indexados?