Given that I have a $3 \times 3$ grid of squares:
$$ \begin{matrix} A & B & C \\ D & E & F \\ G & H & I \\ \end{matrix} $$
I want to know: what are all the possible subsets of this set of squares, excluding square $E$, where each corner square $\{A,C,G,I\}$ can only be included if both of its adjacent squares are also in the subset?
Example: If the subset does not include squares $F$ or $H$, there are only 5 possible subsets of squares: $∅$, $\{B\}$, $\{D\}$, $\{B,D\}$ and $\{A,B,D\}$.
I know that without the adjacency constraint, there would be $(2^8) = 256$ possible subsets. With this constraint, I have iterated the combinations by hand and found $47$, which might be the addition $(25 + 9 + 9 + 4)$ or $(16 + 4 + 12 + 15)$. But I am not satisfied with the hand-iterated result and would like to understand how the constraint modifies the otherwise simple formula to find the number of subsets.
Ultimately, my goal is to create a dictionary of subsets without the adjacency constraint with 47 definitions: one for each subset with the adjacency constraint (invalid corner squares removed). I will want the definitions to be ordered in a way that makes intuitive sense to a non-mathematician, ideally with one or two intuitive sub-categorizations so that all 47 definitions are divided into more manageable chunks rather than being in one big flat list. Therefore I am looking for a way to describe the subsets in such a way that it seems completely obvious that there are 47 of them based on the way they are organized. I am hoping that a better mathematical understanding will help me organize the subsets in such a way.
Simply order the subsets by the number of corner squares they include. Using the symmetries of the square leaves very little work to be done.
0.The sets with no corner squares are the subsets of $\{B,D,F,H\}$, of which there are $16$.
For each corner square, there are precisely four sets containing that corner and no other. That yields another $16$ subsets with precisely one corner square.
For two adjacent corner squares, there are precisely two subsets containg precisely these two corner squares, yielding $8$ subsets. For two opposite corner squares, there is precisely one subset containing these two corner squares, yielding $2$ more subsets. This yields a total of $10$ subsets containing precisely two corner squares.
For any choice of three corner squares, there is only one subset containing all three but not the fourth. That yields $4$ subsets with precisely three corner squares.
There is only one subset containing all corner squares.
This yields a total of $47$ subsets.
Dual to this is ordering the subsets by the number of edge squares they include. You will find yourself distinguishing the same cases and counting the same numbers.