wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Chessboard Conundrum
        
(Message started by: chetangarg on May 5th, 2011, 12:17am)
Title: Chessboard Conundrum
Post by chetangarg on May 5th, 2011, 12:17am
What will be the total no. of ways to rearrange black and white squares on a chess board such that each row and each column has exactly Four white and Four black squares ???
Title: Re: Chessboard Conundrum
Post by Grimbal on May 5th, 2011, 12:27am
I think I would need a computer program to answer this question.

I bet towr is already busy writing it  ;D.
Title: Re: Chessboard Conundrum
Post by towr on May 5th, 2011, 8:45am

on 05/05/11 at 00:27:05, Grimbal wrote:
I bet towr is already busy writing it  ;D.
Not yet, I hadn't even seen it until moments ago. And attempting brute force would be a bit much for my computer.
Title: Re: Chessboard Conundrum
Post by Grimbal on May 5th, 2011, 9:15am
Anyway, here is my first unverified result: [hide]116963796250[/hide].

PS: and it is verified.  A simple search of my result took me to [hide]http://oeis.org/A058527[/hide].
Title: Re: Chessboard Conundrum
Post by ThudnBlunder on May 5th, 2011, 1:11pm
One might expect the number (http://oeis.org/A058527) to be a function of n, but f(3) = 297200 = 743*400, and 743 is prime. :-/
Title: Re: Chessboard Conundrum
Post by JohanC on May 5th, 2011, 1:53pm

on 05/05/11 at 13:11:11, ThudnBlunder wrote:
One might expect the number (http://oeis.org/A058527) to be a function of n, but f(3) = 297200 = 743*400, and 743 is prime. :-/

Why should a simple function of n need to be free of large prime factors? A function as simple as n!-1 quickly leads to terms with large prime factors.

Anyway, the function for these arrangements probably has to count different types of symmetries (and their combinations) seperately. There are not only rotational and reflective symmetries, but also interchanging black and white.

See for example these remarks (http://wwwhomes.uni-bielefeld.de/achim/no3in/symmetry_remarks.html) and counts (http://wwwhomes.uni-bielefeld.de/achim/no3in/table_old.txt) about different chess board symmetries for a similar type of counting question.
Title: Re: Chessboard Conundrum
Post by ThudnBlunder on May 5th, 2011, 2:02pm

on 05/05/11 at 13:53:50, JohanC wrote:
Why should a simple function of n need to be free of large prime factors? A function as simple as n!-1 quickly leads to terms with large prime factors.

Yes, of course. :-[ Sometimes I shoot from the lip. ::)
Title: Re: Chessboard Conundrum
Post by JohanC on May 5th, 2011, 2:04pm

on 05/05/11 at 09:15:46, Grimbal wrote:
Anyway, here is my first unverified result: [hide]116963796250[/hide].

PS: and it is verified.  A simple search of my result took me to [hide]http://oeis.org/A058527[/hide].

The solution not being a small number seems to indicate that quite some grouping is involved. Did you program this in something like c++, or something more exotic?

I already figured out that the 70 (8!/(4!*4!)) posibilities of the first line are a simple multiplication factor. And for each posibility of the second line, you can group depeding on whether you have 4x2, 3x2+2x1, 2x2+4x1, 1x2+6x1 or 8x1.
And after that, it keeps on growing complexity..
Title: Re: Chessboard Conundrum
Post by Grimbal on May 6th, 2011, 12:31am
It is a simple Java program.

The idea is to count row by row how many ways there are to get each possible set of partial totals by column.

An optimization was to reorder the array of partial totals, to group equivalent combinations.

Sorting the totals across columns makes the set of cases equivalent to what you suggest, i.e. group according to how many of each partial column total you have.
Title: Re: Chessboard Conundrum
Post by JohanC on May 6th, 2011, 2:33am

on 05/06/11 at 00:31:21, Grimbal wrote:
It is a simple Java program.
...
Sorting the totals across columns makes the set of cases equivalent to what you suggest, i.e. group according to how many of each partial column total you have.

Interesting. Do you think the same approach is enough to calculate the immense numbers in OEIS? Someone claims to have calculated a 222 digit number for a 30x30 board. (Probably replacing Java with something more machine language friendly, and maybe using some distribution over a network. But even then is seems they must have used some additional insights.
Title: Re: Chessboard Conundrum
Post by Grimbal on May 6th, 2011, 6:59am
I don't know the complexity.

The max number of cases in the 2nx2n case would be halfway through.  That is the number of ways to fill an array of n+1 integers (0..n) in such a way that that sum(i·Ai) = n2.  Or something like that.  That looks close to exponential to me.
Title: Re: Chessboard Conundrum
Post by JohanC on May 6th, 2011, 10:13am
Some googling indicates that this is a quite typical dynamic programming problem.
On the other hand, very similar sequences look at counting the nxn boards with exactly  k black squares in each row and column. This is with k fixed instead of being n/2. They are tackled by quite complex programs to calculate recursions and formulas.
Already for k=2, the formula looks like
a(n) = (n! (n-1) Gamma(n-1/2) / Gamma(1/2) ) * 1F1[2-n; 3/2-n; -1/2] as stated in http://oeis.org/A001499
So there is little hope that the formula for the k=n/2 problem would have an easy recursion or a simple formula.
Some papers:
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPS/bipartite.ps
http://math.fau.edu/~kmatheis/papers/SomeForms01.pdf
And a maple progam by magician Doron Zeilberger:
http://www.math.rutgers.edu/~zeilberg/tokhniot/Bipartite


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board