A Binary Grid counting Problem - Part II

In this post, we consider the same problem as in the previous post but for grids of odd size. As much of the setup was discussed in the previous post, let's dive in right away.

Identity - Let $t_n$ denote total number of such colorings on an $n \times n$ grid. As discussed in the previous post, 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}$

Diagonal (Anti-Diagonal) symmetry - Let $d_n$ denote the required colorings that are symmetric along the main diagonal. Again A000986 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}$

Horizontal (Vertical) reflection - This is really easy. Consider a $(2n+1) \times (2n+1)$ grid. The '$n+1$'th row will have a black square. As each column must have two black squares, there must be another black square in this column. If the second black square is on the top half of the grid, the horizontal reflection would result in an additional black square in the bottom half of the grid, making three squares in that column.Hence, there cant be any colorings that are fixed by horizontal/vertical reflection in an odd sized grid.

180 deg. rotation symmetry - Let $f_n$ denote the number of colorings of a $(2n+1) \times (2n+1)$ grid that are fixed by rotating the grid by 180 degrees. I found this to be the most interesting case. Proceeding like the previous post, we have,

$\begin{align}
f_n&=[x_1^2x_2^2\cdots x_n^2x_{n+1}t_1^2t_2^2\cdots t_n^2t_{n+1}]\displaystyle\prod_{i=1}^n(1+x_{n+1}t_i)(1+x_it_{n+1})\prod_{j=1}^n(1+x_it_j)^2\\
\end{align}$

Unfortunately, I couldn't simplify it any further. I computed the first few terms using Mathematica and searched for a generating function. And I found one.

$\displaystyle f(z)=\sum_{n=0}^\infty f_n \frac{z^n}{n!^2}=\frac{2ze^{-z}}{(1-4z)^{3/2}}$

Now let's derive a (holonomic) recurrence out of this. Let $f(z)=g(z)h(z)$ where $g(z)=ze^{-z}$ and $h(z)=(1-4z)^{-3/2}$. It is see that $(1-4z)h'=6h$ and $zg'=(1-z)g$. From this, we get,

$z(1-4z)f'(z)=6zf(z)+(1-z)(1-4z)f(z)$

Equating coefficients on both sides, we have,

$(n-1)f_n=n^2(4n-3)f_{n-1}+4n^2(n-1)^2f_{n-2}$ with $f_0=0$ and $f_1=2$.

90 deg. Clockwise (Counter-Clockwise) symmetry - Let $c_n$ denote the number of colorings of a $(2n+1) \times (2n+1)$ grid that are fixed by rotating the grid by 90 degrees (270 degrees). We proceed like in the previous post.

$c_n=\displaystyle[x_1^2x_2^2\cdots x_{2n+1}^2 y_1^2y_2^2\cdots y_{2n+1}^2]\prod_{i=1}^{n+1}\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+2-i}y_{2n+2-i}$. Then,

$\begin{align}
c_n&=\displaystyle[t_1^2t_2^2\cdots t_n^2t_{n+1}]\prod_{i=1}^{n+1}\prod_{j=1}^n(1+t_it_j)\\
&=[t_1^2t_2^2\cdots t_n^2t_{n+1}](1+(t_1+t_2+\cdots+t_n)t_{n+1}+O(t_{n+1}^2))\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)\\
&=n\cdot[t_1^2t_2^2\cdots t_{n-1}^2t_n]\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)\\
\end{align}$

Let $x_n=[t_1^2t_2^2\cdots t_{n-1}^2t_n]\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)$. We manipulate this expression hoping to get a recurrence.

$\begin{align}
x_n&=\displaystyle[t_1^2t_2^2\cdots t_{n-1}^2t_n]\prod_{i=1}^n\prod_{j=1}^n(1+t_it_j)\\
&=[t_1^2t_2^2\cdots t_{n-1}^2t_n](1+t_1t_n)^2(1+t_2t_n)^2\cdots(1+t_{n-1}t_n)^2(1+t_n^2)\prod_{i=1}^{n-1}\prod_{j=1}^{n-1}(1+t_it_j)\\
&=[t_1^2t_2^2\cdots t_{n-1}^2t_n](1+t_1t_n)^2(1+t_2t_n)^2\cdots(1+t_{n-1}t_n)^2\prod_{i=1}^{n-1}\prod_{j=1}^{n-1}(1+t_it_j)\\
&=[t_1^2t_2^2\cdots t_{n-1}^2t_n](1+(t_1+t_2+\cdots+t_{n-1})t_n+O(t_n^2))^2\prod_{i=1}^{n-1}\prod_{j=1}^{n-1}(1+t_it_j)\\
&=[t_1^2t_2^2\cdots t_{n-1}^2t_n](1+2(t_1+t_2+\cdots+t_{n-1})t_n+O(t_n^2))\prod_{i=1}^{n-1}\prod_{j=1}^{n-1}(1+t_it_j)\\
&=2(n-1)[t_1^2t_2^2\cdots t_{n-2}^2t_{n-1}]\prod_{i=1}^{n-1}\prod_{j=1}^{n-1}(1+t_it_j)\\
&=2(n-1)x_{n-1}\\
\end{align}$

