A178717 Degree of denominator of GF for number of ways to place k nonattacking queens on an n X n board.

3, 5, 9, 17, 37, 81, 197, 477, 1197, 3077, 7989, 20649, 53885, 140601, 366917, 959685, 2511477, 6571681, 17202449, 45027677, 117871345, 308581637, 807852685, 2114904397, 5536838045, 14495554593, 37949503089, 99352690141, 260108204933

Offset: 1

Author

Vaclav Kotesovec, Jun 07 2010

Keywords

• nonn

Links

• V. Kotesovec, Non-attacking chess pieces, 6ed, 2013

Crossrefs

Cf. A036464, A047659, A061994, A108792, A176186, A000010, A000045.

Programs

Mathematica

Table[2*k + 1 + Sum[Sum[2*j*EulerPhi[i], {i, Fibonacci[k - j] + 1, Fibonacci[k - j + 1]}], {j, 1, k - 1}], {k, 1, 20}]

Formula

Explicit formula (Vaclav Kotesovec, May 31 2010), for k>1 : d(k) = 2*k+1+Sum[Sum[2*j*EulerPhi[i],{i,Fibonacci[k-j]+1,Fibonacci[k-j+1]}],{j,1,k-1}].

Asymptotic formula: d(k) ~ 6/(5*Pi^2)*((1+Sqrt[5])/2)^(2*k+1) or d(k) ~ 3*(1+Sqrt[5])/Pi^2*Fibonacci[k]^2.