# Number of $n\times n$ matrices with fixed columns sums and only one non-zero elements among each row

I would like to find an explicit, analytical formula that counts the number of $n\times m$ matrices with given sums $c_1, \ldots , c_n$ along the columns and only one non-zero value along each row (but the rows' sums may not be specified).

Do you think an explicit analytical solution can be found?

I need an analytical formula because I then would like to see what a "typical matrix" of this set looks like.

NOTE : The problem can also be thought as a multiset partition problem with constrains. I have a multiset with multiplicities $c_1, \ldots , c_n$ and I want to see what a typical partition looks like when we force the block $i$ of a partition to be a multiset with multiplicity $d_i$ (so only one species for each block of each possible partition).

• Are the matrix entries integers? – Omnomnomnom Aug 27 '18 at 17:54
• yes, all entries are integers – Ninja Warrior Aug 28 '18 at 7:50

The formula is $$\binom{m}{c_1,c_2,\dots,c_n}=\frac{m!}{c_1!c_2!\cdots c_n!}$$ This can be derived as follows. You must choose $c_1$ of the rows to put their ones in the first column. From the remaining $m-c_1$ rows, you must choose $c_2$ rows and put their ones in the second columns, and so on. Therefore, the count is $$\binom{m}{c_1}\binom{m-c_1}{c_2}\binom{m-c_1-c_2}{c_3}\cdots \binom{m-c_1-c_2-\dots-c_{n-1}}{c_n},$$ which simplifies to the formula above.