2
$\begingroup$

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

$\binom{m}{k}=R_{k}+C_{k}+\sum\limits_{j=1}^{k-1}R_{j}C_{k-j}.$

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.

$\endgroup$
2
  • $\begingroup$ Where does the restriction that $k\leq 2m$ come from? For $k > m$, you already have everything is 0... $\endgroup$
    – ARupinski
    Feb 9, 2012 at 3:42
  • $\begingroup$ Because I want things like $R_{m-1}C_{2}$ to be zero. $\endgroup$
    – FelipeG
    Feb 10, 2012 at 17:42

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Very, very nice! $\endgroup$ Feb 9, 2012 at 21:31
  • $\begingroup$ I think the way it works is if you edit your own question or answer 4 times it becomes CW. $\endgroup$ Feb 9, 2012 at 22:14
  • $\begingroup$ The threshold is 8 times, actually. Aaron’s answer was CW since the first revision, so this is not it. $\endgroup$ Feb 10, 2012 at 11:12
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes , that exactly what I meant. by "Given R1, the system has a unique solution." thanks for clearing this out. $\endgroup$
    – FelipeG
    Feb 10, 2012 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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