Counting the possible number of shapes.

[John_Andrews0]

Hello,

I have an 8 by 8 binary matrix. Define a shape as a cluster of 1's. For instance, consider the following sample:

0 [COLOR="Red"]1[/COLOR] 0 0 0 0 0 0
0 [COLOR="Red"]1[/COLOR] 0 0 0 0 0 0
0 0 [COLOR="Red"]1 1[/COLOR] 0 0 0 0
0 0 0 [COLOR="Red"]1[/COLOR] 0 0 0 [COLOR="Blue"]1[/COLOR]
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 [COLOR="DarkOliveGreen"]1 1[/COLOR] 0
0 0 0 0 0 [COLOR="DarkOliveGreen"]1 1[/COLOR] 0

As you can see, there are three shapes in the above binary matrix. Given the constraint that the matrix cannot have more than 32 ones inside, then how many possible shapes can I get in an 8 by 8 matrix? The shapes which are similar if you rotate them in any direction are considered as one shape...

Thank you!

 

[pat_connell]

There are technically an infinite number of possible shapes that can be created in an 8 by 8 matrix, but the total number of distinct shapes is limited by the 32 ones constraint. Because there are 64 squares in the matrix, and each one can contain either a 0 or a 1, this gives a total of 2^64 possible combinations. However, since you have a constraint that the matrix cannot have more than 32 ones, then this limits the total possible shapes to 2^32 (or 4,294,967,296).