This post is inspired by the A collection of grid counting problems. The entire wordpress page is a great read and I thoroughly enjoy it every time I visit.
In Example 5 of the quoted page, the author discusses the number of ways of coloring a $n \times n$ grid in which every row and every column has exactly two black squares. In the example that's immediately next, he discusses a counting problem that uses one of favorite results in combinatorics - the Burnside's Lemma.
That got me thinking about the number of unique (upto rotations and reflections) colorings of a $2n \times 2n$ grid with exactly two black squares in each row and column.
We'll also be using Burnside's lemma for this task. We'll be considering the eight symmetries of the square and count how many colorings are fixed by each of these symmetries. We'll progressing on the increasing order of difficulty. Let's begin.
Identity - Let $t'_n$ denote total number of such colorings on an $n \times n$ grid. This is essentially what the wordpress page was doing. In fact we have A001499 that gives us a recurrence. With $t'_0=1$, we have
$t'_n=n(n-1)t'_{n-1}+\frac{1}{2}n(n-1)^2t'_{n-2}$
As we are only interested in $2n \times 2n$ grid, let's define $t_n=t'_{2n}$. With $t_0=1$, this follows the recurrence,
$\displaystyle t_n=\frac{n(2n-1)^2}{2n-3}(8n^2-16n+7)t_{n-1}-2n(n-1)^2(2n-1)^2(2n-3)t_{n-2}$
(or)
$\displaystyle \frac{t_n}{2n-1}=n(2n-1)(8n^2-16n+7)\frac{t_{n-1}}{2n-3}-2n(n-1)^2(2n-1)(2n-3)(2n-5)\frac{t_{n-2}}{2n-5}$
Diagonal (Anti-Diagonal) symmetry - Let $d'_n$ denote the required colorings that are symmetric along the main diagonal. Again, we have A000986 that gives us the following recurrence. Starting with $d'_0=1$,
$d'_n=2(n-1)d'_{n-1}-(n-1)(n-3)d'_{n-2}-\frac{1}{2}(n-1)(n-2)(n-3)d'_{n-4}$
Again, let's define $d_n=d'_{2n}$ which is the number of required colorings with diagonal (anti-diagonal) symmetry in a $2n \times 2n$ grid. With $d_0=1$,
$\displaystyle d_n=\frac{2n-1}{2n-3}(8n^2-16n+7)d_{n-1}-\frac{(n-1)(2n-1)}{2n-5}(16n^3-104n^2+230n-173)d_{n-2}-2(n-1)(n-2)(2n-1)(8n^2-38n+41)d_{n-3}-2(n-1)(n-2)(n-3)(2n-1)(2n-3)(2n-7)d_{n-4}$
(or)
$\displaystyle \frac{d_n}{2n-1}=(8n^2-16n+7)\frac{d_{n-1}}{2n-3}-(n-1)(16n^3-104n^2+230n-173)\frac{d_{n-2}}{2n-5}-2(n-1)(n-2)(2n-7)(8n^2-38n+41)\frac{d_{n-3}}{2n-7}-2(n-1)(n-2)(n-3)(2n-3)(2n-7)(2n-9)\frac{d_{n-4}}{2n-9}$
Horizontal (Vertical) reflection - Let $r_n$ denote the number of colorings that are fixed by Horizontal reflection on a $2n \times 2n$ grid. As we need the grid to be the same after reflecting it horizontally (vertically), we only have to fill up the top $n \times 2n$ grid. We have to make sure that each row has exactly two black squares and each column has exactly one black square in the $n \times 2n$ grid.
Proceeding in the same way as in the wordpress page, we can see that,
$\begin{align}
r_n &= [x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{i=1}^n\prod_{j=1}^{2n}(1+x_iy_j)\\
&= [x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{j=1}^{2n}(1+(x_1+x_2+\cdots+x_n)y_j+O(y_j^2))\\
&= [x_1^2x_2^2\cdots x_n^2](x_1+x_2+\cdots+x_n)^{2n}=2^{-n}(2n)!\\
\end{align}$
So, we have the recurrence $r_n=n(2n-1)r_{n-1}$ with $r_0=1$.
180 deg. rotation symmetry - Let $f_n$ denote the number of colorings of a $2n \times 2n$ grid that are fixed by rotating the grid by 180 degrees. Again like the previous case, we only have to fill up the top $n \times 2n$ grid. We still make sure that each row has exactly two black squares but unlike the previous case, we need to ensure that the total number of black squares in the $j$-th column and $(2n+1-j)$-th column is two.
$\begin{align}
f_n&=[x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{i=1}^n\prod_{j=1}^{2n}(1+x_iy_j)\\
&=[x_1^2x_2^2\cdots x_n^2t_1^2t_2^2\cdots t_n^2]\prod_{i=1}^n\prod_{j=1}^n(1+x_it_j)^2\\
&=[x_1^2x_2^2\cdots x_n^2t_1^2t_2^2\cdots t_n^2]\prod_{j=1}^n(1+(x_1+x_2+\cdots +x_n)t_j+(x_1x_2+x_2x_3+\cdots+x_{n-1}x_n)t_j^2+O(t_j^3))^2\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\Biggl(\biggl(\sum_{i=1}^n x_i\biggl)^2+2\sum_{1\leq i<j\leq n} x_ix_j\Biggl)^n\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\Biggl(2\biggl(\sum_{i=1}^n x_i\biggl)^2-\sum_{i=1}^n x_i^2\Biggl)^n\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\sum_{k=0}^n(-1)^k\binom{n}{k}\biggl(\sum_{i=1}^n x_i^2\biggl)^k 2^{n-k}\biggl(\sum_{i=1}^n x_i\biggl)^{2(n-k)}\\
&=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{n!}{(n-k)!} 2^{n-k}\frac{(2n-2k)!}{2^{n-k}}\\
&=\displaystyle\sum_{k=0}^n(-1)^k \binom{n}{k}^2k!(2n-2k)! \\
\end{align}$
where we have used $t_i=y_i=y_{2n+1-i}$ in the second equality.
Even though we have a closed form, I still wanted to find the recurrence relation. Taking a cue from A001499, I found the following generating function for $f_n$.
$\displaystyle \sum_{n=0}^\infty f_n \frac{z^n}{n!^2}=\frac{e^{-z}}{\sqrt{1-4z}}$
This helped me in finding A296618 which has a recurrence relation for the EGF coefficients of the above function which are actually $\frac{f_n}{n!}$. From there it was straightforward to see that with $f_0=1$,
$f_n=n(4n-3)f_{n-1}+4n(n-1)^2f_{n-2}$
90 deg. Clockwise (Counter-Clockwise) symmetry - Let $c_n$ denote the number of colorings of a $2n \times 2n$ grid that are fixed by rotating the grid by 90 degrees (270 degrees). Now we only have to fill the first quadrant of the grid. This time we have,
$c_n=\displaystyle[x_1^2x_2^2\cdots x_{2n}^2 y_1^2y_2^2\cdots y_{2n}^2]\prod_{i=1}^n\prod_{j=1}^n(1+x_iy_j\cdot x_jy_{2n+1-i}\cdot x_{2n+1-i}y_{2n+1-j}\cdot x_{2n+1-j}y_i)$
Now let $t_i=x_iy_ix_{2n+1-i}y_{2n+1-i}$. Then,
$c_n=\displaystyle[t_1^2t_2^2\cdots t_n^2]\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)$
I was not able to simplify this in anyway and I tried a bunch of approaches. Finally, I gave up and found the sequence with Mathematica. The values for $n=0,1,2,\cdots$ are $1, 1,2,12,90,810,8940,\cdots$. Unfortunately, this time we don't have a OEIS sequence to directly get a recurrence. After laboring for a day, I found the following recurrence with a lot of paper work. With $c_0=1$,
$c_n=(2n-1)c_{n-1}-(n-1)c_{n-2}+2(n-1)(n-2)c_{n-3}$
Searching for a generating function, we get,
$\displaystyle\sum_{n=0}^\infty c_n\frac{z^n}{n!}=\frac{e^{-z^2/2}}{\sqrt{1-2z}}$
From this we get the following explicit formula.
$\displaystyle c_n=\frac{n!}{2^n}\sum_{k=0}^n \frac{(-2)^k}{k!}\binom{2n-4k}{n-2k}$
With ideas from Algorithms forHolonomic Functions, Algorithmic Manipulations and Transformations of Univariate Holonomic Functions and Sequences and Computing the Generating Function of a series given its First few terms, it seems we can find the above recurrence from the generating function.
Back to the main question of this post, we finally have everything we need to apply Burnside's lemma. Let $A_n$ denote the number of unique (upto rotations and reflections) colorings of a $2n \times 2n$ grid with exactly two black squares in each row and column. Then,
$A_n=\displaystyle\frac{1}{8}(t'_{2n}+2d'_{2n}+2r_n+f_n+2c_n)=\frac{1}{8}(t_n+2d_n+2r_n+f_n+2c_n)$
On a side note, the number of unique (upto rotations and reflections) colorings of a $n \times n$ grid with exactly one black square in each row and column can be found completely using OEIS. The only thing we have to note is that there can be no colorings for vertical or horizontal reflections. If $B_n$ is the required result, then
$\displaystyle B_n=\frac{1}{8}(4\text{ A263685}(n)+2\text{ A000085}(n))$
Hope you enjoyed this. See ya later with another interesting topic.
Until then
Yours Aye
Me
In Example 5 of the quoted page, the author discusses the number of ways of coloring a $n \times n$ grid in which every row and every column has exactly two black squares. In the example that's immediately next, he discusses a counting problem that uses one of favorite results in combinatorics - the Burnside's Lemma.
That got me thinking about the number of unique (upto rotations and reflections) colorings of a $2n \times 2n$ grid with exactly two black squares in each row and column.
We'll also be using Burnside's lemma for this task. We'll be considering the eight symmetries of the square and count how many colorings are fixed by each of these symmetries. We'll progressing on the increasing order of difficulty. Let's begin.
Identity - Let $t'_n$ denote total number of such colorings on an $n \times n$ grid. This is essentially what the wordpress page was doing. In fact we have A001499 that gives us a recurrence. With $t'_0=1$, we have
$t'_n=n(n-1)t'_{n-1}+\frac{1}{2}n(n-1)^2t'_{n-2}$
As we are only interested in $2n \times 2n$ grid, let's define $t_n=t'_{2n}$. With $t_0=1$, this follows the recurrence,
$\displaystyle t_n=\frac{n(2n-1)^2}{2n-3}(8n^2-16n+7)t_{n-1}-2n(n-1)^2(2n-1)^2(2n-3)t_{n-2}$
(or)
$\displaystyle \frac{t_n}{2n-1}=n(2n-1)(8n^2-16n+7)\frac{t_{n-1}}{2n-3}-2n(n-1)^2(2n-1)(2n-3)(2n-5)\frac{t_{n-2}}{2n-5}$
Diagonal (Anti-Diagonal) symmetry - Let $d'_n$ denote the required colorings that are symmetric along the main diagonal. Again, we have A000986 that gives us the following recurrence. Starting with $d'_0=1$,
$d'_n=2(n-1)d'_{n-1}-(n-1)(n-3)d'_{n-2}-\frac{1}{2}(n-1)(n-2)(n-3)d'_{n-4}$
Again, let's define $d_n=d'_{2n}$ which is the number of required colorings with diagonal (anti-diagonal) symmetry in a $2n \times 2n$ grid. With $d_0=1$,
$\displaystyle d_n=\frac{2n-1}{2n-3}(8n^2-16n+7)d_{n-1}-\frac{(n-1)(2n-1)}{2n-5}(16n^3-104n^2+230n-173)d_{n-2}-2(n-1)(n-2)(2n-1)(8n^2-38n+41)d_{n-3}-2(n-1)(n-2)(n-3)(2n-1)(2n-3)(2n-7)d_{n-4}$
(or)
$\displaystyle \frac{d_n}{2n-1}=(8n^2-16n+7)\frac{d_{n-1}}{2n-3}-(n-1)(16n^3-104n^2+230n-173)\frac{d_{n-2}}{2n-5}-2(n-1)(n-2)(2n-7)(8n^2-38n+41)\frac{d_{n-3}}{2n-7}-2(n-1)(n-2)(n-3)(2n-3)(2n-7)(2n-9)\frac{d_{n-4}}{2n-9}$
Horizontal (Vertical) reflection - Let $r_n$ denote the number of colorings that are fixed by Horizontal reflection on a $2n \times 2n$ grid. As we need the grid to be the same after reflecting it horizontally (vertically), we only have to fill up the top $n \times 2n$ grid. We have to make sure that each row has exactly two black squares and each column has exactly one black square in the $n \times 2n$ grid.
Proceeding in the same way as in the wordpress page, we can see that,
$\begin{align}
r_n &= [x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{i=1}^n\prod_{j=1}^{2n}(1+x_iy_j)\\
&= [x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{j=1}^{2n}(1+(x_1+x_2+\cdots+x_n)y_j+O(y_j^2))\\
&= [x_1^2x_2^2\cdots x_n^2](x_1+x_2+\cdots+x_n)^{2n}=2^{-n}(2n)!\\
\end{align}$
So, we have the recurrence $r_n=n(2n-1)r_{n-1}$ with $r_0=1$.
180 deg. rotation symmetry - Let $f_n$ denote the number of colorings of a $2n \times 2n$ grid that are fixed by rotating the grid by 180 degrees. Again like the previous case, we only have to fill up the top $n \times 2n$ grid. We still make sure that each row has exactly two black squares but unlike the previous case, we need to ensure that the total number of black squares in the $j$-th column and $(2n+1-j)$-th column is two.
$\begin{align}
f_n&=[x_1^2x_2^2\cdots x_n^2y_1y_2\cdots y_{2n}]\prod_{i=1}^n\prod_{j=1}^{2n}(1+x_iy_j)\\
&=[x_1^2x_2^2\cdots x_n^2t_1^2t_2^2\cdots t_n^2]\prod_{i=1}^n\prod_{j=1}^n(1+x_it_j)^2\\
&=[x_1^2x_2^2\cdots x_n^2t_1^2t_2^2\cdots t_n^2]\prod_{j=1}^n(1+(x_1+x_2+\cdots +x_n)t_j+(x_1x_2+x_2x_3+\cdots+x_{n-1}x_n)t_j^2+O(t_j^3))^2\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\Biggl(\biggl(\sum_{i=1}^n x_i\biggl)^2+2\sum_{1\leq i<j\leq n} x_ix_j\Biggl)^n\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\Biggl(2\biggl(\sum_{i=1}^n x_i\biggl)^2-\sum_{i=1}^n x_i^2\Biggl)^n\\
&=\displaystyle[x_1^2x_2^2\cdots x_n^2]\sum_{k=0}^n(-1)^k\binom{n}{k}\biggl(\sum_{i=1}^n x_i^2\biggl)^k 2^{n-k}\biggl(\sum_{i=1}^n x_i\biggl)^{2(n-k)}\\
&=\displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{n!}{(n-k)!} 2^{n-k}\frac{(2n-2k)!}{2^{n-k}}\\
&=\displaystyle\sum_{k=0}^n(-1)^k \binom{n}{k}^2k!(2n-2k)! \\
\end{align}$
where we have used $t_i=y_i=y_{2n+1-i}$ in the second equality.
Even though we have a closed form, I still wanted to find the recurrence relation. Taking a cue from A001499, I found the following generating function for $f_n$.
$\displaystyle \sum_{n=0}^\infty f_n \frac{z^n}{n!^2}=\frac{e^{-z}}{\sqrt{1-4z}}$
This helped me in finding A296618 which has a recurrence relation for the EGF coefficients of the above function which are actually $\frac{f_n}{n!}$. From there it was straightforward to see that with $f_0=1$,
$f_n=n(4n-3)f_{n-1}+4n(n-1)^2f_{n-2}$
90 deg. Clockwise (Counter-Clockwise) symmetry - Let $c_n$ denote the number of colorings of a $2n \times 2n$ grid that are fixed by rotating the grid by 90 degrees (270 degrees). Now we only have to fill the first quadrant of the grid. This time we have,
$c_n=\displaystyle[x_1^2x_2^2\cdots x_{2n}^2 y_1^2y_2^2\cdots y_{2n}^2]\prod_{i=1}^n\prod_{j=1}^n(1+x_iy_j\cdot x_jy_{2n+1-i}\cdot x_{2n+1-i}y_{2n+1-j}\cdot x_{2n+1-j}y_i)$
Now let $t_i=x_iy_ix_{2n+1-i}y_{2n+1-i}$. Then,
$c_n=\displaystyle[t_1^2t_2^2\cdots t_n^2]\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)$
I was not able to simplify this in anyway and I tried a bunch of approaches. Finally, I gave up and found the sequence with Mathematica. The values for $n=0,1,2,\cdots$ are $1, 1,2,12,90,810,8940,\cdots$. Unfortunately, this time we don't have a OEIS sequence to directly get a recurrence. After laboring for a day, I found the following recurrence with a lot of paper work. With $c_0=1$,
$c_n=(2n-1)c_{n-1}-(n-1)c_{n-2}+2(n-1)(n-2)c_{n-3}$
Searching for a generating function, we get,
$\displaystyle\sum_{n=0}^\infty c_n\frac{z^n}{n!}=\frac{e^{-z^2/2}}{\sqrt{1-2z}}$
From this we get the following explicit formula.
$\displaystyle c_n=\frac{n!}{2^n}\sum_{k=0}^n \frac{(-2)^k}{k!}\binom{2n-4k}{n-2k}$
With ideas from Algorithms forHolonomic Functions, Algorithmic Manipulations and Transformations of Univariate Holonomic Functions and Sequences and Computing the Generating Function of a series given its First few terms, it seems we can find the above recurrence from the generating function.
Back to the main question of this post, we finally have everything we need to apply Burnside's lemma. Let $A_n$ denote the number of unique (upto rotations and reflections) colorings of a $2n \times 2n$ grid with exactly two black squares in each row and column. Then,
$A_n=\displaystyle\frac{1}{8}(t'_{2n}+2d'_{2n}+2r_n+f_n+2c_n)=\frac{1}{8}(t_n+2d_n+2r_n+f_n+2c_n)$
On a side note, the number of unique (upto rotations and reflections) colorings of a $n \times n$ grid with exactly one black square in each row and column can be found completely using OEIS. The only thing we have to note is that there can be no colorings for vertical or horizontal reflections. If $B_n$ is the required result, then
$\displaystyle B_n=\frac{1}{8}(4\text{ A263685}(n)+2\text{ A000085}(n))$
Hope you enjoyed this. See ya later with another interesting topic.
Until then
Yours Aye
Me
No comments:
Post a Comment