The tangled equations
Let's revisit our decomposition of 90:
1-1-1; 1-1-2; 1-1-3; 1-2-2; 1-2-3; 1-3-3; 2-2-2; 2-2-3; 2-3-3; 3-3-3.
Thinking back of our elevator metaphor, each of these numbers indicates time spent roaming around a given floor (listening to a previously heard song) and the number actually indicates on which floor the wandering is taking place. So 1-3-3 means you stayed an extra time period on level 1, and two on level 3.
All the paths are then the ways of wasting three time periods on three different floors. BUT, and this is a very important caveat, the numbers have to be in increasing order: 1-3-2 would not be an acceptable path. Indeed, the only ways of taking 3 items with replacement among 1, 2 and 3 with replacement and with numbers increasing are:
1-1-1, 1-1-2, 1-1-3, 1-2-2, 1-2-3, 1-3-3, 2-2-2, 2-2-3, 2-3-3, 3-3-3
Does this help us? Yes, because there is now another hidden recursion in the process!
We were here studying k=3, but what did the breakout look like at k=2? Let us list all the ways of taking 2 items with replacement among 1, 2 and 3 with replacement and with increasing numbers:
1-1, 1-2, 1-3, 2-2, 2-3, 3-3
It can be verified that the sum product here yields 25 which is the value in the second table of the sequences (part 3) for k=2 and N=4.
Based on this sequence for k=2, how can the sequence for k=3 be constructed?
If we look at all sequences starting with 1, then all k=2 sequences listed in red can be added to the right of the 1:
1-1-1, 1-1-2, 1-1-3, 1-2-2, 1-2-3, 1-3-3
If we now look at all sequences starting with 2, only the sequences for k=2 listed in red starting with 2 or 3 can be added as we cannot go back from 2 to 1, yielding:
2-2-2, 2-2-3, 2-3-3
Finally there is only one sequence listed in red starting with 3 that can be added to a 3:
3-3-3
This illustrates how the 10 sequences for k=3 listed at the top of this post can be generated from the k=2 sequences listed in red.
But remember that more than the sequences themselves it is their sum-product that we are interetsed in. Denoting by s_N^i (k) the sum product of all sequences starting with value i at time k for values ranging between 1 and N, then:
This looks a little confusing at first so let's illustrate the process with N=4 in the following figure:
Each column is a new "time point", and each row represents an s_N^i (k). Each arrow is color-coded according to the multiplication involved (times 1 for green, times 2 for orange and times 3 for blue). The last row is the sum of the s_N^i (k) at a given time-point, and – oh miracle! – the sum corresponds to the mysterious sequence observed in the table of our sequences in part 3 for N=4. Another fun fact to notice is that the sum is also the first row shifted by one, which makes sense as:
So now can we actually obtain the full explicit formula for the sequence itself. It involves some work as we unwind the tangled equations, working backwards from s_3^3 (k) to s_3^2 (k) to s_3^1 (k).
The calculations are a little lengthier for $s_3^2(k)$:
And finally:
No easy task, but we finally have our general formula generating the sequence for N=3:
The tangled equations can be used again for N=4:
More generally, we can start working our way backwards for the general case:
However, this has not allowed me to fully grasp the general formula for our sequence of interest s_N^1 (k) = S_N (k) for any N, which is the remaining piece of our puzzle.
An important observation can nonetheless be made. It seems as if the formula for s_1^k (N) is composed of all the integers 1 through N-1 to the power k+1:
The alpha_j coefficients also seem to alternate between positive and negative values.
Now what?
No comments:
Post a Comment