1

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?

Mathejunior
  • 3,344
  • @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 :) – Mathejunior Dec 09 '18 at 12:09
  • Is there a reason you expect to find a recursive solution? – Christoph Dec 09 '18 at 12:14
  • @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 – Mathejunior Dec 09 '18 at 12:18

0 Answers0