Es directo demostrar eso si $m,n\in\mathbb{Z}$ y $m\geq n$ y $$m\mid \gcd(m, n)\binom{m}{n}.$ $ estoy tratando de encontrar una interpretación combinatoria de este hecho, pero parece que no puedo llegar a uno. Mi dos pruebas son formales y no me dan ninguna visión combinatoria.
Respuestas
¿Demasiados anuncios?
vadim123
Puntos
54128
Set $\gcd(m,n)=d$ y escribir $m=da, n=db$ donde $\gcd(a,b)=1$. Luego de su declaración es equivalente a $$a\left|{da\choose db}\right.$$
Considere la posibilidad de subconjuntos de tamaño $db$$S=\{0,1,2,\ldots, da-1\}$. La permutación $\phi:S\rightarrow S$ dada por $\phi(x)=x+d\pmod{da}$. $\phi$ también induce un mapa de los subconjuntos de tamaño $db$. Podemos llamar a dos de los subconjuntos equivalente si se puede llegar de uno a otro por iteración $\phi$. La iteración $\phi$ $a$ veces nos llegan de vuelta a donde empezamos, y de hecho todas las $a$ subconjuntos deben ser distintos debido a $\gcd(a,b)=1$. Por lo tanto los subconjuntos de tamaño $db$ ha sido dividido en clases de tamaño de $a$, lo que demuestra la declaración.
ciberandy
Puntos
104
Esto no es completamente combinatoria, pero:
Podemos demostrar que $\begin{pmatrix} m \\ n \end{pmatrix}$ es siempre un múltiplo de $m/\gcd(m,n)$ el uso de la izquierda de la multiplicación de la acción de $\mathbb{Z}_m$ en el conjunto de $X$ de todos sus subconjuntos de tamaño $n$. Por definición, $|X|=\begin{pmatrix}m\\n\end{pmatrix}$. Por la teoría de las acciones del grupo, el conjunto $X$ se puede dividir en las órbitas. Entonces es suficiente para demostrar que cada órbita debe tener el tamaño que es un múltiplo de a $m/\gcd(m,n)$. Por la órbita estabilizador teorema, entonces, es suficiente para demostrar que el estabilizador de un conjunto $E$ del tamaño de la $n$ debe tener un tamaño que divide $\gcd(m,n)$.
Deje $E$ ser un subconjunto de a $\mathbb{Z}_m$ del tamaño de la $n$. El estabilizador de la $E$ es un subgrupo de $\mathbb{Z}_n$, y todos los subgrupos de $\mathbb{Z}_m$ son cíclicos. Además, si se elige el mínimo miembro de la $d$ de cualquier subgrupo de $\mathbb{Z}_m$, $d$ genera ese subgrupo. Así que vamos a $d$ ser la mínima generador de la estabilizador de $E$. Así que el estabilizador de la $E$ tiene el tamaño de $m/d$, lo que significa que tenemos que mostrar que $m/d$ divide $\gcd(m,n)$.
Pero si elegimos un elemento $x$$E$, entonces los elementos de a $x,x+d,x+2d,\dots$ pertenecen todos a $E$ (por la definición de un estabilizador); es decir, si $H$ es el estabilizador de la $E$, entonces el coset $x+H$ es un subconjunto de a $E$. Por lo $E$ es una unión de cosets de $H$, todos los cuales tienen el tamaño de $m/d$. Por lo $n$ es un múltiplo de a $m/d$, lo que significa que $m/d$ es un factor común de $m$$n$. Por lo $\gcd(m,n)$ divide $m/d$, como queríamos.
