Number of maximal independent sets in n x n bishops graph and other rook-like graphs.
=====================================================================================

The following note presents a polynomial time algorithm for the determination of the number of maximal independent sets
and the maximal independent polynomial in the bishops graph.
The algorithm is applicable to other similar graphs such as rooks on a triangular or other irregular shaped board.
One requirement is that it must be possible to reorder the rows/columns of the graph so that they form a monotonic sequence (as in a Ferrers diagram).

Bishops graph:
The n x n bishops graph is composed of two connected components, the black bishops graph and the white bishops graph.
The convention that the black bishops graph always includes a corner vertex is used.
The number of maximal independent sets in the combined graph is the product of the number of maximal independent sets in the two components. 
Re-ordering rows and columns does not change the graph and both bishop graphs are equivalent to irregular rook graphs in which not all rows have the same length.

For example after re-ordering, the 5x5 black bishop graphs has 5 rows of lengths 1,1,3,3,5 and the 5x5 white bishops graph has 4 rows of lengths 2,2,4,4.

Basic algorithm:
In the following we will make use of the following simple functions on a vector.
   first(v):  returns first element. Eg first([2,2,4,4]) = 2.
   rest(v):   returns all but the first element. Eg rest([2,2,4,4]) = [2,4,4].
   length(v): returns the length of the vector. Eg length([2,2,4,4]) = 4.
   cut(v,d): reduces each value by d. Eg cut([2,2,4,4], 1) = [1,1,3,3].

For v a vector of ordered non negative integers
and k a non negative integer
define M(v,k) as (k!*x^k) * the sum of the maximal independence polynomials of the rook like graphs defined by the vector v (as described above)
with k rows removed with the summation taken over all ways that the k rows can be removed.
Here x is the polynomial indeterminate.

Using this definition the maximal independence polynomial for the 5x5 black bishops graph is given by M([1,1,3,3,5], 0)

In the case that k > length(v), M(v,k) = 0.

M(v,k) can be computed recursively as follows (for k<=length(v))
  If length(v) = 0 then 1
  Otherwise we consider options for the first row.
  If k > 0, the row can be chosen as one of the rows to remove.
      => k * x * M( rest(v), k-1 )
  Or if k < length(v) a vertex can be chosen from the row which will cover the row. The chosen vertex will also be adjacent to all vertices
    in its column so it is necessary to reduce each column by 1 since those vertices cannot be used by a later row.
      => first(v) * x * M( cut(rest(v), 1), k )
  Or if k + first(v) < length(v) it is possible that the row be left empty. In this case, future rows will need to cover each of the columns.
    To account for this we remove those columns and increase k by that amount. Each time one of those k rows is skipped it can be thought of
    as being used to cover a previously left empty column.
      => M( cut( rest(v), first(v) ), k + first(v) )
  The above three options are not mutually exclusive.

PARI code
Rather than manipulate a description vector with 'rest' and 'cut' it is easier to use a vector that is ordered from biggest
to smallest and to process it in reverse order keeping track of the remaining length and the number of columns that have been cut.
This avoids having to update the description vector.

\\ Functions are needed to give a description of the graphs
Bishop(n,white)=vector(n-if(white,n%2,1-n%2),i,n-i+if(white,1-i%2,i%2));
Rook(m,n)=vector(m,i,n);
Triangle(n)=vector(n,i,n+1-i);
\\ Example uses:
Bishop(5,0)  \\ gives [5, 3, 3, 1, 1]
Bishop(5,1)  \\ gives [4, 4, 2, 2]
Rook(5,3)    \\ gives [3, 3, 3, 3, 3]
Triangle(5)  \\ gives [5, 4, 3, 2, 1]

\\ Main recursive function
\\ Parameters are:
\\ sig: The vector that describes the graph. This remains constant throughout.
\\ n: The number of rows in sig that should be considered. This starts at n and at each step of the recursion reduces by 1.
\\ k: The number of rows that are needed to cover previous rows. This starts at 0 and is always in the range 0..n.
\\ d: The amount that each value in sig needs to be reduced by to get current working value. This starts at 0 and
\\    is increased by one each time a column is 'cut'.
\\ x: The variable that the maximal independence polynomial should be constructed with. This can be given as 1 to get just the total value.
{M(sig,n,k,d,x)=
     if(n==0,k==0,
        if(k>0, k*x*M(sig,n-1,k-1,d,x), 0)
        + if(k<n&&sig[n]>d, (sig[n]-d)*x*M(sig,n-1,k,d+1,x), 0)
        + if(k+sig[n]-d<n, M(sig,n-1,k+sig[n]-d,sig[n],x), 0)  )
}

\\ Top level function to make calling M easier
Q(sig,x)=M(sig,length(sig),0,0,x)


Results and Sequences
Number of maximal independent sets in n X n bishops graph
A146304(n) = Q(Bishop(n,1),1)*Q(Bishop(n,0),1)
=> 1, 4, 10, 64, 660, 7744, 111888, 1960000, 40829184 ...

A122749(n) = polcoeff(Q(Bishop(n,1),x)*Q(Bishop(n,0),x),n,x)
=> 4, 2, 16, 44, 256, 768, 5184, 25344 ...

A288182(n) = p=Q(Bishop(n,1),x);vector(n-1,i,polcoeff(p,i,x))
=> [2], [0, 2], [0, 4, 4], [0, 2, 16, 4] ...

A288183(n) = p=Q(Bishop(n,0),x);vector(n-1,i,polcoeff(p,i,x))
=> [2], [1, 4], [0, 4, 4], [0, 0, 22, 8] ...

Performance
The above code performs poorly for large n due to recursion. However because n, k and d which are the only variables are always
in the range 0..length(sig), using memoization will make the execution time polynomial. Depending on programming language there may
be many ways to accomplish this.

Faster PARI code with caching
{Q(sig,x)=
  local(m,M,cache);
  m = length(sig)+1;
  cache=vector(m^3);
  (M(n,k,d)=local(idx,v);
     if(n==0, k==0, idx=(m*d+k)*m+n;v=cache[idx];
        if(v,v,cache[idx]=
           if(k>0, k*x*M(n-1,k-1,d), 0) + if(k<n&&sig[n]>d, (sig[n]-d)*x*M(n-1,k,d+1), 0) + if(k+sig[n]-d<n, M(n-1,k+sig[n]-d,sig[n]), 0)
  )));
  M(length(sig),0,0)
}