0

How many combinations can be made from a 10 digit number given these rules?

Rules:

  • you can only use the digits 0, 1 and 2
  • the difference between the digits can only be 0 or 1, so you can have 2222222222 or 0000000000 or 0112112100 but not 2011211221 since the difference between the digits should be equal to or less than 1.
Christoph
  • 24,912
significantfigure
  • 13

1 Answers1

1

Can't think of nice closed form, but here's a nice linear recursion:

Let $f_n$ be the number of combinations obeying those two rules of length n, and let $g_n$ be the number of those that end with $1$, and $h_n$ be the number that end with $0$. Note that $h_n$ is also the number of such combinations that end with $2$ because of the symmetry, so $f_n$ = $g_n + 2 \cdot h_n$.

But $g_n = f_{n-1}$, because I can always add a $1$ to the end of any such combination of length $n-1$ to get a combination of length $n$, and pulling off a $1$ from the end of such a combination of length $n$ still obeys the two rules. To get a length $n$ combination that ends with $0$, though, the preceding combination has to end with a $0$ or a $1$, so $h_n = g_{n-1} + h_{n-1}$. So, we get $$f_n = f_{n-1} + 2 \cdot \left( g_{n-1} + h_{n-1} \right) \\ = 2 \cdot f_{n-1} + g_{n-1} \\ = 2 \cdot f_{n-1} + f_{n-2}$$

Callus - Reinstate Monica
  • 5,507
  • The question didn't ask for a closed form, just for $f_{10}$. From $f_1=3$, $f_2=7$, and the recursion, it shouldn't be too hard to work out $f_{10}$. If you need a closed form, it will involve the roots of $x^2-2x-1$. – Gerry Myerson Apr 01 '14 at 09:46
  • @Christoph, I think you have your matrix set up incorrectly --- anyway, it does not agree with the recurrence Callus has written. – Gerry Myerson Apr 01 '14 at 10:00
  • @GerryMyerson You are right, it's $\pmatrix{f_{n-1}\f_n} = \pmatrix{0&1\1&2} \pmatrix{f_{n-2}\f_{n-1}}$, and then your polynomial is of course correct, my bad. Deleted the wrong comments. – Christoph Apr 01 '14 at 10:03
  • I'm still sort of confused - how did you simplify the first statement into the third statement? – significantfigure Apr 01 '14 at 12:21
  • @GerryMyerson how did you derive the closed form? – significantfigure Apr 01 '14 at 12:28
  • I didn't --- but there's a completely standard way to solve linear homogeneous constant-coefficient recurrences. You can probably find several examples done on this website in answer to various questions, and it's in every textbook on discrete math, and on lots of other websites, I'm sure. The closed form will be $Ca^n+Db^n$ where $a,b$ are roots of $x^2-2x-1$ and $C,D$ are determined from the initial conditions $f_1,f_2$. – Gerry Myerson Apr 01 '14 at 12:32
  • @significantfigure I used that $f_{n-1} = g_{n-1} + 2 \cdot h_{n-1}$ then I used that $g_{n-1} = f_{n-2}$. To get the closed form, I think the technique would be to diagonalize the matrix as $M = S^{-1}DS$ with $D$ diagonal. It is then easy to find what the powers of $M$ are in terms of the eigenvalues of $M$ ( which are the entries of $D$ ), which as GerryMyerson points out, will be roots of $x^2 - 2x -1$. – Callus - Reinstate Monica Apr 02 '14 at 00:22