The board is 4x4 and there are three types of battleships: 3x1, 2x1, 1x1. One for each type. How many total placements are possible? Notice, the ships cannot overlap and we must use all ships.
(there is one previous thread about this topic but seems no one actually got the right answer).
Here is my approach:
- Calculate the total number (sample space) which is 11 (1 * 3 ship) * 24 (1 * 2 ship) * 16 (1 x 1 ship)
- Subtract the overlap -> which is quite challenging to do since the discussing all cases using inclusion-exclusion principle is very time consuming and although I do believe one can get the correct solution, it is more suitable to use computer simulation.
How can we do it by hand?
I assume overlap is the actual overlap and ships are allowed to touch. If so, here is a suggested count.
There are 16 positions for 1 * 3 ship, 24 for 1 * 2, and 16 for 1 * 1.
Note that after placing 1 * 3 and 1 * 2 ships, the number of ways to place 1 * 1 is 16-5=11.
Among 16 positions of 1 * 3, exactly 8 are sharing a corner with the boundary of $4\times4$ board and 8 do not.
Each of those 8 positions for 1 * 3 that share the corner is blocking exactly 6 positions for 1 * 2. So if 1 * 3 ship is in the corner, we have 24-6=18 possible valid position for 1 * 2.
Each of those 8 positions for 1 * 3 that do not share the corner is blocking exactly 9 positions for 1 * 2. So if 1 * 3 ship is not in the corner, we have 24-9=15 possible position for 1 * 2.
Since every valid choice for 1 * 3 and 1 * 2 can be finished with 11 valid choices for 1 * 1, the answer is (assuming no arithmetic mistake is made) $$(8 \cdot 18+8 \cdot 15) \cdot 11.$$
Similar symmetry could be used if the ships are not allowed to share an edge of a grid, or even if they are not allowed to touch by the corner.