Contamos con una red de $n \times m$. De cuántas maneras poner $p$ puntos, para que cada columna y fila tenían al menos un punto.

Question

Tenemos una $n \times m$ cuadrícula. De cuántas maneras diferentes podemos poner $p$ monedas en él, de modo que cada moneda estaba en una única celda en la cuadrícula, y cada columna de la cuadrícula y cada fila tenía al menos una moneda.

Bueno, yo traté de solucionar el problema mediante la inclusión-exclusión en el principio:

Todas las formas de poner $p$ de los puntos en una cuadrícula: ${{n \cdot m}\choose{p}}$

Luego nos restan todas las combinaciones incorrectas.

Deje $A$- conjunto de todos los arreglos que dejar algunos de los números de filas vacías, $B$ conjunto de todos los arreglos que dejar algunos de los números de las columnas vacías.

A continuación, las combinaciones incorrectas- $|A \cup B|=|A|+|B|-|A \cap B|$.

$|A|=\sum\limits_{k=1}^n (-1)^{k+1}{{n}\choose{k}}{{(n-k) \cdot m}\choose{p}}$ - elegimos $k$ $n$ filas que están vacíos y llenar el resto de $(n-k)$ filas

$|B|=\sum\limits_{k=1}^m (-1)^{k+1}{{m}\choose{k}}{{n \cdot (m-k)}\choose{p}}$ - similar a la anterior.

$|A \cap B|=\sum\limits_{k=1}^n (-1)^{k+1}{{n}\choose{k}}\sum\limits_{z=1}^m (-1)^{z+1}{{m}\choose{z}}{{n - k*m-(n-k)*z}\choose{p}}$ - en primer lugar, elegir la cantidad de filas que queremos vacío, entonces podemos elegir la cantidad de filas, entonces se cuenta el número de forma de que las columnas pueden estar defectuosos, y poner puntos en el resto de lugares..

Answer 1

Una simplificación: nosotros podemos incluir-excluir filas de todo-$i$ $0$ y $j$ % todo $0$columnas de una sola vez. Esto da el número $$\sum_{i=0}^n \sum_{j=0}^m (-1)^{i+j} \binom{n}{i} \binom{m}{j} \binom{(n-i)(m-j)}{p}.$ $

(Esta fórmula fue verificado comptuationally $n \leq 4$, $m \leq 5$ y $p \in \{1,2,\ldots,nm\}$.)