Word and number ladder puzzles

Question

Introduction

$ \begin{array}{} \begin{array}{c|c|c} \text{1} & \text{SIZE}\\ \hline 2 & \\ 3 & \\ 4 & \\ 5 & \\ \hline 6 & \text{RANK} \end{array} & \begin{array}{c|c|c} 1 & \text{SIZE}\\ \hline 2 & \text{SINE} \\ 3 & \text{LINE} \\ 4 & \text{LINK} \\ 5 & \text{RINK} \\ \hline 6 & \text{RANK} \end{array} \end{array} $

On the left is an example of a Word Ladder puzzle, invented (allegedly) by Lewis Carroll. One possible solution is on the right. The aim is to place a valid word in each row that is the same as the one preceding it except for one letter change. There are four words to fill in, so there are five letter changes between the start and end: at least one additional letter must be introduced (the L in line 3 of my example.)

I got to wondering how many possible solutions a given puzzle may have. Puzzles vary in this because of the restriction that all words must be valid, but if we use numbers instead of words that restriction disappears. Furthermore, in the word problem all eight of the given letters are different, but in my digital version I want to allow duplicates.

So I am attempting to calculate the number of ways that one $4$-digit number may be changed into another, changing one digit at a time, such that all the $4$-digit numbers are different, and five changes are made (so over six lines). Leading $0$'s and duplicate digits are allowed.

First case and a solution
The easiest case to enumerate is where none of the digits in the final row are in the same position in the starting row (e.g. changing $1234$ into $5678$ or changing $1234$ into $4321$). Four of the five digit changes are "fixed" in that once a digit is placed in its correct position in the final row it can't be changed. The other change I call "free" in that it doesn't appear in that position in the final row, so any valid digit will do.

Here is an example using numbers: \begin{array}{ll} 1234 & \text{ Start}\\ \hline 5234 & 5 \text{ is fixed}\\ 5634 & 6 \text{ is fixed}\\ 5639 & 9 \text{ is free}\\ 5679 & 7 \text{ is fixed}\\ \hline 5678 & 8 \text{ is fixed} \end{array}

The four fixed digits can appear in any order, and so these lines contribute a factor of $4!$ to the total.

Which leaves the line containing the free digit. The number of possibilities for this line depends on when it is introduced: as more of the fixed digits are put in position, there are fewer places for the free digit to go. Although all 10 digits are theoretically available, each line must be different to the one(s) preceding it (i.e. one digit must change each time), and the free digit must not be the same as the digit in the same position in the final line (or it wouldn't be free). So only eight digits are available.
The possibilities of what can happen where are:

\begin{array}{clcc} \text{Line}^1 & \text{Positions available} & \text{Possible lines}\\ \hline 2 & 4 & 32\\ 3 & 3 & 24\\ 4 & 2 & 16\\ 5 & 1 & \phantom{0}8 \end{array} $^1$ i.e. the line in which the free digit is introduced.
So the line containing the free digit can appear in $32+24+16+8 = 80$ ways. Putting all this together, there are $24 \cdot 80 = 1920$ possible ways to complete each game.

Other cases
The next case is where one of the target digits is already in position, e.g. changing $1234$ into $1678$. There are two cases here:

i) force the target digit already in position to change. Another line then has to be used up to change it back again, so there is room for only one free digit.

ii) do not change the target digit already in position. The problem becomes one of changing the other three digits over five lines, so two free digits are required. There are $\binom42 = 6$ ways in which they can be introduced (the final change must be fixed, not free). This gives six sub-cases of varying complexity. As above, the number of possibilities depends on when the free digits come in. I shan't take up time and space describing them here.

The remaining cases (changing $1234$ into $1278$ (up to three free digits) and changing $1234$ into $1238$ (up to four free digits)) have increasing complexity.

My question
Is there an easier way to enumerate all this? Maybe consider the whole problem in one go rather than considering all these cases? Or a different way to divide into cases that makes for easier computation?

Answer 1

