function c = latticecounthelper(n,A,x,y)
% counts the number of n*n lattices with k dimers below the current point
% x,y and with positions at the current depth given by A already taken.
% input:
%   n: the length of one side of the square dimer
%   A: an indicator matrix showing where dimers have been placed
%      for the current and next row
%   x: the current x position
%   y: the current y position
% output: c: the count
% global:
%   memo: data structure used for memoizing to speed this up
%         if uses a very large amount of memory
% ("Memoizing" in this case just means saving partial results so that
% that the computation is reduced.)
% Thomas DuBois 10/2006 (with some comments added by DPO)
global memo;

maxk=n^2/2+1;
c=zeros(1,maxk);

if x>n
  % if the lattice has been completed, record it with 0 more dimers
  c(1)=1;
else
  % turn A into a single n bit binary number for checking the memo
  id=A(1); 
  for i=2:length(A)
    id=2*id+A(i);
  end
  id=id+1;
  if(0 <= memo(id,1,x,y)) % this configuration is in the memo, use that value
     c=memo(id,:,x,y);
  else % this configuration is not in the memo, so compute its value
    % determine the next position
    if(y<n)
      newx=x;newy=y+1;
    else
      newx=x+1;newy=1;
    end
    if A(y)
      % if there is already a dimer covering the current entry
      % we cannot add another one, so just move to the next one
      % and mark this y position empty for the next row
      A(y)=0;
      c=c+latticecounthelper(n,A,newx,newy);
    else
      % we have (up to) three options.  1) do not add a dimer
      % 2) add a horizontal dimer, 3) add a vertical dimer
      % option 1)
      c=c+latticecounthelper(n,A,newx,newy);
      if(y<n && A(y+1)==0) % option 2)
        % if available, put a dimer on this an the next horizontal position
        A(y+1)=1;
        c1=latticecounthelper(n,A,newx,newy);
        % shift the results to account for the dimer just added
        c=c+[0,c1(1:(maxk-1))];
        A(y+1)=0;
      end
      if(x<n) % option 3)
        % if available, put a dimer on this and the next vertical position
        A(y)=1;
        c1=latticecounthelper(n,A,newx,newy);
        % shift the results to account for the dimer just added
        c=c+[0,c1(1:(maxk-1))];
      end
    end
    % update the memo
    memo(id,:,x,y)=c;
  end
end
