4
$\begingroup$

I am trying to compute the number of distinct ways a $4n$ $\times$ $4n$ chessboard can be colored black and white, with exactly half the squares black and half the squares white. By distinct, I mean not equivalent by rotation or reflection, i.e. with respect to the dihedral group $D_4$.

Of course I wouldn't be too surprised if this has already been computed and the answer already known, but calculating a few terms and looking them up in OEIS didn't lead to anything. FYI, the first three terms are 1674, 229078019084673798, and 185026624806098273753009169783707528668060, corresponding to board sizes of 4$\times$4, 8$\times$8, and 12$\times$12.

Using Burnside and simplifying I've got it down to

$$\frac{1}{8} \left[2 {4 n^2 \choose 2 n^2}+3 {8 n^2 \choose 4 n^2}+{16 n^2 \choose 8 n^2} + 2 \sum _{k=0}^{2 n} {4 n \choose 2 k} {8 n^2-2 n \choose 4 n^2-k}\right]$$ and you can probably guess I would like a closed form for the sum.

With a little research and some help from Mathematica, the sum simplifies to
$$ \frac{(8n^2-2n)!}{(4n^2)!(4n^2-2n)!} \ {}_ {3}F_ 2\biggl(\begin{matrix} \frac{1}{2}-2n,\ -2n,\ -4n^2 \cr \frac{1}{2},\ 4n^2-2n+1\end{matrix};-1\biggr)$$

I know little about hypergeometric functions but apparently some special cases are reducible to closed forms. My question is this, then: Does this particular hypergeometric expression have a closed form? And more generally, is there something akin to a table of integrals where I could look up something like this?

Clarification: Although my sequence does not appear in OEIS, it does appear as a subsequence of A082963, where two of three terms I computed are given. Unfortunately there is no formula given, closed or otherwise; nor is there any generating function mentioned, nor references cited. This is what I meant by my lookup in OEIS not leading to anything. Sorry to those I confused with my remark. The only reason I mentioned OEIS in the first place was to spare those kind enough to take interest in my question the time of looking there.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ There's much better than a table: there's an algorithm. See, for example, Petovsek, Wilf, and Zeilberger: math.upenn.edu/~wilf/AeqB.html $\endgroup$
    – Qiaochu Yuan
    Commented Jul 14, 2010 at 3:42
  • 1
    $\begingroup$ I have no idea, but if you run into this kind of thing a lot, or if you really care about this particular case, check out the excellent book "A=B" by Petkovsek, Wilf, and Zeilberger. I believe it will answer your question. $\endgroup$
    – Eric Tressler
    Commented Jul 14, 2010 at 3:43
  • 2
    $\begingroup$ And, I forgot to say, your series has no closed form evaluation. The $_3F_2(-1)$ is rarely summable, at least for 1-parametric families all such cases are known and are classical (Bailey's and Slater's books on hypergeometric functions are more than sufficient). $\endgroup$
    – Wadim Zudilin
    Commented Jul 14, 2010 at 7:50
  • 2
    $\begingroup$ I.J.: You said "I wouldn't be too surprised if this has already been computed and the answer already known, but calculating a few terms and looking them up in OEIS didn't lead to anything" and to 99.9% of the people, this translates into "the sequence is not in OEIS". When Qiaochu found it there, you've acknowledged it in the comments but refused to update your question. $\endgroup$
    – Victor Protsak
    Commented Jul 16, 2010 at 4:44
  • 2
    $\begingroup$ @Victor: I disagree. Many more than 0.1% would think that "looking them up in OEIS didn't lead to anything" implies that they were found in OEIS, since not finding them would be more likely be stated "didn't find them". $\endgroup$
    – Gerald Edgar
    Commented Jul 17, 2010 at 1:24

1 Answer 1

Reset to default
5
$\begingroup$

The ${}_3F_2$ that you have is well-poised, meaning that it has the form $${}_ {3}F_ 2\biggl(\begin{matrix} a,b,c \cr a+1-b,a+1-c\end{matrix};x\biggr).$$ There are quadratic transformation formulas for such series. For instance, your sum can be written $${}_ {3}F_ 2\biggl(\begin{matrix} \frac 12-2n,-2n,-4n^2 \cr \frac 12,4n^2-2n+1\end{matrix};-1\biggr)=4^n{}_ {3}F_ 2\biggl(\begin{matrix} -n,\frac 12-n,\frac 12+4n^2 \cr \frac 12,4n^2-2n+1\end{matrix};1\biggr).$$ (See e.g. Gasper and Rahman, Basic hypergeometric series, Eq. (3.1.8).) This is a simplification since the right-hand side has $n+1$ terms, compared to $2n+1$ in your original sum.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ...and I suppose the identities at dlmf.nist.gov/16.4.iii might be of service as well. $\endgroup$
    – J. M. isn't a mathematician
    Commented Nov 15, 2010 at 16:00
  • $\begingroup$ The identity I was using is 16.6.1 in dlmf.nist.gov/16.6. As you say, after you have applied this identity, you have a series of unit argument, and you can apply e.g. 16.4.11 in different ways. $\endgroup$
    – Hjalmar Rosengren
    Commented Nov 15, 2010 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .