Suppose you have a large collection of coloured rods of various lengths, where two rods of the same colour always have the same length, and all the lengths are integer multiples of some smallest unit (say, one centimetre). But unlike the Cuisenaire rods that you might have encountered in primary school, there could be rods with different colours but the same length: five-centimetre green rods, but also five-centimetre purple rods.
How many different ways can you assemble rods from such a collection into an ordered sequence of a given total length, N?
This question (posed in terms of the masses of amino acids, rather than the lengths of rods) was discussed in a recent blog post by John Baez, about the work of the mathematical chemists Shane Hubler and Gheorghe Craciun in their paper Periodic patterns in distributions of peptide masses, BioSystems 109 (2012), 179–185. Most of what I’ve written here is just a recap of the exposition in those two sources, but the main point of this web page is the interactive section below that enables you to play around with the results for different choices for the list of rod lengths.
Suppose we have k different colours for our rods, and the lengths of the rods are m1 ≤ m2 ≤ ... ≤ mk. We require the mi to be positive integers, but we do not require them to be distinct. We will define F(N) as the number of different ways we can line up a selection of rods such that their total length is N, where the order of the rods matters; that is, a red followed by two greens counts as a different way of reaching the total than a green followed by a red followed by a green. And to be clear, we are studying the idealised, mathematical version of this problem, where the supply of rods is inexhaustible: we can’t “run out” of rods of any colour.
There is a simple recurrence formula for F(N), which gives its value at a given positive integer N in terms of its values for smaller integers:
F(N) = F(N – m1) + F(N – m2) + ... + F(N – mk)
This says that the number of ways you can reach a total length of N is equal to the sum of all the various ways you can reach N minus one of the rod lengths, because you can take each of these cases and just add one more rod to get a total of N. This method leads directly to a count that treats differently ordered sums as distinct; there is no need to perform additional calculations to account for different arrangements of the same set of rods.
To make use of this formula, we need to know F(N) for some specific values, but there are some very easy cases that are enough to get the process started. Since there is exactly one way to reach a total length of 0, via an empty set containing no rods, we have F(0)=1. And since the total length of any set of rods can’t be negative, we have F(N)=0 for any negative value of N. The repeated application of the recurrence formula then lets us find F(N) for any positive integer.
But we don’t have to be satisfied with this recurrence formula; it’s also possible to find a direct, closed-form expression for F(N). To see this, suppose we could satisfy the recurrence formula alone (but not the other conditions on F(N)) simply by setting F(N) = xN for some constant x. The formula would then become:
xN = x(N – m1) + x(N – m2) + ... + x(N – mk)
Because both sides of this equation share a factor of xN, it will be satisfied by any x that is a root of the polynomial we get by dividing out that factor and multiplying through by xmk:
P(x) = –xmk + x(mk – m1) + x(mk – m2) + ... + 1 = 0
Since P(x) has degree mk, at least generically it will have mk distinct roots, say x1, x2, ..., xmk. Because the recurrence formula is linear, any linear combination of diffent functions that satisfy it will also satisfy it, so if we can find a linear combination of the mk expressions xiN that also satisfies the initial conditions on F(N) for N = –mk+1, –mk+2, ..., 0, then that linear combination, say:
Fc(N) = a1 x1N + a2 x2N + ... + amk xmkN
will agree with F(N) for all positive integer values of N.
What if the polynomial P(x) has repeated roots? If a root xi has multiplicity p, then as well as being a root of P(x), it will be a root of the first p–1 derivatives of P(x). For example, a root x of multiplicity 2 will also satisfy:
P'(x) = –mk x(mk – 1) + (mk – m1) x(mk – m1 – 1) + (mk – m2) x(mk – m2 – 1) + ... + (mk – mk–1) x(mk – mk–1 – 1) = 0
xN – mk + 1 P'(x) = –mk xN + (mk – m1) x(N – m1) + (mk – m2) x(N – m2) + ... + (mk – mk–1) x(N – mk–1) = 0
xN – mk + 1 P'(x) + (N – mk) x(N – mk) P(x) = –N xN + (N – m1) x(N – m1) + (N – m2) x(N – m2) + ... + (N – mk–1) x(N – mk–1) + (N – mk) x(N – mk) = 0
But the last equation amounts to saying that, for this particular root, we can satisfy the recurrence formula by setting F(N) = N xN. This gives us an extra function we can use, to make up for the reduced number of roots. Similarly, for a root of multiplicity 3, F(N) = N (N – 1) xN will also satisfy the recurrence formula, and so on.
In most cases, the polynomial P(x) will have mostly complex roots, and so the individual terms of the form xiN will be complex. But because P(x) has real coefficients, any complex roots will come in pairs that are conjugate to each other, and so long as the coefficients of the terms involving the conjugate roots in Fc(N) are themselves conjugate, the sum of the two terms for each such pair of complex roots will be real. When P(x) has a negative real root, things don’t work out quite so nicely: the associated term will be real for all integers N, but generally complex-valued in between the integers (the only exception would be if the term had a coefficient of exactly zero, which is very unlikely).
The presence of complex roots or negative real roots allows for the possibility that Fc(N) will be cyclic as well as exponential. It turns out that the root with the largest magnitude is always a real positive number, so for large enough N the function will become purely exponential. But along the way, the complex roots with the largest magnitude can also contribute an overlay of very visible cyclic behaviour.
The interactive panel below lets you enter a list of integers and see a plot of F(N) and Re(Fc(N)), along with plots of the roots of the associated polynomial. As well as the conventional view of the roots in the complex plane, you can see the roots on a magnitude-phase plot, where real roots appear in cyan, and the pair of complex roots with the greatest magnitude are shown in red.
Note: This program finds the polynomial roots by an iterative process that begins with a random set of points. The process can sometimes fail to converge on the roots after a fixed number of attempts, in which case the message “Failed to find roots” will be displayed. You can try again by hitting the Recompute roots button. Also, for high-degree polynomials, small errors in the roots can sometimes mean that the coefficients for Fc(N) cannot be determined accurately, and the continuous curve for Fc(N) will not be plotted along with the discrete values of F(N). When this happens, if you hit the Recompute roots button, the curve can sometimes be computed with the new estimates of the roots.
|
|
|