¿Por qué $(128)!$ es igual al producto de estos coeficientes binomiales $128! = \binom{128}{64}\binom{64}{32}^2 \dots \binom21^{64}$ ?

Question

Estoy trabajando con algunos juegos de práctica de combinatoria y encontré el siguiente problema que no puedo resolver.

Pide que se demuestre lo siguiente:

$$128! = \binom{128}{64}\binom{64}{32}^2\binom{32}{16}^4\binom{16}8^8\binom 84^{16}\binom 42^{32}\binom{2}{1}^{64}$$

Raro, ¿no? Lo primero que noté es que los exponentes reflejan el $r$ variables. Normalmente me limitaría a reexpresar cada declaración en $\frac{n!}{(n-r)!r!}$ forma, pero los exponentes me desconciertan. Hay alguna intuición sobre los factoriales o nCr que deba tener en cuenta aquí?

Answer 1

Para divertirnos, lo hacemos con un argumento combinatorio. Tomemos $128$ diferentes objetos. Demostramos que el lado derecho cuenta las permutaciones de estos objetos.

Imagina que haces la permutación de la siguiente manera. Primero decida quién estará en la primera mitad (y, por tanto, quién estará en la segunda). Esto puede hacerse en $\binom{128}{64}$ formas. Ahora decida quiénes de la primera mitad estarán en el primer trimestre, y quiénes de la segunda mitad estarán en el tercer trimestre. Esto se puede hacer en $\binom{64}{32}^2$ formas.

Ahora decida quién de entre el primer cuarto estará en el primer octavo, quién de entre el segundo cuarto estará en el tercer octavo, quién de entre el tercer cuarto estará en el quinto octavo, quién de entre el cuarto cuarto estará en el séptimo octavo. Esto se puede hacer en $\binom{32}{16}^4$ formas.

Continúa.

Answer 2

La cuestión es sencilla. Tenemos el lado derecho igual a $$\frac{128!}{64!^2}\frac{64!^2}{32!^4}\frac{32!^4}{16!^8}\frac{16!^8}{8!^{16}}\frac{8!^{16}}{4!^{32}}\frac{4!^{32}}{2!^{64}}\frac{2!^{64}}{1}=128!$$

Answer 3

Es sencillo desde el punto de vista algebraico. Si introducimos la fórmula estándar $\binom{n}{r} = \frac{n!}{r! (n-r)!}$ entonces tenemos \begin {align*} & \binom {128}{64} \binom {64}{32}^2 \binom {32}{16}^4 \binom {16}{8}^8 \binom {8}{4}^{16} \binom {4}{2}^{32} \binom {2}{1}^{64} \\ [8pt] = {} & \left ( \frac {128!}{64!^2} \right ) \left ( \frac {64!}{32!^2} \right )^2 \left ( \frac {32!}{16!^2} \right )^4 \left ( \frac {16!}{8!^2} \right )^8 \left ( \frac {8!}{4!^2} \right )^{16} \left ( \frac {4!}{2!^2} \right )^{32} \left ( \frac {2!}{1!^2} \right )^{64} \\ [8pt] = {} & \frac {128!}{64!^2} \frac {64!^2}{32!^4} \frac {32!^4}{16!^8} \frac {16!^8}{8!^{16}} \frac {8!^{16}}{4!^{32}} \frac {4!^{32}}{2!^{64}} \frac {2!^{64}}{1!^{128}} \\ [8pt] ¡= {} & 128! \text (todo lo demás se cancela.)} \end {align*}

---

Sólo por diversión, aquí hay una prueba combinatoria también. Sea $A$ sea un conjunto de tamaño 128, y sea $S$ sea el conjunto de todas las cadenas binarias de longitud $7$ . Contemos el número de biyecciones de $A$ a $S$ .

• Por un lado, $|A| = |S| = 128$ , por lo que hay $128!$ biyecciones de $A$ a $S$ .

• Por otro lado, para construir una biyección, primero elegimos qué elementos de $A$ ir a una cadena que comienza en $0$ y luego elegir qué elementos de $A$ ir a una cadena que comienza en $1$ . Podemos hacerlo en $\binom{128}{64}$ formas. Entonces, entre los elementos que asignamos una cadena que comienza en $0$ debemos dividirlos en cadenas que comienzan en $00$ y las cadenas que comienzan en $01$ ; podemos hacer esto en $\binom{32}{16}$ formas. Del mismo modo, para los elementos asignados a una cadena que comienza en $1$ ; o bien comienzan en $10$ o en $11$ . Y así sucesivamente.

Answer 4

Dividir $128$ artículos por la mitad, y asignar a una de las mitades un $1$ bit en el primer dígito y el otro un $0$ poco. A continuación, vuelve a dividir cada mitad por la mitad, y en cada mitad asigna a un $1$ bit en el segundo dígito y el otro un $0$ poco. Continúe hasta que las mitades estén formadas por elementos individuales. Ahora se ha asignado a cada elemento un número binario de $0$ a $127$ . El lado izquierdo cuenta el número de formas de asignar los números, y el lado derecho cuenta el número de formas de realizar las subdivisiones.