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

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

Offset

1,1

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 = 1..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

Formula

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

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}]

Crossrefs

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

Sequence in context: A369778 A284762 A296718 * A167016 A300014 A108522

Adjacent sequences: A201859 A201860 A201861 * A201863 A201864 A201865

Keyword

nonn

Author

Vaclav Kotesovec, Dec 06 2011

Status

approved