4
$\begingroup$

I am considering a $3\times 3$ block of pixels where each pixel can be either $0$ or $1$.

How many unique blocks are there if we consider rotations/reflections to be identical?

I believe the answer is $76$, but I am really bad at combinatorics. Below is an image of what I believe is the solution set:

Imgur

$\endgroup$
  • 2
    $\begingroup$ You wrote $9\times9$, but posted a solution set for $3\times3$. What do you really mean? $\endgroup$ – Dario Jan 15 '17 at 20:20
  • $\begingroup$ I meant $3 \text{x} 3$! Somehow I miswrote. $\endgroup$ – user407198 Jan 15 '17 at 20:35
  • $\begingroup$ This MSE link looks like a close match. Adapt and re-use to solve your problem. $\endgroup$ – Marko Riedel Jan 15 '17 at 22:22
  • 3
    $\begingroup$ I get $102$ patterns. There is a diagram at OEIS A054247. It would appear that e.g. you are missing the pattern $010 \times 100 \times 000.$ $\endgroup$ – Marko Riedel Jan 16 '17 at 0:04
  • 1
    $\begingroup$ The image at the OEIS has all of them. I compared the two. $\endgroup$ – Marko Riedel Jan 16 '17 at 3:32
1
$\begingroup$

I would classify all patterns in the following way.
I assume that black pixels are meaningful ($1$), the rest is a background ($0$).

First we see that the lower row in your example is just the negative for the upper row so the total number of patterns = $2 \times $ number for the upper row.

So let's concentrate on the upper row.

Here we have cases where in the $ 3\times{3}$ grid there is no pixels, there is 1 black pixel, there are 2 pixels, 3 pixels and 4 pixels. These cases I denote as #0,..#4. In this grid the central pixel is stabile under rotation and reflection, the remaining $8$ ones make structure which I'll name outer cycle (neighborhood of the central pixel) which generally can be affected by these operations.

0

Evidently $1$ pattern.

Introduction for other cases.

For other cases it is important to notice that we can distinct between patterns with visible central pixel and without it. Patterns with central pixel for #k (denoted as PC) are descended from the lower case #k-1. Patterns without central (denoted as PW) pixel can be classified according to 'distances' between pixels measured on the outer cycle (there are $8$ pixels in this outer cycle, so the sum of number of pixels and distances is always equal to $8$ as it was said). Distances are just empty pixels between elements from the right and left side of the pixel to the nearest pixel - e.g. in the case of two pixels in the outer cycle two numbers can denote a distance.
If a distance is equal to $0$ it means that two pixels are in the one continuous block. These possible distances are listed below in $\{,\}$ brackets for every case. The number of distances in the set $\{,\}$ is equal to the number of pixels in the pattern.

Notice that rotation and reflection doesn't change the set of distances for a given pattern so to use distances for the classification it seems to be a good idea.

1

PW - we have here distance $\{ 7\} $ - there are two distinct patterns for this set of distances (a pixel in the corner of outer cycle and a pixel in the midpoint of outer cycle) as in the drawing in the question
PC - $1$ pattern

Total number $=2+1=3$ patterns.

2

PW -
2 pixels so the sum of distances must be $8-2=6$

distances $\{0,6\}$ - $1$ pattern
$\{1,5\}$ - $2$ patterns
$\{2,4\}$ - $2$ patterns
$\{3,3\}$ - $2$ patterns

PC - $2$ patterns ( based on PW#1)

Total number $= 7+2 =9$

3

PW - 3 pixels so the sum of distances must be $8-3=5$

distances $\{0,0,5\}$ - $2$ patterns
$\{1,1,3 \}$ - $2$ patterns
$ \{1,2,2 \}$ - $2$ patterns
$\{1,0,4 \}$ - $2$ patterns
$ \{3,0,2 \}$ - $2$ patterns

PC - $7$ patterns ( based on PW#2)

Total number $= 10+7=17$

4

PW
4 pixels so the sum of distances must be $8-4=4$

distances $\{4,0,0,0\}$ $1$ pattern
$\{3,0,0,1\}$ $4$ patterns - the only situation for all cases when for a given set of distances we have $4$ patterns not $2$ or $1$.
$\{2,0,0,2\}$ $2$ patterns
$\{2,0,1,1\}$ $2$ patterns
$\{1,1,1, 1 \}$ $2$ patterns

PC $10$ patterns ( based on PW#3)

Total number $=11+10= 21$

Summary

Total sum for the upper row: $1+3+9+17+21=51$

And multiplying by $2$ we receive $2 \times {51} = 102$ patterns.

It's not the same number as you have given, but your visualization of $76$ patterns was very helpful to construct this solution.

$\endgroup$
  • $\begingroup$ @user407198 . Btw, this $3\times{3}$ grid with $9$ possible elements would be very useful for constructing a game of picking up elements from the grid starting from some initial state with the use of minimal number of movements, including rotations but not reflection because it is hard to realize physically. These patterns which you have presented are very inspiring. $\endgroup$ – Widawensen Jan 17 '17 at 8:22
  • $\begingroup$ Neat!$\text{ }$ $\endgroup$ – user407198 Jan 18 '17 at 1:27
  • $\begingroup$ @user407198 This method taking into account 'distances' between pixels on 'outer cycle', with some effort, can be generalized also for grids of greater dimensions $4\times{4}$ or $5\times{5}$. Notice that 'outer cycles' with different radii are combinatorically independent - rotations and reflections don't change assignment of a pixel to the outer cycle with a given radius, If you like my kind of explanation please consider also acceptation of the answer.. $\endgroup$ – Widawensen Jan 18 '17 at 8:12

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.