I'm not sure how to approach the following problem. Any help would be appreciated!
An nxn square is divided into n^2 unit squares. Each of the (n+1)^2 vertices is to be colored either red or blue. How many different colorings are there such that each unit square has exactly two red vertices?
Note: Two colorings are considered different if at least one vertex is colored differently in the two schemes.
It seems to me that all the configurations of the first column except two are such that the other columns are forced. So that, in most cases, the configuration is entirely given by the first column, and counting configurations boils down to counting configurations of the first column (with a special treatment for the above mentioned two special configurations)
I let you think about it (draw plenty of sketches). This proof scheme would work for a rectangle with m columns and n rows.