Given $N \times M$ binary matrices (matrix containing only $0$'s and $1$'s), two matrices are called identical if one can be converted into the other by first permuting the $N$ rows and then permuting the $M$ columns of the resulting matrix. Find the number of non-identical matrices.

I'm not really sure of how to begin this problem either. It's some recursion (or composition of more than one recursion) and I can't figure that out. May I get some valid hints?


marked as duplicate by Christoph, Lord Shark the Unknown, user10354138, Shailesh, Brahadeesh Dec 11 '18 at 8:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @Christoph okay, but I'm more interested in the recursion and not a solution using some kind of generating functions. Also, one of the solutions there uses some idea related to symmetric groups and I'm not aware of all those. The other answer which has a proof using Polya enumeration is not something I asked for as that does not help with a recursion. Thank you :) $\endgroup$ – Mathejunior Dec 9 '18 at 12:09
  • $\begingroup$ Is there a reason you expect to find a recursive solution? $\endgroup$ – Christoph Dec 9 '18 at 12:14
  • $\begingroup$ @Christoph yes, because I found it on a coding platform and it has to be done using dynamic programming which includes recursion. And so it is supposed to have a recursion. Also, I couldn't find a solution to this as a result of which I wrote it here $\endgroup$ – Mathejunior Dec 9 '18 at 12:18

Browse other questions tagged or ask your own question.