MathOverflow is a question and answer site for professional mathematicians. 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

Working with cellular automata I came across a system of equations for unknown integers $R_{k}$ and $C_{k}$ that looks like this.


Where 0< k$\leq$ 2m

(for k>m we take $\binom{m}{k}=R_{k}=C_{k}=0$)

Given $R_{1}$, the system has a unique solution.

Has anyone seen something similar? Do you know if it still possible to solve it, if instead of $\binom{m}{k}$ in the left you put something else?

I just want to know if it's related to something else, and if it's possible to solve more general systems.

share|cite|improve this question
Where does the restriction that $k\leq 2m$ come from? For $k > m$, you already have everything is 0... – ARupinski Feb 9 '12 at 3:42
Because I want things like $R_{m-1}C_{2}$ to be zero. – FelipeG Feb 10 '12 at 17:42
up vote 7 down vote accepted

So piggybacking off the two two good answers so far, a system of equations $$a_k=R_k+C_k+\sum\limits_{j=1}^{k-1}R_{j}C_{k-j} \text{ for } 1 \le k \le M$$ is a system of $M$ equations in $2M$ variables which starts out

$$\begin{align} R_1 + C_1 &= a_1\\\ R_2+C_2&= a_2-R_1C_1 \\\ R_3+C_3 &= a_3- R_2C_1 - R_1C_2 \\\ R_4+C_4 &= a_4- R_3C_1 - R_2C_2-R_1C_3\\\ \end{align}$$

This can be solved top down leading to an a branching cascade of solutions where at stage $j$ we have $$R_j+C_j=b_j$$ where $b_j$ depends of the previous choices. If the $a_i$ are non-negative integers and we want the solutions to be of the same form then at that stage we have $\max(0,b_j+1)$ choices.

The system is equivalent to $$\left(1+\sum_1^MC_jx^j\right)\left(1+\sum_1^MR_jx^j\right)=1+\sum_1^Ma_jx^j+O(x^{M+1})$$

If we add enough conditions to make it equivalent to $$\left(1+\sum_1^MC_jx^j\right)\left(1+\sum_1^MR_jx^j\right)=1+\sum_1^Ma_jx^j$$ then there is some number of solutions (at most $2^M$) depending on how the right-hand side factors (and the conditions).

One set of conditions which does this is that $M=2m$ and $R_j=C_j=0$ for $j \gt m.$

If we say that the $a_j$ are in $\mathbb{Z}$ and the $R_j,C_j$ should be rational then there will be some solutions and they will all be integers (one is $R_j=0$ and $C_j=a_j$).

As noted, in the given problem the $m+1$ solutions come from $(1+x)^t(1+x)^{m-t}=(1+x)^m$ so they are $C_j=\binom{t}{j},R_j=\binom{m-t}{j}$ for some non-negative integer $t \le m.$

It is a disguised form of a classic problem to solve the case that the $a_k$ are all $1$ for $k \le m$ and the $C_i,R_i$ should be nonegative.

share|cite|improve this answer
Very, very nice! – Barry Cipra Feb 9 '12 at 21:31
I think the way it works is if you edit your own question or answer 4 times it becomes CW. – Gerry Myerson Feb 9 '12 at 22:14
The threshold is 8 times, actually. Aaron’s answer was CW since the first revision, so this is not it. – Emil Jeřábek Feb 10 '12 at 11:12

Here something is being said about the generating functions r(t) and c(t) for the $R_{k}$ and $C_{k}$; we'd better agree to begin with that $R_{0}$ and $C_{0}$ for that purpose are both equal to 1. You want in fact to multiply: the product r(t)c(t) is determined by your equation, coefficient by coefficient. So far, so good.

On the face of it, you are saying in fact that the product r(t)c(t) is the same as mth power of 1 + t. If you simply force r(t) and c(t) to be polynomials, then under this condition the uniqueness of factorisation of polynomials means here there are only the powers of 1 + t possible. I think this isn't what you are actually saying, or intending, so I'm a bit puzzled at this point. With r(t) and c(t) as just any power series you can't expect uniqueness at all: there are numerous invertible power series. The "boundary condition" forcing r(t) and c(t) to be polynomials is very strong, therefore.

share|cite|improve this answer

I agree with Charles Matthews, there's something that doesn't seem right in the formulation of the problem. Consider what you get for $m=2$:

$$\begin{align} {2 \choose 1} &= R_1 + C_1 \\\ {2 \choose 2} &= R_2 + R_1C_1 + C_2\\\ {2 \choose 3} &= R_3 + R_2C_1 + R_1C_2 + C_3\\\ {2 \choose 4} &= R_4 + R_3C_1 + R_2C_2 + R_1C_3 + C_4 \end{align}$$

Given the assumptions made for $k>m$, this becomes

$$\begin{align} 2 &= R_1+C_1\\\ 1 &= R_2 + R_1C_1 + C_2\\\ 0 &= R_2C_1 + R_1C_2\\\ 0 &= R_2C_2 \end{align}$$

This has just three possible solutions $(R_1,C_1,R_2,C_2)$: $(0,2,0,1)$ $(1,1,0,0)$, and $(2,0,1,0)$, so it's not clear what's meant by saying "Given $R_1$, the system has a unique solution." Here's my guess:

For each $m$, the system has $m+1$ solutions, each solution is in non-negative integers, and there is exactly one solution for each integer $0 \le R_1 \le m$.

This is certainly true for $m=1$ and $m=2$ and seems to be true for $m=3$ as well (I checked but didn't doublecheck that case).

Added later: Aaron Meyerowitz has taken this quite a bit further, so read his answer, not this one.

share|cite|improve this answer
Yes , that exactly what I meant. by "Given R1, the system has a unique solution." thanks for clearing this out. – FelipeG Feb 10 '12 at 18:10

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.