Problem with Qs and Ps

[Leonard Smiley]

"Antreas P. Hatzipolakis" wrote:

> Consider an n X n chessboard. Place n queens in the cells of the first
row,
> namely in the cells (1,1), (2,1),..., (n,1), and [(n+1)/2] pawns in
the
> odd cells of the second row, namely in the cells (1,2), (3,2), (5,2),
...
> Which is the number of the unattacked (by the queens) cells ?
>
> Example: 5 X 5
>
>                     ---------------------
>                   5 |   |   | * |   |   |
>                     ---------------------
>                   4 | * |   | * |   | * |
>                     ---------------------
>                   3 |   |   |   |   |   |
>                     ---------------------
>                   2 | P |   | P |   | P |
>                     ---------------------
>                   1 | Q | Q | Q | Q | Q |
>                     ---------------------
>                       1   2   3   4   5
>
> Q: queen, P: pawn, *: unattacked cell
>
> I made some computations by hand, and here is a table:
>
> n |  1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 .....
> __|______________________________________________
> # |  0 0 0 2 4 7 10 14 19 24 30 36 44 51 60 .....
>
> Formula ??
>
> Antreas

I'm probably a day late with this (although June 1 still has 5 hours to
go
here).

a(2m+1) = m^2 -1 + A002620(m)

a(2m) = a(2m-1) + m

and it's easy to prove. (m>0 is a good idea)

Len Smiley