Number of Ways to Fill a Matrix with symbols subject to Weird contsraint. Got this problem from a friend and would like some pointers if anyone has any.
Fill an $n \times n$ matrix with the symbols $\{a,b,c,d\}$ subject to the following:
 
  
*Only the symbol $a$ appears to the left or above an $a$ 
  
*Only the symbol $b$ appears to the right or above a $b$ 
  
*Only the symbol $c$ appears to the left or below a $c$ 
  
*Only the symbol $d$ appears to the right or below a $d$ 
 
Here are some examples of a valid fillings:
$$\left( \begin{matrix} a & a & b  & b \\ a & a & b & b \\ c & c & c & d \\  c & c & c & d  \end{matrix}\right) $$
$$\left( \begin{matrix} a & a & a  & a & a & b  & b \\ a & a & a  & a & a & b  & b \\ a & a & a & d & d & d & d \\  a & a & a & d & d & d & d\\a & a & d & d & d & d & d\\c & c & d & d & d & d & d\\  c & c & d & d & d & d & d  \end{matrix} \right) $$
What I have done: We'll it is clear to me that the $a$'s (for example) make up a sort of Young Diagram just by the property above. But there is more to the problem than that. If your YT for $a$ is just a square, then you might have a reversed (right justified) YT available to place for the $b$'s. Details like this seem to make this a tricky problem for me. I am intrigued by this problem and I just thought I'd share it here in case there is some easy way to do this counting problem that I've never heard of.
Thanks,
 A: Answerified comment as requested:
If I'm counting correctly, the first few values (starting with $n=1$) are $4$, $25$, $120$, $497$, $1924$, $7265$, $27288$, $102745$, $388692$, $1477721$, $5643064$, $21632785$, $83204260$, $320932177$. This sequence isn't in OEIS.
Here's the code I used. 
A: I don't know how amcalde did it, but after thinking about it some more, I have a derivation, which I've translated to match this formulation of the problem, rather than the one I posted.
Note: this answer is wrong, though I feel like I covered every case without double-counting.  I only post it because I think it's close, and maybe someone can see what went wrong with it too arrive at the correct derivation.
(update: I thought I had it for a second, after I got the correct result for the first couple values.  It's not the same form amcalde got, though and they aren't equivalent)
We attack it case-by-case... 
In the following, "opposite symbol" means diagonally opposite, so $a$ and $d$ are opposites, as are $b$ and $c$.
for cases 1-5, we assume that each symbol is configured in a rectangle (i.e. the number of a given symbol in each row is either $0$ or $k$ for some $k\le n$ and likewise (with possibly different $k$) for each column):
Case 1: there is only one unique symbol in the matrix.  there are $4$ of these.
Case 2: every column (or every row) contains only one unique symbol, with two unique symbols in the array as a whole.  there are $n-1$ ways to choose the first column of the second symbol, times $4$ ways to choose the symbols, times $2$ to count the same thing for rows for a total of $8n-8$
Case 3:some columns (or rows) contain (the same) 2 distinct symbols, and the rest contain only a single (different) distinct symbol. using similar counting to the above, there are $8(n-1)^2$ of these.
Case 4: there are four distinct symbols in the matrix and no symbol shares a column or row with its opposite. there are $(n-1)^2$ of these.
Case 5: there are four distinct symbols and two opposite symbols appear together in at least one column or row (but not both, because of the rectangle requirement).  There are $4(n-1){{n-1} \choose 2}=2(n-1)(n-1)(n-2)=(2n-4)(n-1)^2$ of these.
all other configurations belong to case 6.
Case 6: at least one column and at least one row contains two opposite symbols. In other words, at least one symbol fails to form a rectangle shape.
This is the tough one, but suppose for a second that we're talking about $a$ and $d$.  Each such case will correspond to a reflection $a \iff c$ and $b \iff d$, so we'll just multiply by two when we're done.  Now imagine drawing a line between every $a$ and $d$ that appear in the same row or column.  this will form a stairstep-shaped line going from lower right to upper left.  If there are $k$ rows and $r$ columns consisting of $a$ and $d$, then this is a classic stars-and-bars problem with ${k+r} \choose r$ possibilities for the shape of the stairstep. The number of different places a stairstep can be placed is a source of potential pitfalls.  To simplify it we assume at first that our stairstep starts with a horizontal line (we'll double our result again, and start our sum at $k=0$), and count the number of a stairstep that ends with a vertical line (we'll also start at $ r=0 $) can be placed. There are $n-r-1$ horizontal positions.  There are also $n-k-1$ vertical positions, in all but one of which the stairstep can optionally be extended with an additional horizontal line, so the total number of possible stairsteps is
$$4\sum_{k=0}^{n-2}\left((2n-2k-3)\sum_{r=0}^{n-2}\left({{r+k} \choose r}(n-r-1)\right)\right)$$$$=4\sum_{k=0}^{n-2}\left((2n-2k-3){{k+n} \choose {k+2}}\right)$$$$=4\left(3{{2n-1} \choose n}-2n^2+n-2\right)=6{{2n} \choose n}-8n^2+4n-8$$
Adding it all up we get $$6{{2n} \choose n}-8n^2+4n-8+(2n+5)(n-1)^2+8n-8+4= 6{{2n} \choose n}+2n^3-7n^2+4n-7$$
