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

  • 3
    $\begingroup$ Are the matrix entries integers? $\endgroup$ – Omnomnomnom Aug 27 '18 at 17:54
  • $\begingroup$ yes, all entries are integers $\endgroup$ – 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.

  • $\begingroup$ I don't think the multinomial is the proper answer. This coefficient is concerned with distinguishable objects into distinguishable bins. Here we have distinguishable groups of indistinguishable objects (within the group) in distinguishable bins. $\endgroup$ – Ninja Warrior Aug 28 '18 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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