0
$\begingroup$

Problem Given a $m*n$ matrix, $m\le n$ calculate how many configurations satisfies the following three constraints.

  1. Each cell is either 0 or 1.
  2. For each column, there is exactly one cell be 1.
  3. For the $i$~th row, there should be no more than $f(i)$ 1s. $f(i)$ is a function.

This seems like an exercise, I do not know whether there is a name on it. Any reference is appreciated.

I want to derive a formula for it. It seems like a dynamic programming is available.

Example. $n=m=3$, $f(1)=1, f(2)=0, f(3)=3$. Then the answer is 3.

This problem was asked at TCS@SE first, and was suggested to migrate to Math@SE.

1 Answers 1

1

Another way of saying this: you have $f \in {\mathbb N}_0^m$, and want $L(f)$ which is the number of $v \in \{1,\ldots,m\}^n$ such that $|\{i: v_i = j\}| \le f_j$ for each $j$. Of course $\sum_{i=1}^m f_i \ge n$ in order for there to be any of these. It would be simpler to count the number if you required $= f_j$ rather than $\le f_j$, where $\sum_{i=1}^m f_i = n$: then it would be $N(f) = \frac{n!}{f_1! f_2! \ldots f_j!}$. For your problem, the result will be $L(f) = \sum_h N(h)$ where the sum is over all $h \in {\mathbb N}_0^m$ with $h \le f$ and $\sum_i h_i = n$. This can be written as $ L(f) = \sum_{h_1 = a_1}^{b_1} \sum_{h_2 = a_2}^{b_2} \ldots \sum_{h_m = a_m}^{b_m} \frac{n!}{h_1! h_2! \ldots h_m!}$ where $a_j = \max\left( 0, n - \sum_{k=1}^{j-1} h_k - \sum_{k=j+1}^m f_k \right)$ and $b_j = \min\left(f_j, n - \sum_{k=1}^{j-1} h_k\right)$