But it's easy to see that $x_1=\displaystyle[t_1]\prod_{i=1}^1\prod_{j=1}^1(1+t_it_j)=[t_1](1+t_1^2)=0$

Therefore, like in the case of reflections, there are no colorings that are fixed by clockwise (anti-clockwise) rotations.

Now that we have all of the above, we can use Burnside's Lemma to solve the problem for grids of odd size. 

Hope you enjoyed this. See ya later with another interesting topic.


Until then
Yours Aye
Me

A Quest for Pi

For $m<n$, it is easy to show that,

$\displaystyle\frac{x^m}{(x-a_0)(x-a_1)\cdots(x-a_{n-1})}=\sum_{k=0}^{n-1}\frac{a_k^m}{x-a_k}\prod_{i=0\\i \neq k}^{n-1}(a_k-a_i)^{-1}$

Let's choose, $a_k=\eta^k$ where $\eta$ is the $n^{\text{th}}$ root of unity. Then we have,

$\displaystyle \frac{x^m}{1-x^n}=\sum_{k=0}^{n-1}\frac{1}{n\eta^{k(n-1)}}\frac{\eta^{km}}{\eta^k-x}=\frac{1}{n}\sum_{k=0}^{n-1}\frac{\eta^{km}}{1-x/\eta^k}$

Integrating $x$ in the above expression between $0$ and $t$ and comparing the real part, we get,

$\begin{align}
\displaystyle \sum_{j \geq 0}\frac{t^{jn+m}}{jn+m}&=\frac{1}{n}\sum_{k=0}^{n-1}\cos(2\pi km/n)\log(1-2\cos(2\pi k/n)t+t^2)^{-1/2}\\ &\quad +\frac{1}{n}\sum_{k=0}^{n-1}\sin(2\pi km/n)\tan^{-1}\left(\frac{\sin(2\pi k/n)}{t^{-1}-\cos(2\pi k/n)}\right)
\end{align}$

Comparing the Imaginary parts, we also get,

$\displaystyle \sum_{k=0}^{n-1}\cos(2\pi km/n)\tan^{-1}\left(\frac{\sin(2\pi k/n)}{t^{-1}-\cos(2\pi k/n)}\right)=\sum_{k=0}^{n-1}\sin(2\pi km/n)\log(1-2\cos(2\pi k/n)t+t^2)^{-1/2}$

Using the properties of Conjugates, we also have,

$\begin{align}
\displaystyle \sum_{j \geq 0}\frac{t^{jn+m}}{jn+m}&=\frac{1}{n}\log(1-t)^{-1}+\mathbf{1}_{n \text{ even}}\frac{(-1)^m}{n}\log(1+t)^{-1}\\ & \quad +\frac{2}{n}\sum_{k=1}^{\lceil n/2 \rceil-1}\sin(2\pi km/n)\tan^{-1}\left(\frac{\sin(2\pi k/n)t}{1-\cos(2\pi k/n)t}\right)\\ & \quad +\frac{2}{n}\sum_{k=1}^{\lceil n/2 \rceil-1}\cos(2\pi km/n)\log(1-2\cos(2\pi k/n)t+t^2)^{-1/2}
\end{align}$

On the other hand, using Vandermonde matrix or otherwise,

$\displaystyle \frac{1}{1-x/\eta^m}=\sum_{k=0}^{n-1}\eta^{-km}\frac{x^k}{1-x^n}$

Integrating the above,

$\displaystyle \log(1-\eta^{-m}t)^{-1}=\sum_{k=1}^n\eta^{-mk}P_{n,k}(t)$ where $\displaystyle P_{n,k}(t)=\sum_{j \geq 0}\frac{t^{nj+k}}{nj+k}$

Comparing real and imaginary parts, we have,

$\displaystyle \log(1-2\cos(2\pi m/n)t+t^2)^{-1/2}=\sum_{k=1}^n\cos(2\pi km/n)P_{n,k}(t)$

$\displaystyle \tan^{-1}\left(\frac{\sin(2\pi m/n)}{t^{-1}-\cos(2\pi m/n)}\right)=\sum_{k=1}^n\sin(2\pi km/n)P_{n,k}(t)$

The second one here is more interesting. Using $t=\cos(2\pi m/n)$, we get infinitely many representations for $\pi$.

$\displaystyle (n-4m)\frac{\pi}{2n}=\sum_{k=1}^n\sin(2\pi km/n)P_{n,k}(\cos(2\pi m/n))$

For example, with $m=1$ and $n=3$, we get a Bailey–Borwein–Plouffe type formula (BBP formula) for $\pi$ in Base-64 which can be verified with Wolfram Alpha.

$\displaystyle \frac{\pi}{(\sqrt{3}/2)^3}=\sum_{k=0}^\infty\left[\frac{1}{64^k}\left(\frac{4}{6k+1}+\frac{2}{6k+2}-\frac{2^{-1}}{6k+4}-\frac{4^{-1}}{6k+5}\right)\right]$

(or)

$\displaystyle \frac{32\pi}{3\sqrt{3}}=\sum_{k=0}^\infty\left[\frac{1}{64^k}\left(\frac{16}{6k+1}+\frac{8}{6k+2}-\frac{2}{6k+4}-\frac{1}{6k+5}\right)\right]$


Until then
Yours Aye
Me