Probar usando combinatoria$n \mid \binom{n}{m} \binom{n}{m-1}$

Question

Probar usando combinatoria$$n ~\Bigg | \binom{n}{m} \binom{n}{m-1}$ $.

Debemos encontrar un problema cuya respuesta es$\displaystyle\dfrac{\displaystyle\binom{n}{m} \binom{n}{m-1}}{n \times f(n,m)}$ pero no puedo encontrar tal problema. ¿Alguna sugerencia?

Answer 1

Supongo que te refieres a que $m$ es un número entero entre el$1$$n$, inclusive.

Deje $S$ el conjunto de pares que consiste en un $m$-elemento subconjunto de $\{1,\ldots,n\}$ e una $(m-1)$-elemento subconjunto de $\{1,\ldots,n\}$. Escribir un elemento de $S$ como un par $(\{a_1,\ldots,a_m\},\{b_1,\ldots,b_{m-1}\})$ donde $a_i,b_i\in \{1,\ldots,n\}$ todos los $i$ e las $a_i$ elementos son distintos uno del otro, como son las $b_i$ elementos.

Con un par, podemos cíclicamente el incremento de cada una de sus entradas por $1$ para obtener el nuevo par $(\{a_1+1,\ldots,a_m+1\},\{b_1+1,\ldots,b_{m-1}+1\}).$ Aquí la adición es el modulo $n$.

Después de realizar el ciclo de incremento de $n$ veces, volvemos a la par que hemos empezado. Por otra parte, cada una de las $n$ pares encontrados a lo largo de la manera en que deben ser distintos el uno del otro. Para ver por qué esto es cierto, supongo que para que, al contrario, después de $k$ cíclico turnos, $1\leq k<n$, volvemos a la misma par que había comenzado con. La única manera en que esto puede suceder es que si tanto $km$ $k(m+1)$ son múltiplos de $n$. Pero entonces su diferencia, $k$, también tendría que ser un múltiplo de $n$, lo cual es una contradicción.

Por lo tanto, hemos encontrado una forma de la partición de los elementos de $S$ en grupos de tamaño $n$, lo $n$ divide $|S|$. Por otro lado, $|S|=\binom{n}{m}\binom{n}{m-1}$. Esto produce el deseado combinatoria prueba del hecho de que $n$ divide $\binom{n}{m}\binom{n}{m-1}$.

---

EDIT: me permite aclarar un punto clave en la prueba anterior, con el fin de responder a una pregunta que se formuló en los comentarios de abajo. La razón por la $km$ $k(m-1)$ deben ser múltiplos de $n$ puede ser visto por considerar las sumas $a_1+\cdots+a_m$ $b_1+\cdots+b_{m-1}$ modulo $n$. Cada vez que un incremento que se realiza, las sumas aumentar por $m$ $m-1$ modulo $n$, respectivamente. Por tanto, si la pareja vuelve a su valor inicial después de $k$ cíclicos cambios, ya que las sumas que se incrementa a $km$ $k(m-1)$ modulo $n$ durante este tiempo, debemos tener tanto $km$ $k(m-1)$ son múltiplos de $n$.

(Se puede considerar el caso de $m=3$ para ganar algo de intuición de lo que está pasando.)

Answer 2

Tal vez esto no es una prueba combinatoria, pero$$\frac{1}{n}\,\binom{n}{m}\,\binom{n}{m-1}=\binom{n-1}{m-1}\,\binom{n+1}{m+1}-\binom{n}{m}\,\binom{n}{m-1}\,.$ $ Esto se debe a que$$\frac{1}{n}\,\binom{n}{m}\,\binom{n}{m-1}=\frac{1}{m}\,\binom{n-1}{m-1}\,\binom{n}{m-1}=\frac{1}{n+1}\,\binom{n-1}{m-1}\,\binom{n+1}{m}\,.$ $ El resultado anterior se debe a la identidad$\displaystyle\binom{k}{r}=\frac{k}{r}\,\binom{k-1}{r-1}$, que tiene una prueba combinatoria.