¿De cuántas formas se pueden permutar las filas de una matriz sin que ninguna columna sea cero, y por qué la respuesta es una función hipergeométrica?

Question

Estoy buscando una explicación intuitiva para la respuesta que he encontrado a esta pregunta que se me ha ocurrido:

Tengo una matriz B con $m$ filas y $k$ columnas, con entradas tomadas del conjunto ${0,1, \ldots, n}$ (pero puede ser cualquier conjunto de $n+1 $ símbolos en lugar de números). Los números pueden repetirse.

Puedo permutar cualquiera de las filas, es decir, intercambiar cualquier entrada con cualquier entrada de la misma fila, pero no con una entrada de otra fila. La única restricción es que no puedo tener ninguna columna que contenga sólo ceros.

He aquí algunas anotaciones. Sea $z_r$ contar el número de ceros del $r$ 'th row. Además, para $c=1, \ldots n$ deje $T_{rc}$ contar el número de $c$ 's en el $r$ 'th row.

Sin la restricción, es fácil ver que el número de permutaciones es $$P = \frac{k!^m}{\prod_{r=1}^m \prod_{c=0}^n T_{rc}!}.$$

Aparentemente, la respuesta final es multiplicar este número por la siguiente función hipergeométrica:

$$_mF_{m-1} [-z_1 -z_2 \ldots -z_m; -k -k \ldots -k](1).$$

Encontré esto a través de un enfoque de fuerza bruta y algunas simplificaciones con Mathematica, pero realmente no entiendo por qué debería ser cierto. También se puede expresar como una suma finita de factoriales decrecientes.

¿Existe alguna propiedad combinatoria de las funciones hipergeométricas que lo explique? ¿O hay una forma más sencilla de expresar la respuesta? ¿O quizá mi problema es un caso especial de un problema más general?

Answer 1

Había un pregunta muy similar hace un rato. Me encontré con una solución más general cuando se trabaja en barajado de secuencias .

Una versión más general de su problema puede surgir como un iterado distribución hipergeométrica : let $X_0=n_0$ y luego $X_r\sim\text{Hypergeom}(X_{r-1},n_r,N_r)$ .

Básicamente, su problema es que en cada uno de los $m$ filas, $z_r$ fuera del $k$ las columnas se eligen al azar: es decir, los ceros. Sea $X$ sea el número de columnas recogidas en todas las filas.

Calculemos el número esperado de formas de elegir $q$ fuera del $X$ columnas: ie $q$ columnas todo cero.

En primer lugar, hay $\binom{k}{q}$ maneras de elegir $q$ columnas. Ahora, supongamos que miramos una selección de $q$ columnas. En fila $r$ la posibilidad de incluir a todos $q$ entre los $z_r$ recogido es $\binom{k-q}{z_r-q}/\binom{k}{z_r}$ . Por lo tanto, el número esperado de formas de elegir $q$ fuera del $X$ columnas es $$ \text{E}\left[\binom{X}{q}\right] = \binom{k}{q}\cdot\prod_{r=1}^m \frac{\binom{k-q}{z_r-q}}{\binom{k}{z_r}} = \binom{k}{q}\cdot\prod_{r=1}^m \frac{\binom{z_r}{q}}{\binom{k}{q}}. $$

Ahora, expresemos la $\text{E}[\binom{X}{q}$ una diferente utilizando la función generadora de probabilidad $$ P_X(t) = \text{E}\left[t^X\right] = \sum_{i=0}^k \Pr[X=i]\, t^i. $$ Esto hace que $$ P_X(1+u) = \text{E}\left[(1+u)^X\right] = \sum_{q=0}^k \text{E}\left[\binom{X}{q}\right]\, u^q = \sum_{q=0}^k \frac{\prod_{r=1}^m z_r!/(z_r-q)!}{[k!/(k-q)!]^{m-1}} \cdot\frac{u^q}{q!}\\ ={}_mF_{m-1}(-z_1,\ldots,-z_m;-k,\ldots,-k;-u). $$ Ahora, puede recuperar todos $P_X(t)$ estableciendo $u=t-1$ y haciendo una ampliación de potencia. En concreto, la probabilidad de que no queden columnas, $X=0$ se obtiene fijando $t=0$ o $u=-1$ que da tu resultado.