Mathematics desk
< July 14	<< Jun \| July \| Aug >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 15

count of MxN legal counterchanged grids?

For an M by N grid of 0s and ls (of which there are 2^(M*N)), define a legal counterchanged grid if it can be formed by inverting a series of entire rows and/or columns. It would seem to me the entire grid can be derived from the values of a single row and a single column and as such, the number of legal grids would be 2^(M+N-1), is this correct?Naraht (talk) 16:35, 15 July 2014 (UTC)[reply]

Just trying to understand the Q here. Are you saying you can invert each column and row as many times as you want, in any order, or only once ? StuRat (talk) 18:14, 15 July 2014 (UTC)[reply]

As many times in any order.Naraht (talk) 18:54, 15 July 2014 (UTC)[reply]

Yes, that sounds correct to me, assuming I understand your description. If a row is defined, then it will have to be either inverted or not when it is copied to each other row, and the decision is based on the values in the column you've defined. There are other configurations that would uniquely identify a grid, not just a row and column, but intuitively it seems that M+N-1 is the minimum number of values that must be fixed. Katie R (talk) 18:46, 15 July 2014 (UTC)[reply]

The question of how many possible sets of M+N-1 entries uniquely define a valid counterchange is a different, also interesting question.Naraht (talk) 18:54, 15 July 2014 (UTC)[reply]

Apparently the answer to this is OEIS: A072590. --RDBury (talk) 21:03, 16 July 2014 (UTC)[reply]

Nice find! It certainly does seem like this problem transforms beautifully. Each spanning tree uniquely describes a chain of reasoning to deduce the M+N-1 entries in a specific row and column, and each chain of reasoning uniquely identifies the set of entries that it starts from. Katie R (talk) 14:04, 17 July 2014 (UTC)[reply]