Take the 2-minute tour ×

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
What if $n=3$? Then we can have $a=0, b=2, c=1$. –  Rick Decker Jul 3 '12 at 18:49
@RickDecker: Fixed. –  Ross Millikan Jul 3 '12 at 18:53
@RossMillikan: Thank you Ross. Could you please explain a bit about the sum? I understand it's a product of the number of ways to choose A and the number of ways to choose B. But why the sum? Many thanks. –  cody Jul 3 '12 at 20:41
The 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) –  Ross Millikan Jul 3 '12 at 20:48

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.

share|improve this answer
I'm curious. May I see that recurrence relation, Rick? Thank you. –  cody Jul 3 '12 at 19:19
@cody If you lick on the link I provided you'll find it (and see why I chose not to copy it in my answer). –  Rick Decker Jul 3 '12 at 19:32
Oh, I see. Quite ugly! Do you know how they derived that recurrence relation? Thank you. –  cody Jul 3 '12 at 19:43
@cody Sorry, but I haven't a clue how it was derived. –  Rick Decker Jul 3 '12 at 20:19

Your Answer


