In how many ways can $5$ P's be placed in $16$ identical squares formed by a $4$ × $4$ grid, such that each row has at least one P?
The number of ways of introducing first P will be: $16$ ( let us say the chosen cell is in first row)
Next P has $12$ cells to go in. (let us put that in $2$nd row)
$3$rd P has $8$ cells. (put that in $3$rd row)
$4$th P has $4$ cells. (put that in $4$th row)
And because $4$ cells out of $16$ have been full now, so the final P has $12$ cells to go in.
Making the total number of ways to place = $16 \cdot 12 \cdot 8 \cdot 4 \cdot 12 = 73728$ ways.
Where am I going wrong?
Best Answer
Please note all $P$'s are identical so if there was no restriction, all you would do is to choose $5$ cells from $16$ cells, which is $ \displaystyle {16 \choose 5}$.
As there are $5$ P's and each row must have at least one $P$, one of the rows will have two $P$'s and rest three rows will have one $P$ each.
For each row with one $P$, there are $4$ columns to choose from and for the row with two $P$, there are $4 \choose 2 ~ $ ways to choose two columns. Also there are $4$ ways to choose the row with two $P$'s.
That leads to $ ~ \displaystyle 4^4 \cdot {4 \choose 2} ~$ ways.