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.
This is an interesting problem. My suggestion would be to look at the first column, and to wonder if the positions of the red vertices in this column force the positions of the red vertices in the second column. (For instance, if the first two vertices of the first column are red, the first two vertices of the second column have to be blue)
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.