Permutations on a grid with repetition allowed

121 Views Asked by At

I understand how to calculate the number of permutations given a latin grid, but this problem is not that.

Given a $4\times4$ grid, how many unique ways are there to arrange the numbers $1, 2, 3$ and $4$. It doesn’t matter if they repeat. Neither is it necessary for them all to appear. Therefore, a grid filled entirely with $1$'s is allowable.

However, rotations don’t count as unique. Therefore, a grid of fifteen $3$'s with a single $2$ in the $(1,1)$ position is the same as a grid of fifteen $3$'s with a single $2$ in the $(1,4)$ position or $(4,4)$ position or $(4,1)$ position.

BUT mirrored images ARE allowable. So fifteen $3$'s with a single $2$ in the $(2,1)$ position is NOT the same as a grid with fifteen $3$'s and a single $2$ in the $(2,4)$ position. (But due to rotation it would be the same as if the $2$ were in the $(1,3)$ position, the $(3,4)$ position or the $(4,2)$ position.)

1

There are 1 best solutions below

0
On

With no restrictions, there are $4^{16}$ grids. However, any grid with rotational symmetry order $2$ has been counted one too many times, and any grid with rotational symmetry order $4$ has been counted three two many times.

Note that grids with rotational symmetry order $2$ can be defined by a $2 \times 4$ half-grid, giving $4^{8}$ such grids. Note that every grid with rotational symmetry $4$ also gets subtracted once in this way, so we need to subtract them twice more, this time defining them by a $2 \times 2$ quarter-grid, giving $4^4$ such grids.

So the final answer is $4^{16} - 4^8 - 2 \times 4^4$.