How many $6$ digit numbers there are, where first and last digits and also consecutive digits are not equal?

Question

We have a 6 digit number $a_1a_2a_3a_4a_5a_6$ and $a_1 \neq 0$

also $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6, a_6 \neq a_1$

All of numbers where $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6$ are $9^6$
I'm having troubles with the last case.
I know that this is generalization of $a_1a_2a_3$ for which there are $8*9^2$ numbers but cannot figure out how they are related

and this is the source file which counts all those digits.

bool foo(int num)
{
    char str[15] = {};
    int i=0;
    while(num)
    {
        str[i]=num%10;
        num/=10;
        i++;
    }
    str[i]=str[0];
     for(int j=0;j<i;j++)
            if(str[j]==str[j+1])
                return false;
    return true;
}

int main()
{
    int sum=0;
    for(int i=100000;i<=999999;i++)
        if(foo(i))
            sum++;
    cout<<sum;
    return 0;
}

Please note that this program produces answer: 478305, which is correct
Also note that the answer 8*9^5 misses some cases

Answer 1

Let $f(n)$ denote the number of strings $a_1\cdots a_n$, where no consecutive digits are equal, and $a_1\ne a_n$. Let $g(n)$ be the number of strings where no consecutive digits are equal, but $a_1 = a_n$. The OP notes that $f(n)+g(n)=9^n$.

We'll write down a recurrence involving both $f$ and $g$, and solve for $f$. It's easy to see that $f(1)=9$, $f(2)=9^2$, $f(3)=8\cdot 9^2$. So suppose $n\ge 4$; to compute $g(n)$, we assume $a_n=a_1$. We have $9$ choices for each of $a_1,\ldots, a_{n-2}$. The number of choices for $a_{n-1}$ depends on whether $a_{n-2} = a_n$ or not. If so, there are $9$ choices, and there are $g(n-2)$ ways for this to happen. If not, there are only $8$ choices for $a_{n-1}$, and there are $f(n-2)$ ways for this to happen.

This gives the recurrence $g(n)=9 g(n-2) + 8 f(n-2)$. Substituting $g(n)=9^n-f(n)$ we see $$ f(n) = 8\cdot 9^{n-1} + f(n-2),\,n\ge 4.$$

We conclude $f(6)= 8\cdot 9^5 + 8\cdot 9^3 + 9^2 = 478305.$

Answer 2

WRONG ANSWER (for reason noted below)

a1 can be any one of 9 numbers, (1,2,...,9)
a2 can be any one of 9 numbers, (0,1,...,9 not a1)
.
.
.
a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1)

These choices are all unique and exhaustive. So I get 9^5 * 8.

CORRECTION: Saying that a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1) IS WRONG if a5=a1. In that case, a6 can be any one of 9 numbers.

Answer 3

Here's another approach. We will do cases based on the digits in positions $1$, $3$, and $5$.

Case 1:

$a$, ___ , $a$, ____, $a$, ____.

There are $9$ ways to select the digit $a$, and $9$ ways to fill each blank. So $9^4$ numbers of interest in this case.

Case 2.1, 2.2, 2.3:

$a$, ___ , $a$, ____, $b$, ____

and $a$, ___ , $b$, ____, $b$, ____

and $b$, ___ , $a$, ____, $a$, ____

For each of three subcases, there are $9\cdot 9$ ways to choose $a$ and $b$, and $9\cdot 8\cdot 8$ ways to fill the blanks. So there are a total of $3\cdot 9^3\cdot 8^2$ numbers of interest in these three subcases combined.

Case 3:

$a$, ___ , $b$, ____, $c$, ____.

There are $9\cdot 9\cdot 8$ ways to choose $a, b,c$, and $8$ ways to fill each blank. So there are a total of $9^2\cdot 8^4$ numbers of interest in this case.

Grand total: $9^4+3\cdot 9^3\cdot 8^2+9^2\cdot8^4=478305$ numbers of interest.

Answer 4

You need to examine each position - whether it is the same as $a_1$, or not. Although this is slow in general, it's OK with a few cases, like here for n=6. So here we go, I denote different choices with different letters:

1. $a_1 = A$ - 9 choices. | A | _ | _ | _ | _ | _ |

2. $a_2 = B$ - 9 choices. | A | B | _ | _ | _ | _ |

3.A. $a_3 = a_1 = A$ - 1 choice. Then $a_4 = D$ - 9 choices. | A | B | A | D | _ | _ |

• 3.A.4.A. $a_5 = a_1 = A$ - 1 choice, then $a_6$ - 9 choices
  - in total $\fbox{$9^4$}$ | A | B | A | D | A | F |

• 3.A.4.B $a_5 = E \ne a_1$ - 8 choices, then $a_6$ has 8 choices

  - in total $\fbox{$9^3.8^2$}$ | A | B | A | D | E | F |

---

3.B. $a_3 = C \ne a_1$ - 8 choices | A | B | C | _ | _ | _ |

• 3.B.4.A. $a_4 = A$ - 1 choice => $a_5 = E\ne A$ - 9 choices => $a_6 = F$ - 8 choices

  - in total $\fbox{$9^3.8^2$}$ | A | B | C | A | E | F |

---

• 3.B.4.B. $a_4 = D\ne a_1$ - 8 choices | A | B | C | D | _ | _ |

  • 3.B.4.B.5.A. $a_5 = a_1 = A$ - 1 choice => $a_6 = F$ - 9 choices
    - in total $\fbox{$9^3.8^2$}$ | A | B | C | D | A | F |

  • 3.B.4.B.5.B $a_5 = E\ne a_1$ - 8 choices => $a_6 = F$ - 8 choices
    - in total $\fbox{$9^2.8^4$}$ | A | B | C | D | E | F |

---

And now, just sum up the results: $3.9^3.8^2+9^4+9^2.8^4 = $478305, exactly what we needed.

Tad's response is also great and timely!