The number of ways to pick which digit gets changed at step $i$ is $4\binom{5}{1,1,1,2}=60,$ where we can pick one of the four digits to be changed twice and then pick the the rounds when each digit is changed.

(More intuitively, this is: $$\binom5{2,1,1,1}+\binom5{1,2,1,1}+\binom5{1,1,2,1}+\binom5{1,1,1,2},$$ but all those terms are equal. $\binom{n}{n_1,\dots,n_k}$ is the multi nominal - the number of ways to partition a set of size $n$ into an ordered list of $k$ parts of sizes $n_i$ for $i=1,\dots,k.$ In particular, $\sum_{i} n_i=n,$ and when $k=2,$ $\binom{n}{a,n-a}=\binom{n}a,$ the usual binomial.)

The only digit which is free to choose is the one "free digit," which can be changed to something which is neither the goal digit nor the final digit, so there are $8\cdot 4\cdot 60$ total solutions.

---

This assumes all the digits change from start to finish. You get different formula for starting at $1234$ and wanting to end at $2354,$ since the last digit doesn't need to change, and if it changes on the free choice, it can change to $9$ distinct values.

The number will depend on the number $i$ of digits that don't change from start to finish.

It gets harder when the number of steps increases, too. For example, in seven rows/six changes, if $i=0,$ we can get $6\cdot \binom{6}{2,2,1,1}$ cases where two digits can be chosen freely in $8^2$ ways, or $4\binom6{3,1,1,1}$ ways to change one digit three times, which can be done in $9\cdot 8$ ways.

In general, if a digit changes $k$ times, from $d$ to $e,$ then the number of ways it can change is (where $\delta=\delta_{de}$ is $1$ if $d=e$ and $0$ otherwise): $$f(\delta,k)=\begin{cases}1&k=0, \delta=1\text{ or }k=1,\delta=0\\ 0&k=0,\delta=0\text{ or }k=1,\delta=1\\ 8\cdot 9^{k-2}&k>1,\delta=0\\ 9^{k-1}&k>1,\delta=1 \end{cases}$$

Then the number of solutions in $k$ changes with $m$ digits starting $d_1,\dots,d_m$ and ending $e_1,\dots,e_m$ is:

$$\sum_{k_1+\cdots+k_m=k}\binom{k}{k_1,\dots,k_m}\prod_{i} f(\delta_{d_ie_i},k_i)$$

In your case, all $d_i\neq e_i$ and thus the $k_i=0$ cases contribute $0,$ and we are left with $(k_i)=(2,1,1,1)$ and permutations.

By symmetry, this is a function if $k,m$ and the number of digits, $c,$ with $d_i=e_i.$

---

For example, in your case, if one digit is unchanged, when $m=4, k=5, c=1,$ you get:

$$3\binom5{0,1,2,2}f(0,2)^2+3\binom5{0,1,1,3}f(0,3)+\binom 5{2,1,1,1}f(1,2)\\=3\cdot 30\cdot 8^2+3\cdot 20\cdot 8\cdot 9+60\cdot 9$$

You can also probably do a recursion:

$$F_{m,k,c}=\\\begin{cases}0&c+k<m\text{ or }m=0&c+k>0\\ k!&c+k=m\\ F_{m-1,k,c-1}+\sum_{i=2}^{\min(k,c+k-m)}9^{i-1}\binom ki F _{m-1,k-i,c-1}&c>0\\kF_{m-1,k-1,0}+ \sum_{i=2}^{\min(k,m-k)}8\cdot 9^{k-2}\binom ki F_{m-1,k-i,0}&c=0\end{cases}$$

So $m=4, k=5, c=2$ gives:

$$F_{4,5,0}=5 F_{3,4,0}+8\binom52 F(3,3,0)$$

$F(3,3,0)=3!$ You quickly see a pattern:

$$F{4,5,0}= 8\binom52 3!+5\cdot 8 \binom42 2!+5\cdot 4\cdot 8\binom 32 1!+5\cdot4\cdot 3\binom{2}20!$$

But each of those terms is just $\binom{5}{2,1,1,1}.$