Number of ways the letters of two k-letter words can match $M(k) :=$ the number of ways the letters of two (ordered) k-letter words can match.
$M(1) = 2$: the single letters of the two words are either matching or not. 
$M(2) = 12$:
$$\begin{array}{ c|c c }
      & A & A \\\hline
    B & \circ & \circ \\
    B & \circ & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & A \\\hline
    A & \bullet & \bullet \\
    A & \bullet & \bullet \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    A & \bullet & \circ \\
    B & \circ & \bullet \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    B & \circ & \bullet \\
    A & \bullet & \circ \\
\end{array}$$
$$\begin{array}{ c|c c }
      & A & B \\\hline
    A & \bullet & \circ \\
    C & \circ & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    B & \circ & \bullet \\
    C & \circ & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    C & \circ & \circ \\
    A & \bullet & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    C & \circ & \circ \\
    B & \circ & \bullet \\
\end{array}$$
$$\begin{array}{ c|c c }
      & A & A \\\hline
    A & \bullet & \bullet \\
    B & \circ & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & A \\\hline
    B & \circ & \circ \\
    A & \bullet & \bullet \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    A & \bullet & \circ \\
    A & \bullet & \circ \\
\end{array}
\begin{array}{ c|c c }
      & A & B \\\hline
    B & \circ & \bullet \\
    B & \circ & \bullet \\
\end{array}$$
How to calculate $M(k)$?
The upper bound for $M(k)$ is obviously $2^\left(k^2\right)$, because each letter from the first word is either matching with any of the letters of the second word or not, but not all "match patterns" are possible. 
Based on computer simulation $M(3) = 128, M(4) = 2100, M(5) = 48032$.
Two example matches for k=5 out of the 48032:
$$\begin{array}{ c|c c }
      & A & B & C & C & D\\\hline
    A & \bullet & \circ & \circ & \circ & \circ \\
    A & \bullet & \circ & \circ & \circ & \circ \\
    B & \circ & \bullet & \circ & \circ & \circ \\
    B & \circ & \bullet & \circ & \circ & \circ \\
    C & \circ & \circ & \bullet & \bullet & \circ \\
\end{array}\begin{array}{ c|c c }
      & A & B & C & D & E\\\hline
    A & \bullet & \circ & \circ & \circ & \circ \\
    A & \bullet & \circ & \circ & \circ & \circ \\
    B & \circ & \bullet & \circ & \circ & \circ \\
    C & \circ & \circ & \bullet & \circ & \circ \\
    D & \circ & \circ & \circ & \bullet & \circ \\
\end{array}$$

After some time trying to solve definitively the problem @Tamas finally found a paper with the "solution".
Based on the calculated values of $M$ given by a computer program that checked all possible matrices, $M(n)$ gives the https://oeis.org/A014235 series. It's formula is therfore is $\sum_{k=0}^{n} k! * S(n+1, k+1)^2$ where $S$ is the function to get the Stirling numbers of the second kind. 
The general case for a matrix of $n\times m$ is $\sum_{k=0}^{\min(n,m)} k!\cdot S(m+1, k+1) S(n+1, k+1)$
The problem discussed in the referenced paper of the series can be directly applied to this problem. (On the link provided the answer is the section 3.1 named "$\Gamma$-avoiding matrices".)
