[Math] How many combination of numbers

combinatoricspermutations

Anyone can give me an idea how I approach calculating the following problem. How many possible valid numbers, where a valid number is any number between 0-9, length of 10 digits, excluding # or *, a piece of Chess can trace while travelling across a telephone keypad. Here say I have a King, it can move only as in a real game, in any direction but only a single cell at a time.

So the keypad looks like this:

     1  2  3
     4  5  6
     7  8  9
     *  0  #

So the piece makes 10 moves each time and each unique number created by it is a valid number. A piece starts its journey from an initial starting position.

The pieces can move or stay in one place (where moving or staying will both count as a move) as well as revisit the cells (as long as its allowed within their respective moving rights). So for example if a King moves from position 1 a three valid 10-move paths to create a valid number number could be 1236547890 or 1111111111 or 1212121212

All help much appreciated.

Best Answer

I'll consider the "king" case, without the ability to "pass"; the other cases can be resolved similarly. Let $S_{\text{king}}(n,p)$ be the number of $n$-digit numbers with the king ending at $p \in \{0,1,\ldots,9\}$.

We have:

  • Boundary conditions: $S_{\text{king}}(1,p)=1$ for all $p \in \{0,1,\ldots,9\}$. (I'll assume we can start wherever we want.)

  • Recurrence relations:

    • $S_{\text{king}}(n,1)=\sum_{p \in \{2,4,5\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,2)=\sum_{p \in \{1,3,4,5,6\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,3)=\sum_{p \in \{2,5,6\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,4)=\sum_{p \in \{1,2,5,7,8\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,5)=\sum_{p \in \{1,2,3,4,6,7,8,9\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,6)=\sum_{p \in \{2,3,5,8,9\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,7)=\sum_{p \in \{0,4,5,8\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,8)=\sum_{p \in \{0,4,5,6,7,9\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,9)=\sum_{p \in \{0,5,6,8\}} S_{\text{king}}(n,p)$,

    • $S_{\text{king}}(n,0)=\sum_{p \in \{7,8,9\}} S_{\text{king}}(n,p)$.

This gives:

$$\scriptsize \begin{array}{r|rrrrrrrrrr|r} & p=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & \text{sum} \\ \hline n=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 10 \\ 2 & 3 & 5 & 3 & 5 & 8 & 5 & 4 & 6 & 4 & 3 & 46 \\ 3 & 18 & 24 & 18 & 26 & 35 & 26 & 22 & 29 & 22 & 14 & 234 \\ 4 & 85 & 123 & 85 & 128 & 185 & 128 & 104 & 145 & 104 & 73 & 1160 \\ 5 & 436 & 611 & 436 & 642 & 902 & 642 & 531 & 722 & 531 & 353 & 5806 \\ 6 & 2155 & 3058 & 2155 & 3202 & 4551 & 3202 & 2619 & 3601 & 2619 & 1784 & 28946 \\ 7 & 10811 & 15265 & 10811 & 15984 & 22611 & 15984 & 13138 & 17977 & 13138 & 8839 & 144558 \\ 8 & 53860 & 76201 & 53860 & 79802 & 113108 & 79802 & 65411 & 89694 & 65411 & 44253 & 721402 \\ 9 & 269111 & 380432 & 269111 & 398274 & 564041 & 398274 & 326857 & 447787 & 326857 & 220516 & 3601260 \\ 10 & 1342747 & 1898811 & 1342747 & 1988228 & 2816703 & 1988228 & 1630618 & 2234819 & 1630618 & 1101501 & 17975020 \\ \end{array}$$

So there are $17975020$ phone numbers with $10$-digits that can be dialled by a king.

(There are some "sanity checks" we can apply to the above numbers. E.g. $S(n,1)=S(n,3)$ by symmetry.)

The above numbers were computed in GAP using the following code:

M:=[[1,1,1,1,1,1,1,1,1,1]];  # index 10 represents 0
for n in [2..10] do
  M[n]:=[];
  M[n][1]:=Sum([2,4,5],p->M[n-1][p]);
  M[n][2]:=Sum([1,3,4,5,6],p->M[n-1][p]);
  M[n][3]:=Sum([2,5,6],p->M[n-1][p]);
  M[n][4]:=Sum([1,2,5,7,8],p->M[n-1][p]);
  M[n][5]:=Sum([1,2,3,4,6,7,8,9],p->M[n-1][p]);
  M[n][6]:=Sum([2,3,5,8,9],p->M[n-1][p]);
  M[n][7]:=Sum([4,5,8,10],p->M[n-1][p]);
  M[n][8]:=Sum([4,5,6,7,9,10],p->M[n-1][p]);
  M[n][9]:=Sum([5,6,8,10],p->M[n-1][p]);
  M[n][10]:=Sum([7,8,9],p->M[n-1][p]);
od;

In a previous version of the question, there was a condition on the 10-digits being unique. This is a much harder problem, and amounts to counting the number of hamilton paths in various $10$-vertex graphs. Note that finding a hamilton path is an NP-complete problem (ref.). Nevertheless, this enumeration should be achievable using a backtracking algorithm (judging from the above numbers). There's probably not a much better way than this; see these Stackoverflow questions here and here.

Related Question