(This is part 6 of a series of posts on iTunes randomness. The introduction and a link to all parts can be found here.)
Thanks to the heuristic of the decomposition in integer powers from the previous section, we can guide our favorite statistical software R as to what linear regression to use.
Let's provide each of the sequences as our dependent variable, and all the integer powers as independent variables to determine, for each N, the alpha_j coefficients from the equation in the previous part:
For N=5, the regression would look something like:
Estimating the coefficients is then straightforward with most softwares, and even by hand considering the solution is most likely exact and thus only requires solving a system of 4 equations with 4 unknowns (any 4 rows of the equation above).
The underlying function generating the sequence for N=5 is:
And so, based on the equation derived in part 3 we obtain:
We now are capable of identifying the coefficients of s_1^k (N), but can we find a pattern in those in order to finally get a general formula for P(k|N), valid for all k and all N?
The next table summarizes the alpha_j coefficients of each of the powers in the equation mentioned at the top of this post:
Let us rewrite the values as fractions and momentarily drop the signs that seem to be in perfect alternance:
Let us take a closer look at this triangular matrix, diagonal by diagonal.
First diagonal: 1, 1, 3/2, 8/3, 125/24, 54/5
The 24 in the denominator hints at factorials yet again. With this in mind, the first terms of the sequence can be re-written as:
We can then view 16 as 4^2 and 125 as 5^3 hinting at k^(k-2). The first diagonal is then k^(k-2) / (k-1)!.
Second diagonal: 1, 2, 9/2, 32/3, 625/24
The 24 hints again at factorials. The sequence can be re-written as:
Encouraged by the formula for the first diagonal, the second diagonal can be written as k^(k-1) / (k-1)!.
Third diagonal: 1/2, 2, 27/4, 64/3
Based on the previous two formulas can we generalize? We would have hoped for k^k / (k-1)! for this new sequence but unfortunately the formula doesn't work. It is just off by a half: k^k / (2(k-1)!).
Third diagonal: 1/6, 4/3, 27/4
We have now become experts and the sequence is k^k / (6(k-1)!).
i-th row, j-th column:
Based on the previous findings, we can generalize the element on the i-th row and j-th column to be:
Adding the sign back in:
Is it me or does it feel like the end is right around the corner?