1

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

M.P
  • 13
  • 3
  • 1
    Welcome to MSE. You'll get a lot more help, and fewer votes to close, if you show that you have made a real effort to solve the problem yourself. What are your thoughts? What have you tried? How far did you get? Where are you stuck? This question is likely to be closed if you don't add more context. Please respond by editing the question body. Many people browsing questions will vote to close without reading the comments. – saulspatz Jan 05 '20 at 13:15
  • It depends on how many repetitions there are in the table. If every letter is the same the number of combinations is far fewer than if they are all different. – almagest Jan 05 '20 at 13:28
  • it doesn't matter whether the words are unique or not maybe i did not do a good job of clarifying that
    what I'm asking is the number of possible words, unique or not, meaning that if a word appears twice (for example once in a straight line and once diagonally) it is counted as 2 possible words     – M.P Jan 05 '20 at 14:30
  • So the letters are irrelevant. You need to give some specific examples for small $k$. I assume that you mean for $k=2$ there are 6 length 2 and 4 length 1. For $k=3$ there are 8 length 3, 20 length 2, and 9 length 1. For $k=4 there are 10 length 4, 24 length 3, 42 length 2, and 16 length 1. Is that correct? – almagest Jan 05 '20 at 17:06
  • If that is so then for some $n$ the formula is obvious. Eg if $n=k$ it is $2k+2$. For $n=1$ it is $k^2$. It would be helpful if you amended the question to make it clearer and put in any partial results you have. – almagest Jan 05 '20 at 17:08
  • i have edited the question and have set max min values for k and n – M.P Jan 05 '20 at 18:45

1 Answers1

0

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$.

almagest
  • 18,380