Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.