An square is subdivided into unit squares like a chessboard. Some of these unit squares are black, all others are white. Such a configuration is called spotty if it contains at least two black unit squares each of which shares an edge with a white unit square to its left or above it.
How many spotty configurations are there?
Solution
We will use coordinates , , to address the vertices of the small squares so that is the bottom left corner. There are ways to make each of the squares either black or white. Each such 'colouring' will be called a configuration.
Let a spot be a black square which shares an edge with a white square to its left or above it. We will first count the number of configurations with no spots. Note that in this case, if a square is black, then the rectangle whose diagonal connects that square with the upper left corner is entirely black. Thus the configuration will contain a connected black area in the upper left corner bounded by a wall in the shape of an Up-and-Right path connecting the corner with the corner .
Such paths can be represented by a string consisting of U-s and R-s.
There are such strings, and so spot-free configurations.
We next count the configurations containing exactly one spot.
The spot of such a configuration cannot have a black neighbour to the right and below, because this would imply that all squares above and to the left need to be black as well.
By symmetry, it suffices to count those configurations where the single spot does not have a black neighbour to the right.
If it also does not have a black neighbour below, after removing the spot, we obtain a spot-free configuration. If it has a black neighbour below, the spot will be the top square of a column of black squares. As only the top one of them is a spot, this column must be adjacent to a vertical wall of the spot-free configuration obtained by removing these squares.

This vertical wall segment gives options for placing a single spot in the grey rectangle to its right. Only the top left corner of this rectangle wouldn't give a spot.
The other option would be to add a column of black squares so that the topmost of them is a spot. As seen above, these squares can only be situated directly next to the wall. There are ways doing so, because the column is determined by selecting its top square and its bottom square, and there are possible positions for these black squares in order to get a spot at the top.
The wall segment considered can be completed to an Up-and-Right path in
ways. The two binomial coefficients count the Up-and-Right paths in the cross-hatched rectangles above. When we take the first factor to be . Adding up the contributions from all such wall segments, we get a total of
-spotted configurations. Note that the factor in the second line accounts for the symmetry mentioned above.
For fixed , the factors in the first and second line can be organized carefully in a table with one row for each value of and one column for each value of , which allows one to do the sums in an orderly way, leading to a total of
-spotted configurations. The number of spotty configurations is therefore
In the above count of -spotted configurations, one can use the following "generalized hockey stick" formula to simplify the sums: