Lesson Four: The Power of Diagramming and other Visual Aides

I was looking over some basic combinatorics problems and stumbled upon some very interesting solutions to a few problems. The problems below are not meant to be particularly challenging, but instead are meant to demonstrate the power of diagramming.

Here's the first problem:
How many ways are there to put eight rooks on a chessboard so that they do not attack each other?

For those of you not familiar with chess, a chessboard is an 8x8 grid, and rooks attack each other by sharing a row or column with another rook.

To begin with, the rook can be placed in any of eight columns. The second rook can be placed in any of seven columns. This continues on until the rook is forced to be placed in the final column. The answer is 8! (or 8x7x6x5x4x3x2x1). Factorial notation is much simpler to use and occurs frequently in combinatorics problems...so I will use it from now on.

Easy enough, right?

How about this problem:

There are N booys and N girls in a dance class. How many ways are there to arrange them in pairs for a dance?









**** Try it! ****








This problem, as it turns out, is quite similar to the problem above. In fact, the same image of a chess board can be used to help us solve this problem.




Instead of chess pieces, we can think of each boy as a numbered row (1 through 8) and each girl as a column (A through H). See what I'm getting at?









Let's say that each couple placed a dot where their respective column and row met. Assuming a monogamous dance, each row and column can only have one such dot because each person is dancing with EXACTLY one other person. Then, this problem becomes exactly like the rook problem! So...for N girls and N boys we have N! possible pairings.

Can you think of other settings for this type of problem?

I will post a couple in the comments section that I thought of :)

Another simple combinatorics problem that amused me was the following:

There are 18 ping pong players at a ping pong tournament. The tournament is a round robin (where every player plays every other player exactly once). How many matches are played?

Initially, I thought about adding each player's matches in subsequent order. The first player plays 17 unique matches, the second player plays 17 matches, but he plays one match with the first player, making 16 unique matches. This pattern continues until you reach the last player who plays no unique matches.

Instead...the book hinted at representing all the players on an N-gon, or a polygon with N vertices. Using this method, we choose any vertice for one of our 18 players. We then know our one player plays 17 other matches. So we would have 18*17 for each player's 17 other diagonals or matches. This number, however, is incorrect, as it counts the match A plays with B and B plays with A as unique. Therefore, we divide by two. 18*17/2, or 153 total matches.

This blog post provides an excellet segue into the importance of generality, which will be the topic of my next blog post.