If I have a table which has $k$ columns and $k$ rows (same number of rows and columns) that contains letters of the English alphabet, what are the number of $n$ letter combinations I can create from this table while $n \le k$? Letters can be chosen in a straight line or diagonally. Any formulas for this?
Edit:
k is max 9 and min 3
n is between 3 and 9
I assume that the chosen letters have to be without gaps. So you can pick the second, third and fourth letters in a row, but not the first, second and fourth. I also assume that order is unimportant, so picking the second, third, fourth a row is the same as picking the fourth, third, second.
There are $2k$ rows and columns and 2 diagonals length $k$. There are 4 diagonals for each length $2,3,\dots,k-1$. Let's call all of these "lines".
We now count the words length $m$. Call the number in a $k\times k$ square $w(k,m)$. Clearly $w(k,1)=k^2$.
Since we are ignoring duplicates there are are $m-1$ runs of 2 letters in a line of length $m$. So for $m<k$ there are $4\left(1+2+\dots+(k-2)\right)$ in the diagonals length $2,3,\dots,k-1$ and $(2k+2)(k-1)$ in the lines length $k$, so $w(k,2)=2(k-1)(2k-1)$ (note this also gives the correct value for $k=2$).
Similarly $$w(k,3)=4(1+2+\dots+(k-3))+(2k+2)(k-2)=4(k-2)(k-1)$$ and in general (for $1<n\le k$) $$w(k,n)=4(1+2+\dots+(k-n))+(2k+2)(k-n+1)=2(k-n+1)(2k-n+1)$$
Check: for $k=5$ and $n=1,2,3,4,5$ we get $25,72,48,28,12$.