0
$\begingroup$

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.
$\endgroup$

1 Answer 1

1
$\begingroup$

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}$$

$\endgroup$
7
  • $\begingroup$ 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$. $\endgroup$ Apr 1, 2014 at 9:46
  • $\begingroup$ @Christoph, I think you have your matrix set up incorrectly --- anyway, it does not agree with the recurrence Callus has written. $\endgroup$ Apr 1, 2014 at 10:00
  • $\begingroup$ @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. $\endgroup$
    – Christoph
    Apr 1, 2014 at 10:03
  • $\begingroup$ I'm still sort of confused - how did you simplify the first statement into the third statement? $\endgroup$ Apr 1, 2014 at 12:21
  • $\begingroup$ @GerryMyerson how did you derive the closed form? $\endgroup$ Apr 1, 2014 at 12:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .