Understanding a formula in OEIS

Question

I was looking at this question:

Embedding Mazes - Spanning Trees of a Grid Graph

and one of the comments mentioned "See OEIS sequence A007341", which is here:

A007341 Number of spanning trees in n X n grid.

I am trying to understand the formula in the A007341 link above. Can someone explain it to me? I want to plug in some numbers to see if it will give me what I am looking for. Specifically the part in bold below I do not understand. Also, I am not sure how to connect the cosine parts...multiply? Is the bold part some kind of loop that I can translate into code?

FORMULA

a(n) = 2^(n^2-1) / n^2 * product_{n1=0..n-1, n2=0..n-1, n1 and n2 not both 0} (2 - cos(PIn1/n) - cos(PIn2/n) )

Answer 1

I know this is old and may no longer be something you need answered, but since someone else could be wondering now or in the future, and since there are no answers yet...

A more mathematical version of the formula is in the comments on the post. TBH I don't think the formula is well written (I mean the OEIS one, not the one in the comments by Yves) but I think that's just a byproduct of the formula itself and not really the fault of the formula's author. Anyway, on the OEIS site directly below the formula there is a piece of Maple code, reproduced here:

a:= n-> round(evalf(2^(n^2-1) /n^2 *mul(mul(`if`(j<>0 or k<>0, 
        2 -cos(Pi*j/n) -cos(Pi*k/n), 1), k=0..n-1), j=0..n-1),
        15 +n*(n+1)/2)): seq(a(n), n=1..20);

If you don't know Maple then that's a pain at best and meaningless at worst. Luckily I know Maple and based on that piece of code, we can write the formula mathematically as follows (using $j$ and $k$ instead of $n_1$ and $n_2$, respectively).

$$ a(n) = \frac{2^{n^2-1}}{n^2} \prod_{\substack{\text{$j=0$ if $k \ne 0$} \\ \text{$j=1$ if $k=0$}}}^{n-1} \prod_{\substack{\text{$k=0$ if $j \ne 0$} \\ \text{$k=1$ if $j=0$}}}^{n-1} \left[2 - \cos\left(\frac{j\pi}n\right) - \cos\left(\frac{k\pi}n\right)\right] $$

The condition that $j$ and $k$ aren't both zero unfortunately complicates the notation quite a bit.

You also asked:

Is the bold part some kind of loop that I can translate into code?

Yes. Based on your profile I think I can assume you know C#. I don't know C# well enough to use it to explain something but I do know Java, and I believe the two are similar enough and this algorithm is simple enough to be easily converted between the two languages. In the below (untested and likely non-optimal) Java code snippet, I'm assuming $n$ has already been defined.

double prod = Math.pow(2, n*n-1) / (n*n);

for (j = 0; j <= n; j++) {
    for (k = 0; k <= n; k++) {
        if (j != 0 && k != 0) {
            prod = prod * (2 - Math.cos(Math.PI * j / n) - Math.cos(Math.PI * k / n));
        }
    }
}

---

For example, if $n=2$ then both $j$ and $k$ range from $0$ to $2$, and we skip the case where $j$ and $k$ are simultaneously zero. So we have

\begin{align*} a(2) &= \frac{2^{2^2-1}}{2^2} \prod_{\substack{\text{$j=0$ if $k \ne 0$} \\ \text{$j=1$ if $k=0$}}}^{2-1} \prod_{\substack{\text{$k=0$ if $j \ne 0$} \\ \text{$k=1$ if $j=0$}}}^{2-1} \left[2 - \cos\left(\frac{j\pi}2\right) - \cos\left(\frac{k\pi}2\right)\right]\\[0.3cm] &= \frac{2^3}{2^2} \underbrace{\left[2 - \cos\left(\frac{0\pi}2\right) - \cos\left(\frac{1\pi}2\right)\right]}_{j=0 \text{ and } k=1} \cdot \underbrace{\left[2 - \cos\left(\frac{1\pi}2\right) - \cos\left(\frac{0\pi}2\right)\right]}_{j=1 \text{ and } k=0} \cdot \underbrace{\left[2 - \cos\left(\frac{1\pi}2\right) - \cos\left(\frac{1\pi}2\right)\right]}_{j=1 \text{ and } k=1}\\[0.3cm] &= 2 \cdot \left[ 2 - \cos 0 - \cos\frac\pi2\right] \cdot \left[2 - \cos\frac\pi2 - \cos 0\right] \cdot \left[2 - \cos\frac\pi2 - \cos\frac\pi2\right]\\[0.3cm] &= 2 \cdot (2 - 1 - 0) \cdot (2 - 0 - 1) \cdot (2-0-0)\\ &= 4 \end{align*} Note that $a(2) = 4$ matches OEIS.