6 votos

Inclusión – exclusión: Matrices

Deje $A$ $n\times n$ matriz que contiene todos los números de $1,2,\ldots,n^2$ (cada uno aparece una vez). Contar el número de $n \times n$ matrices $B$ que contienen todos los números de $1,2,\ldots,n^2$ y no tienen ninguna fila idénticos a algunos de fila en $A$, y no tienen ninguna columna idéntica a la de alguna columna en $A$.

He marcado $R_i=\{\text{all the matrices with row }i\text{ identical to some row in }A\}$, $C_i=\{\text{all the matrices with column }i\text{ identical to some column in }A\}$, y dijo que

$$\left|\bigcap_{i\in I} R_i\right|=\left|\bigcap_{i\in I} C_i\right|={n \choose |I|}\big(n^2-|I|n\big)!|I|!$$

y

$$\left|\bigcap_{i\in I} R_i\cap\bigcap_{j\in J} C_j\right|=\left(n^2-(|I|+|J|)n+|I||J|\right)!\;.$$

Por la Inclusión–exclusión principio, recibí esta respuesta:

$$(n^2)!+\sum_{k=1}^{2n}(-1)^k\left[2{n \choose k}^2k!(n^2-kn)!+ \sum_{i=1}^{k-1}{n \choose i}{n \choose k-i}\big(n^2-kn+i(k-i)\big)!\right]\;.$$

Es esto correcto? Hay otra manera? Gracias

1voto

JiminyCricket Puntos 143

Ya que todos mis errores y tu un error se han corregido entretanto, no quedo mucho que para decir aquí salvo que creo que el Conde ahora es correcta.

1voto

Marko Riedel Puntos 19255

Aquí es un enfoque ligeramente diferente. Para los nodos del poset subyacente de inclusión-exclusión vamos a utilizar pares de $(S,T)$ con $S\subseteq [n]$ $T\subseteq [n]$ , de modo que $(S,T)\ne (\emptyset, \emptyset)$ where $S$ gives the rows that agree with some row of $$ y $T$ las columnas. Ahora bien, hay varias posibilidades. Nota que las filas y columnas de $A$ son todos mutuamente distintas. Si $T$ es vacía, pero no $S$ elegimos el $|S|$ filas y puede permutar. Mismo si $S$ está vacía, pero no $T.$ Si no está vacía, sólo hay uno posible cesión a saber, una coincidencia exacta de las filas correspondientes y columnas de $A.$ Nota de que en el segundo caso hemos utilizado $n(|S|+|T|)- |S|\times|T|$ elementos. Por lo tanto, obtener por inclusión-exclusión

$$\sum_{S\ne\emptyset} (-1)^{|C|} {n\elegir la |S|}|S|! (n^2-|S|n)! + \sum_{T\ne\emptyset} (-1)^{|C|} {n\elegir |T|}|T|! (n^2-|T|n)! \\ + \sum_{S\ne\emptyset, T\ne \emptyset} (-1)^{|S|+|T|} (n^2 - n(|S|+|T|) + |S|\|T|)!.$$

Ahora, en este punto tenemos que calcular el peso de una configuración que tiene exactamente $p$ filas $A$ $q$ columnas. Con ninguno de estos vacíos tenemos

$$\sum_{p'=1}^p {p\elegir p'} (-1)^{p'} + \sum_{q'=1}^p {q\elegir q'} (-1)^{q'} + \sum_{p'=1}^p \sum_{q'=1}^q {p\elegir p'} {q\elegir q'} (-1)^{p'+q'} \\ = -1-1+1 = -1.$$

Con $T$ vacío (el mismo con $S$ vacío)

$$\sum_{p'=1}^p {p\choose p'} (-1)^{p'} = -1.$$

Hemos comprobado que el peso es $-1$ en todos los casos y, por tanto, la la respuesta está dada por

$$(n^2)! + 2\sum_{k=1}^n {n\elegir k}^2 (-1)^k \times k! \times (n^2-kn)! \\ + \sum_{k=1}^n \sum_{j=1}^n {n\elegir k} {n\elegir j} (-1)^{k+j} (n^2-n(k+j)+kj)!.$$

Esto va a producir la secuencia

$$0, 13, 350314, 20907473410813, 15511088399276664432001386, \\ 371993307691696427796897697438711091311473, \\ 608281863896576961368925279207011528484342192328937893038299066, \ldots $$

El Arce código para esto es la siguiente (advertencia, el total de la enumeración solo para $n=2$$n=3$)

con(planta);

Q :=
proc(n)
opción de recordar;
local de S, T, res, todos, p, q;

 res := 0; todas := powerset(n);

 para S en todos lo hacen
 para T en todos lo hacen
 p := nops(S); p := nops(T);

 si p = 0 y q = 0, entonces
siguiente;
 elif q = 0, entonces
 res := res +
(-1)^p*binomial(n,p)*p!*(n^2-p*n)!;
 elif p = 0,
 res := res +
(-1)^q*binomial(n,p)*q!*(n^2-q*n)!;
otra cosa
 res := res +
(-1)^(p+q)*(n^2-((p+q)*n-p*q))!;
fi;
od;
od;

 ((n^2)!) + res;
end;

X :=
proc(n)
opción de recordar;
local de perm, res, pos, filas, columnas, srcrows, srccols;

 res := 0;

 srcrows :=
 {seq([seq(p*n+p+1, q=0..n-1)], p=0..n-1)};

 srccols :=
 {seq([seq(p*n+p+1, p=0..n-1)], p=0..n-1)};

 perm := firstperm(n^2);

 mientras que el tipo(perm, `lista`) 

 filas :=
 {seq([seq(perm[p*n+p+1], q=0..n-1)], p=0..n-1)};

 cols :=
 {seq([seq(perm[p*n+p+1], p=0..n-1)], p=0..n-1)};

 si nops(filas se cruzan srcrows) = 0 y
 nops(cols cruzan srccols) = 0, entonces
 res := res + 1;
fi;

 perm := nextperm(perm);
od;

res;
end;

P :=
proc(n)
 (n^2)! + 2*agregar(binomial(n,k)^2*(-1)^k*k!*(n^2-k*n)!,
k=1..n)
 + agregar(add((-1)^(k+j)*binomial(n,k)*binomial(n,j)
 *(n^2-n*(k+j)+k*j)!, j=1..n),
k=1..n);
end;

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X