Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.