How many sequences can be made with 5 digits so that the difference between any two consecutive digits is $1$

combinatoricssolution-verification

Using the digits $0$, $1$, $2$, $3$, and $4$, how many ten-digit sequences can be written so that the difference between any two consecutive digits is $1$?

I was wondering if my solution is right.

Let $a(n)$ be the number of $n$ digit sequences that end with $0$ or $4$ so that the difference between any two consecutive digits is $1$.

$b(n)$ be the number of n digit sequences that end with $1$ or $3$ so that the difference between any two consecutive digits is $1$.

$c(n)$ be the number of n digit sequences that end with $2$ so
that the difference between any two consecutive digits is $1$.

$x(n)$ be the number of n digit sequences so that the difference between any two consecutive digits is $1$.

$x(n) = a(n) + b(n) + c(n)$

$a(n) = b(n-1)$

$b(n) = a(n-1) + 2c(n-1)$

$c(n) = b(n-1)$

By substituting $a(n-1)$ and $c(n-1)$ in the formula for $b(n)$ we get $b(n) = 3b(n-2)$

We know that $b(1) = 2, b(2) = 4$.

The characteristic equation for this recursion is $x^2-3 = 0$ with have the roots $3^{1/2}$ and $-3^{1/2}$, so $b(n) = A{(3^{1/2})}^{n} + B{(-3^{1/2})}^{n}$ where $A = {(3^{1/2}+2)}/{3}$ and $B = {(2-3^{1/2})}/{3}$. I think this is an integer.

We get $x(n) = 2b(n-1) + 3b(n-2)$ and by substituting we get something.

Best Answer

Your approach looks good to me but you have to check the final result somehow. You can do that with 15 lines of code:

#include <iostream>
using namespace std;

int count(int startDigit, int length) {
    if(startDigit < 0 || startDigit > 4) {
        return 0;
    }
    if(length == 1)
        return 1;
    return count(startDigit - 1, length - 1) + count(startDigit + 1, length - 1);
}

int main() {
    cout << count(1, 10) + count(2, 10) + count(3, 10) + count(4, 10);
}

...and the result is 567.

Related Question