A machine can perform $3$ types of operation $A$, $B$ and $C$. The memory is initially $0$. A Program $P$ is a series of these operations. If the machine does $A$, it will add $1$ to the memory's current value. If it does $B$, it will subtract $1$ from the memory. If it does $C$, it will add $2$ to the memory (It is kind of like a Turing machine). How many programs are there if they are of length $n$ and set the memory to zero after execution? And how can I derive a recurrence relation to solve this problem recursively?
What's the recurrence relation to this problem?
2
$\begingroup$
algorithms
recurrence-relations
2 Answers
2
You are looking for words of length $n$ on A, B, and C. If there are $a$ A's, $b$ B's, and $c$ C's, the constraints are $a+b+c=n,\ \ a-b+2c=0$ With two equations in three unknowns, you have one free parameter. We can take $c$ as the free parameter. Then $a+b=n-c, \ \ a-b=-2c, a=\frac {n-3c}2,\ \ b=\frac {n+c}2$, so $c$ must have the same parity as $n$. The number of words is $\sum_{i=0}^{\lfloor \frac n3 \rfloor}\binom n{\frac{n-3i}2}\binom{n-\frac{n-3i}2}{\frac{n+i}2}$
I don't see a simple recurrence relation for this.
-
0The sum is over the number of c's. Given the number of c's, you calculate the number of a's and b's. Then the product is the number of ways to choose positions for the a's and then the b's in the word. If n=6, you can have (a,b,c)=(3,3,0), or (0,4,2) – 2012-07-03
2
This is A176806. The formula OEIS gives is $ a(n) = \sum_{\lfloor\frac{n+2}{3}\rfloor}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{k}\binom{k}{3k-n} $ There is a recurrence relation for it, but it's quite ugly.
-
0@cody Sorry, but I haven't a clue how it was derived. – 2012-07-03