A201862 Number of ways to place k nonattacking bishops on an n X n board, sum over all k>=0.

1, 2, 9, 70, 729, 9918, 167281, 3423362, 82609921, 2319730026, 74500064809, 2711723081550, 110568316431609, 5016846683306758, 251180326892449969, 13806795579059621930, 827911558468860287041, 53940895144894708523922, 3799498445458163685753481, 288400498147873552894868886

Offset: 0

Author

Vaclav Kotesovec, Dec 06 2011

Keywords

• nonn

Comments

Also the number of vertex covers and independent vertex sets of the n X n bishop graph.

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..320
• Vaclav Kotesovec, Non-attacking chess pieces
• Eric Weisstein's World of Mathematics, Bishop Graph
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Vertex Cover

Crossrefs

Cf. A010790, A172123, A172124, A172127, A172129, A176886, A187239 - A187242, A002465, A216078, A216332.

Row sums of A378590.

Programs

Mathematica

knbishops[k_,n_]:=(If[n==1,If[k==1,1,0],(-1)^k/(2n-k)!
*Sum[Binomial[2n-k,n-k+i]*Sum[(-1)^m*Binomial[n-i,m]*m^Floor[n/2]*(m+1)^Floor[(n+1)/2],{m,1,n-i}]
*Sum[(-1)^m*Binomial[n-k+i,m]*m^Floor[(n+1)/2]*(m+1)^Floor[n/2],{m,1,n+i-k}],{i,Max[0,k-n],Min[k,n]}]]);
Table[1+Sum[knbishops[k,n],{k,1,2n-1}],{n,1,25}]

Formula

a(n) = A216078(n+1) * A216332(n+1). - Andrew Howroyd, May 08 2017

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 01 2024