Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 A0892963, 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.

share|improve this question
2  
There's much better than a table: there's an algorithm. See, for example, Petovsek, Wilf, and Zeilberger: math.upenn.edu/~wilf/AeqB.html –  Qiaochu Yuan Jul 14 '10 at 3:42
1  
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. –  Eric Tressler Jul 14 '10 at 3:43
2  
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). –  Wadim Zudilin Jul 14 '10 at 7:50
2  
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. –  Victor Protsak Jul 16 '10 at 4:44
2  
@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". –  Gerald Edgar Jul 17 '10 at 1:24
show 5 more comments

1 Answer

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.

share|improve this answer
    
...and I suppose the identities at dlmf.nist.gov/16.4.iii might be of service as well. –  J. M. Nov 15 '10 at 16:00
    
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. –  Hjalmar Rosengren Nov 15 '10 at 16:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.