Combinatorics is the mathematical study of how we count stuff.  In your Battleship homework, you were faced with the challenge of counting the number of ways you can place a 2x1 ship (the destroyer) on a 10x10 board, as well as a 3x1 ship (the submarine or the cruiser) on a 10x10 board.  Even more challenging, you were tasked with counting the number of ways that you could place both a 2x1 and a 3x1 on a 10x10 board.  Whether you did so explicitly or subconsciously, you likely had to use some basic mathematical tools which come from combinatorics in order to achieve your goal.

You also studied the most likely spots that you would find a 2x1 placed on a 3x3 board.  In order to get the associated probabilities, we had to consider (1) the total number of different possible positions for that 2x1 ship and (2) the frequency that those positions included a certain cell.  Certainly the calculations would become much more complicated on the full-sized 10x10 board with more than one ship!  In the image above, your professor Riley used a computer to randomly place 100000 full battleship fleets and recorded the frequency that each particular space was occupied.  Again we see that randomly placed ships have a tendency to find their way toward the center of the board.  

Using symmetry

One tool in our mathematical toolbox that we use very often is symmetry.  Take for example the problem of placing a single 2x1 ship on a 10x10 board.

  • By symmetry, the number of ways we can place it vertically is the same as the number of ways we can place it horizontally.  Thus we need only count the horizontal placements, and then multiply our answer by 2.
  • By symmetry, the number of horizontal placements will be the same for any row, so we need only count the number of horizontal placements in a single row, and then multiply that answer by the number of rows 10.
  • It's easy to count the number of horizontal placements in a single row: its 9

Putting this all together, we get that the total number of placements is

LaTeX: 9\times10\times2\:=\:180.Do you see how we reduced the problem again and again by symmetry?

The same sort of calculations will work for placing a 3x1 ship.  The only thing which changes will be the number of ways we can place it horizontally in a single row (which is 8) so the total number of placements is

LaTeX: 8\times10\times2=160

Other combinatorial goodies

The toughest problem on the homework was figuring out how to place a 3x1 and a 2x1 together on the board.  To use this, we can leverage some more basic mathematical ideas having to do with counting.

One useful idea is a rule for combinations:

  • If I have a collection of LaTeX: m different cards and a collection of LaTeX: n different marbles, then the number of possible ways of picking a combination consisting of one card and one marble is LaTeX: m\cdot n

Of course, we can apply this to more than cards and marbles!  Instead of cards, we could think of the was that we can place the 3x1 ship and instead of marbles we can think of the number of ways we can place the 2x1 ship.  Then the number of ways that we can choose a combination of placing the 3x1 ship and the 2x1 ship.  Our rule above then suggests this is

LaTeX: 180\times160\:=\:28800\:\:\text{different ways.}

However, this isn't quite right because where we place our 3x1 ship restricts where we can place our 2x1 ship!

So to get our correct answer, we need to subtract all of the placement combinations that we just counted which were illegal because the ships overlapped.  Thus we have reduced the problem to counting the number of ways we can place the 3x1 on the board and the 2x1 on the board in an overlapping way.

 

Once we place the 3x1 down on the board, to place our 2x1 illegally we can either have it completely on top of our 3x1 in 2 different ways, or else hang over by one into an adjacent cell.  Thus the number of illegal placements will depend on the number of adjacent cells, which varies depending on whether our 3x1 is on the boarder of the board or not!

  • CASE 1: our 3x1 is not on the boarder of the board.  Then we can place the 2x1 in 10 different ways illegally.
  • CASE 2: our 3x1 is lying broad-side to the edge of the board, but not in a corner.  Then we can place the 2x1 in 7 different ways illegally
  • CASE 3: our 3x1 is on the side of the board at its tip. Then we can place the 2x1 in 9 different ways
  • CASE 4: our 3x1 is in a corner.  Then we can place the 2x1 in 6 different ways.

How many ways can CASE 1 happen?  That's the same as the number of ways we can place a 3x3 ship into a 8x8 board, which is 6x8x2=96.

How many ways can CASE 2 happen?  By symmetry, we just have to check out one side and then multiply by 4 for the number of sides.  Thus the answer is 6x4=24 ways.

How many ways can CASE 3 happen?  By symmetry, we just have to check out one side and then multiply by 4 for the number of sides.  So it's 8x4=32 ways.

How many ways can CASE 4 happen?  Two different ways in each corner with four corners means 2x4=8 ways.

Thus the number of illegal cases is

 

LaTeX: \left(96\cdot10\right)+\left(24\cdot7\right)+\left(32\cdot9\right)+\left(8\cdot6\right)\:=\:1464

This gives us the total number of legal board arrangements:

LaTeX: 28800-1464=27336