Previously, we have explored methods to compute the essence of power functions $Ȣx^n$ which involves solving a large system of linear equations. This method is equivalent to solving for the inverse of a large $n\times n$ matrix where entries are values of pascal's triangle. Though the matrix method allow us to solve for large number of essences at once, it does not extend easily to solve for next iterations of essence coefficients. Rather than reusing the values we have already solved for, we will have to solve for inverse of a separate larger matrix again. Here we will introduce an iterative method for solving for these coefficients. Chapter 0: Recap Let us first remind ourselves of the definition of essence. For a function $f(x)$, we want to find the transformation $Ȣf(x)$ such that we are able to 'smooth out' its series: $$\sum_{i=a}^b f(i) = \int_{a-1}^b Ȣf(x) dx$$ For example, we can solve for the following functions: $$\begin{align*}Ȣ1 &= 1 \\ Ȣx &= x +
Partitions are number of ways an integer can be represented as sum of positive integers. We can ask, for example, what is the partition of 5? If we write out every possible combination,
$$\begin{align*}
5 &= 1+1+1+1+1 \\
&= 1+1+1+2\\
&= 1+1+3\\
&= 1+4\\
&= 1+2+2\\
&= 2+3\\
&= 5 \end{align*} $$ we can see that partition of 5 is 7. One will immediately notice, however, that this is not the most efficient approach to answering the question: not only does partition grow quickly, attempting to organize and not miss or repeat an algebraic expression becomes messy and impractical.
We can confirm that our two rules are satisfied. We also realize that now counting the partition of $n$ is simply counting the number of terminating nodes in the $n$-Tree. If we let $P(n)$ be partition counting function, we easily can count that
$$\begin{align*}
P(1) &= 1\\
P(2) &= 2\\
P(3) &= 3\\
P(4) &= 5\\
P(5) &= 7\\
P(6) &= 11
\end{align*}
$$ Readers may try to figure out a systematic approach to generating these trees. Try to generate 7-Tree as a fun exercise.
We can discover a more interesting fact from these Partition-Trees: the 1-branch (the branch with 1 as the parent node) is simply the whole of the previous Tree. This will perhaps be more clear once branches are colored:
For example, the 1-branch of 6-Tree is the same as the whole of the 5-Tree. Same is true for 1-branch of 5-Tree, and so on. Next, we can notice that the 2-branch of 6-Tree is a sub-tree of 4-Tree, namely sub-tree excluding the 1-branch (cover up the 1-branch of 4-Tree to see it is identical to 6-Tree's 2-branch). Then, we also notice the same for 6-Tree's 3-branch: it is the same as sub-tree of 3-Tree only involving branches larger than or equal to 3. This pattern continues for all n-branches, explaining why there is no 4,5-branches. Then lastly, we have the $n$ itself, as the last branch.
When $m=1$, $R(n,1)$ is equal to the total partition $P(n)$ for obvious reasons. For when $m>1$, finding the $R(n,m)$ is simply counting the terminating node of n-Tree excluding the branches smaller than $m$. So we find that
$$\begin{align*}
&R(1,1) = 1 && R(2,1) =2 && R(3,1) = 3 && R(4,1) = 5 && R(5,1) = 7 && R(6,1) = 11 \\
&R(1,2) = 0 && R(2,2) = 1 && R(3,2) = 1 && R(4,2) = 2 && R(5,2) = 2 && R(6,2) = 4 \\
&\vdots && && R(3,3) = 1 && R(4,3) = 1 && R(5,3) = 1 && R(6,3) = 2 \\
& && && && R(4,4) = 1 && R(5,4) = 1 && R(6,4) = 1\\
& && && && && R(5,5) = 1&& R(6,5) = 1 \\
& && && && && && R(6,6) = 1
\end{align*}$$ Using this new function, we can make sense of the characteristic we notice above in this formula:
$$R(n,1) = R(n-1,1) +R(n-2,2) + \dots + 1$$ The $R(n-1,1)$ represents the 1-branch of n-Tree, which is identical to the whole to (n-1)-Tree. The $R(n-2,2)$ represents the 2-branch of n-Tree, which is a sub-tree of (n-2)-Tree excluding branches smaller than 2. This pattern continues until the n-branch of n-Tree, which can only be the value $n$ itself. This last n-branch is represented by the +1 at the end.
We can also discover this second identify:
$$R(n,m+1) = R(n,m) - R(n-m,m)$$ This can be derived through induction.
We know that $R(n,2)$ is simply the whole of n-Tree but with its 1-branch removed. Since we know the 1-branch is $R(n-1,1)$, we find that $R(n,2) = R(n,1) - R(n-1,1)$. Similarly, we know that $R(n,3)$ can be reached by simply removing the 2-branch from what remains of $R(n,2)$. Since the 2-branch is represented by $R(n-2,2)$, we find that $R(n,3) = R(n,2) - R(n-2,2)$. This continues for ever branch and thus the identity can be easily seen. $\blacksquare$
Finally, the last observation is that
$$m>n \Rightarrow R(n,m) = 0$$ which again will come as obvious fact.
With these three rules, we can begin calculating the next iterations of partitions by hand.
$$\begin{align*}
\because R(1,1) &= 1, \text{ as a given} \\
R(2,1) &= 1+R(1,1) , \text{ we can stop here because every subsequent terms are 0} \\
&= 1+1 \\
&= 2 \\
&\vdots \\
R(7,1) &= 1 + R(6,1) + R(5,2) + R(4,3) \\
&= 1 + 11 + 2 + 1 \\
&= 15 \\
R(8,1) &= 1 + R(7,1) + R(6,2) + R(5,3) + R(4,4) \\
&= 1 + 15 + 4 + 1+1 \\
&= 22 \\
R(9,1) &= 1 + R(8,1) + R(7,2) + R(6,3) + R(5,4) \\
&= 1 + 22 + R(7,1) - R(6,1) + 2 + 1 \\
&= 1 + 22 + 15 - 11 + 2 + 1\\
&= 30\\
&\vdots
\end{align*}$$ However, like with before, relying on algebraic calculation by hand can become messy and vulnerable to mistakes. A more elegant alternative will be to organize these values into a table.
With the values written on such table, generating the next values becomes as easy as summing up the values on a diagonal of the table. The two recursive formulas translate very neatly into the following graphic:
$$\begin{align*}
R(n,1) &= 1+R(n-1,1) + R(n-2,2) + \dots \\
R(n,m+1) &= R(n,m) - R(n-m,m) \\
R(n,m) &= 0, m > n
\end{align*}$$
Numbers highlighted in blue are being summed to find the number in red.
Now seeing that diagonal method works for known values, we can use it to quickly and visually generate many more partitions.
After iterating bit more, we can reach the following large table:
Let's notice few more interesting facts:
$$\begin{align*}
R(n,n) &= 1\\
R(n,m) &= 1, m > \frac{n}{2}
\end{align*}$$ Both facts may come naturally to the readers.
With more known about positive partitions, let us not try to explore negative and zero partitions. Firstly, it is easy to note that it is meaningless to expand the R-table into negative $m$'s. This becomes most obvious when considering $m=-1$, in words when we are able to use -1 in our partitions of $n$. Because we can simply add infinite pairs of $+1-1$ to already existing positive partitions of $n$, $R(n,-1) = \infty$. Same will be true for $m=0$ and all other negative integers.
More interesting is expanding $n$ to the negatives. Using the second recursive rule, let us set $m=n+1$.
$$ \begin{align*}
R(n,n+1) &= R(n,n) - R(n-n,n) \\
0 &= 1 - R(0,n) \\
\therefore R(0,n) &= 1
\end{align*} $$ This makes intuitive sense as well, because there will always only be one way to represent 0 as sum of positive integers: not adding any integer at all.
If we consider when $m=n+2$, we can find the following:
$$\begin{align*}
R(n,n+2) &= R(n,n+1) - R(n-n-1,n+1) \\
0&=0 - R(-1,n+1) \\
\therefore R(-1,n) &= 0
\end{align*}$$ We can show that partition for every negative integer is zero with a more general proof.
$$m = n + k + 1, k \geq 1 \\
\begin{align*}
R(n,n+k+1) &= R(n,n+k) - R(n-n-k, n+k) \\
0 &= 0 - R(-k,n+k) \\
\therefore R(-k, m) &= 0, k \geq 1
\end{align*}$$ These results allow us to more satisfyingly define our first recursive formula:
$$\begin{align*}
R(n,1) &= R(n-1,1) + R(n-2,2) + \dots + 1\\
&= R(n-1,1) + R(n-2,2) + \dots + R(0,n)\\
&= \sum_{i = 1}^n R(n-i,i)
\end{align*}$$ This also fits in neatly to graphical generation of partitions. In fact, we can simply start with a column of 1s in $n=0$ and begin generating:
The resulting table is consistent with the larger n=23 table above.
Though this is a better method of computing partition and even becomes do-able by hand (and ruler for quide), it still is not the most efficient method for calculating large partitions. Primary reason being that we need to compute the all the necessary Restricted Partitions which we may not be interested in. It may be little more efficient if we could define the subsequent partitions purely in terms of pervious partitions.
We first know from the first recursive formula, that a when $m=1$, it is equal to the sum of terms in the diagonal.
We can also rewrite the second recursive formula to be
$$\begin{align*} R(n,m+1) &= R(n,1) - R(n-1,1) - R(n-2,2) - \dots - R(n-m,m) \\
&= R(n,1) - \sum_{i=1}^m R(n-i,i)
\end{align*} $$ Which can be graphically represented as
Using this second map, we can expand every $m\neq 1$ terms in the first map, ultimately yielding the coefficients we wanted.
Focusing only on the first row, we reach the map-coefficients
For those interested, here is a longer expanded map:
This map shows that
$$P(n) = P(n-1)+P(n-2) - P(n-5) -P(n-7) + P(n-12) + P(n-15) - P(n-22) - P(n-26) + \dots$$
$$\begin{align*}
p_2(n) &= p_2(n-1) + p_2(n-2) \\
p_5(n) &= p_5(n-1) + p_5(n-2) - p_5(n-5) \\
p_7(n) &= p_7(n-1)+p_7(n-2) - p_7(n-5) - p_7(n-7) \\
&\vdots \\
\lim_{m\rightarrow \infty } p_m(n) &= P(n)
\end{align*}$$ Few interesting notes about $p_m(n)$ Partition Approximation: $p_3$, $p_4$ and others are skipped because they are no different than their previous approximations. This is because the 3rd, 4th terms and so on are multiplied by 0.
Second interesting note is that $p_2$ is the same as the famous Fibonacci Sequence. This is mot obvious for smaller terms: $$\begin{align*}
&Fib. &1,1,2,3,5,8,13, 21 , 34,55\dots \\
&Part. &1,1,2,3,5,7,11,15,22,30\dots
\end{align*}$$ Of course, this approximation does not hold for long, but it is interesting to consider the connection or similarities of partitions with fibonacci sequence. And being inspired by them, we can represent these approximation in term of matrices:
$$\begin{align*}
p_2(n) &= \begin{bmatrix}
1 & 0
\end{bmatrix} \begin{bmatrix}
1&1\\
1&0
\end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\
p_5(n) &= \begin{bmatrix}
1&0&0&0&0
\end{bmatrix} \begin{bmatrix}
1&1&0&0&-1 \\
1&0&0&0&0 \\
0&1&0&0&0 \\
0&0&1&0&0\\
0&0&0&1&0
\end{bmatrix} ^n \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0\\ 0 \end{bmatrix} \\
p_7(n) &= \begin{bmatrix}
1&0&0&0&0&0&0
\end{bmatrix} \begin{bmatrix}
1&1&0&0&-1&0&-1 \\
1&0&0&0&0&0&0 \\
0&1&0&0&0&0&0 \\
0&0&1&0&0&0&0 \\
0&0&0&1&0&0&0 \\
0&0&0&0&1&0&0 \\
0&0&0&0&0&1&0 \\
0&0&0&0&0&0&1
\end{bmatrix} ^n \begin{bmatrix}
1\\0\\0\\0\\0\\0\\0
\end{bmatrix} \\
&\vdots
\end{align*}$$ Similar to the derivation of Binet Formula, you may attempt to calculate a closed formula for these approximations using eigenvectors of these matrices, but this will not be covered here (Check out The Linear Algebra View of the Fibonacci Sequence for inspirations on how to approach this).
Let us compare the accuracy of these approximations. In the following graphic, values are highlighted blue if approximation equals the actual partition, green if larger than, and red is less than.
Notice that approximations are accurate for the first few partitions. Namely, if our current approximation uses $m$ terms and the next effective number of terms is $k$ terms, then $p_m(n) = P(n)$ for $n<k$. This may come obvious to the readers, as all the terms in between $m$th and $k$th terms on the map are zeroes.
We will also notice the pairs of green and red rows. This seems to suggest that some approximations will always be under-approximation and others an over-approximation.
Let us see these characteristics continue with larger partitions. Quick disclaimer: due to the limitations of the program used to create the graphic, approximations may get too large (or small) and overflow, displaying the wrong value. To prevent any confusion, these incorrect values are erased and cleaned in the following graphic.
Using more terms yields a better approximation, but will naturally be more computationally expensive. Weighing the accuracy and runtime, it may be more practical to simply calculate the actual partition rather than approximate it.
Let's observe the pattern on the map. Looking at the lengths of chains of 0s, starting from index 0, we get the following sequence of gap lengths:
$$0,0,2,1,4,2,6,3,8,4,10,5,\dots$$ Let $g(k)$ count the $k$th gap length. If we start with index 0, we can get the following piecewise definition.
$$g(k)=\left\{\begin{matrix}
k, & k \text{ is even}\\
\frac{k-1}{2} = \left \lfloor \frac{k}{2} \right \rfloor, & k\text{ is odd}
\end{matrix}\right. $$ Then, we can also notice that the term on the map comes in alternating pairs of +1s and -1s. Let $t(k)$ yield the term that comes after the $k$th gap. Then, we can define $t(k)$ as
$$t(k) = -1^{ \left \lfloor \frac{k}{2} \right \rfloor }=\left\{\begin{matrix}
1, & \left \lfloor \frac{k}{2} \right \rfloor \text{ is even}\\
-1, & \left \lfloor \frac{k}{2} \right \rfloor \text{ is odd}
\end{matrix}\right. $$ Using these two simple functions, we can easily and quickly generate Partition Map for any given length:
Essentially, we conclude that $P(19) = 490P(0)$, but because $P(0) = 1$, we find that $P(19) = 490$. We have already confirmed this is true with the large R-Table above. In above graphic, each expanded term goes to 0 because that is accurate to what is happening during the expansion, but if we left the expanded values behind, we will find that they are all accurate partitions of the previous integers.
Being inspired by this, we can write the following algorithm to compute the first $n$ number of Partitions.
We have looked into various approaches and explorations into more quickly and more cleanly compute large partitions, but we are still shy of reaching that closed functions to yield partitions in one elegant calculation. Hopefully this little journey peaked your interest in dealing with partitions and encouraged you to look into it yourself.
$$\begin{align*}
5 &= 1+1+1+1+1 \\
&= 1+1+1+2\\
&= 1+1+3\\
&= 1+4\\
&= 1+2+2\\
&= 2+3\\
&= 5 \end{align*} $$ we can see that partition of 5 is 7. One will immediately notice, however, that this is not the most efficient approach to answering the question: not only does partition grow quickly, attempting to organize and not miss or repeat an algebraic expression becomes messy and impractical.
Chapter 1: Partition Tree
A cleaner, but still not the best, approach would be to use tree diagrams to represent the partitions of a number. In a Partition Tree of $n$, every path to a terminating node will add up to the number $n$. And also, every child of a node (every nodes below a given parent node) will always be greater than or equal to the parent node in order to not have repeating partitions. With these two rules, we can generate these very organized Partition Trees: |
| First 6 Partition Trees |
$$\begin{align*}
P(1) &= 1\\
P(2) &= 2\\
P(3) &= 3\\
P(4) &= 5\\
P(5) &= 7\\
P(6) &= 11
\end{align*}
$$ Readers may try to figure out a systematic approach to generating these trees. Try to generate 7-Tree as a fun exercise.
We can discover a more interesting fact from these Partition-Trees: the 1-branch (the branch with 1 as the parent node) is simply the whole of the previous Tree. This will perhaps be more clear once branches are colored:
 |
| Color-coded Partition Trees |
Chapter 2: Restricted Partition and Recursive Formulas
With this, we recognize the importance of a restricted version of partition counter which only counts partition excluding usage of terms smaller than $m$. Let us call this Restricted Partition Counter $R(n,m)$ which counts the partition of $n$ only involving terms greater than or equal to $m$.When $m=1$, $R(n,1)$ is equal to the total partition $P(n)$ for obvious reasons. For when $m>1$, finding the $R(n,m)$ is simply counting the terminating node of n-Tree excluding the branches smaller than $m$. So we find that
$$\begin{align*}
&R(1,1) = 1 && R(2,1) =2 && R(3,1) = 3 && R(4,1) = 5 && R(5,1) = 7 && R(6,1) = 11 \\
&R(1,2) = 0 && R(2,2) = 1 && R(3,2) = 1 && R(4,2) = 2 && R(5,2) = 2 && R(6,2) = 4 \\
&\vdots && && R(3,3) = 1 && R(4,3) = 1 && R(5,3) = 1 && R(6,3) = 2 \\
& && && && R(4,4) = 1 && R(5,4) = 1 && R(6,4) = 1\\
& && && && && R(5,5) = 1&& R(6,5) = 1 \\
& && && && && && R(6,6) = 1
\end{align*}$$ Using this new function, we can make sense of the characteristic we notice above in this formula:
$$R(n,1) = R(n-1,1) +R(n-2,2) + \dots + 1$$ The $R(n-1,1)$ represents the 1-branch of n-Tree, which is identical to the whole to (n-1)-Tree. The $R(n-2,2)$ represents the 2-branch of n-Tree, which is a sub-tree of (n-2)-Tree excluding branches smaller than 2. This pattern continues until the n-branch of n-Tree, which can only be the value $n$ itself. This last n-branch is represented by the +1 at the end.
We can also discover this second identify:
$$R(n,m+1) = R(n,m) - R(n-m,m)$$ This can be derived through induction.
We know that $R(n,2)$ is simply the whole of n-Tree but with its 1-branch removed. Since we know the 1-branch is $R(n-1,1)$, we find that $R(n,2) = R(n,1) - R(n-1,1)$. Similarly, we know that $R(n,3)$ can be reached by simply removing the 2-branch from what remains of $R(n,2)$. Since the 2-branch is represented by $R(n-2,2)$, we find that $R(n,3) = R(n,2) - R(n-2,2)$. This continues for ever branch and thus the identity can be easily seen. $\blacksquare$
Finally, the last observation is that
$$m>n \Rightarrow R(n,m) = 0$$ which again will come as obvious fact.
With these three rules, we can begin calculating the next iterations of partitions by hand.
$$\begin{align*}
\because R(1,1) &= 1, \text{ as a given} \\
R(2,1) &= 1+R(1,1) , \text{ we can stop here because every subsequent terms are 0} \\
&= 1+1 \\
&= 2 \\
&\vdots \\
R(7,1) &= 1 + R(6,1) + R(5,2) + R(4,3) \\
&= 1 + 11 + 2 + 1 \\
&= 15 \\
R(8,1) &= 1 + R(7,1) + R(6,2) + R(5,3) + R(4,4) \\
&= 1 + 15 + 4 + 1+1 \\
&= 22 \\
R(9,1) &= 1 + R(8,1) + R(7,2) + R(6,3) + R(5,4) \\
&= 1 + 22 + R(7,1) - R(6,1) + 2 + 1 \\
&= 1 + 22 + 15 - 11 + 2 + 1\\
&= 30\\
&\vdots
\end{align*}$$ However, like with before, relying on algebraic calculation by hand can become messy and vulnerable to mistakes. A more elegant alternative will be to organize these values into a table.
Chapter 3: R-Table and Visual Partition Computation
 |
| R-Table |
$$\begin{align*}
R(n,1) &= 1+R(n-1,1) + R(n-2,2) + \dots \\
R(n,m+1) &= R(n,m) - R(n-m,m) \\
R(n,m) &= 0, m > n
\end{align*}$$
 |
| Recursive Formula being visually confirmed for known values |
Now seeing that diagonal method works for known values, we can use it to quickly and visually generate many more partitions.
 |
| Generating Partitions and Restricted Partitions using a Table |
 |
| R-Table up to n=23 |
$$\begin{align*}
R(n,n) &= 1\\
R(n,m) &= 1, m > \frac{n}{2}
\end{align*}$$ Both facts may come naturally to the readers.
With more known about positive partitions, let us not try to explore negative and zero partitions. Firstly, it is easy to note that it is meaningless to expand the R-table into negative $m$'s. This becomes most obvious when considering $m=-1$, in words when we are able to use -1 in our partitions of $n$. Because we can simply add infinite pairs of $+1-1$ to already existing positive partitions of $n$, $R(n,-1) = \infty$. Same will be true for $m=0$ and all other negative integers.
More interesting is expanding $n$ to the negatives. Using the second recursive rule, let us set $m=n+1$.
$$ \begin{align*}
R(n,n+1) &= R(n,n) - R(n-n,n) \\
0 &= 1 - R(0,n) \\
\therefore R(0,n) &= 1
\end{align*} $$ This makes intuitive sense as well, because there will always only be one way to represent 0 as sum of positive integers: not adding any integer at all.
If we consider when $m=n+2$, we can find the following:
$$\begin{align*}
R(n,n+2) &= R(n,n+1) - R(n-n-1,n+1) \\
0&=0 - R(-1,n+1) \\
\therefore R(-1,n) &= 0
\end{align*}$$ We can show that partition for every negative integer is zero with a more general proof.
$$m = n + k + 1, k \geq 1 \\
\begin{align*}
R(n,n+k+1) &= R(n,n+k) - R(n-n-k, n+k) \\
0 &= 0 - R(-k,n+k) \\
\therefore R(-k, m) &= 0, k \geq 1
\end{align*}$$ These results allow us to more satisfyingly define our first recursive formula:
$$\begin{align*}
R(n,1) &= R(n-1,1) + R(n-2,2) + \dots + 1\\
&= R(n-1,1) + R(n-2,2) + \dots + R(0,n)\\
&= \sum_{i = 1}^n R(n-i,i)
\end{align*}$$ This also fits in neatly to graphical generation of partitions. In fact, we can simply start with a column of 1s in $n=0$ and begin generating:
 |
| Generation of Partition R-Table from n=0 |
Though this is a better method of computing partition and even becomes do-able by hand (and ruler for quide), it still is not the most efficient method for calculating large partitions. Primary reason being that we need to compute the all the necessary Restricted Partitions which we may not be interested in. It may be little more efficient if we could define the subsequent partitions purely in terms of pervious partitions.
Chapter 4: Partition Map-Coefficient
$$P(n) = c_1P(n-1) + c_2P(n-2) + \dots $$ This, of course, can be derive algebraically from our first and second recursive definition by expanding every term with $m>1$, but doing so by hand is not recommended as it becomes too messy and difficult to organize. Better approach will be to again rely on graphical representation of expansion. We will try to create a map showing us which previous terms relative to current term to sum up. Basically on a map, values to sum will be marked with 1 and to subtract is marked with -1. Values to ignore is marked with 0.We first know from the first recursive formula, that a when $m=1$, it is equal to the sum of terms in the diagonal.
 |
| The map for the term circled in red |
$$\begin{align*} R(n,m+1) &= R(n,1) - R(n-1,1) - R(n-2,2) - \dots - R(n-m,m) \\
&= R(n,1) - \sum_{i=1}^m R(n-i,i)
\end{align*} $$ Which can be graphically represented as
 |
| The map for the term in red |
 |
| Expanding the Map for R-Table for the next partition |
 |
| Partition Map for 28 terms |
 |
| Partition Map for 77 terms |
$$P(n) = P(n-1)+P(n-2) - P(n-5) -P(n-7) + P(n-12) + P(n-15) - P(n-22) - P(n-26) + \dots$$
Chapter 5: Approximations using Matrices
Because terms becomes relatively smaller and perhaps even insignificant, we can use the first few terms of the map to compute an approximation of the partition. Let $p_m(n)$ be approximation of $P(n)$ using $m$ number of terms on the map.$$\begin{align*}
p_2(n) &= p_2(n-1) + p_2(n-2) \\
p_5(n) &= p_5(n-1) + p_5(n-2) - p_5(n-5) \\
p_7(n) &= p_7(n-1)+p_7(n-2) - p_7(n-5) - p_7(n-7) \\
&\vdots \\
\lim_{m\rightarrow \infty } p_m(n) &= P(n)
\end{align*}$$ Few interesting notes about $p_m(n)$ Partition Approximation: $p_3$, $p_4$ and others are skipped because they are no different than their previous approximations. This is because the 3rd, 4th terms and so on are multiplied by 0.
Second interesting note is that $p_2$ is the same as the famous Fibonacci Sequence. This is mot obvious for smaller terms: $$\begin{align*}
&Fib. &1,1,2,3,5,8,13, 21 , 34,55\dots \\
&Part. &1,1,2,3,5,7,11,15,22,30\dots
\end{align*}$$ Of course, this approximation does not hold for long, but it is interesting to consider the connection or similarities of partitions with fibonacci sequence. And being inspired by them, we can represent these approximation in term of matrices:
$$\begin{align*}
p_2(n) &= \begin{bmatrix}
1 & 0
\end{bmatrix} \begin{bmatrix}
1&1\\
1&0
\end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\
p_5(n) &= \begin{bmatrix}
1&0&0&0&0
\end{bmatrix} \begin{bmatrix}
1&1&0&0&-1 \\
1&0&0&0&0 \\
0&1&0&0&0 \\
0&0&1&0&0\\
0&0&0&1&0
\end{bmatrix} ^n \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0\\ 0 \end{bmatrix} \\
p_7(n) &= \begin{bmatrix}
1&0&0&0&0&0&0
\end{bmatrix} \begin{bmatrix}
1&1&0&0&-1&0&-1 \\
1&0&0&0&0&0&0 \\
0&1&0&0&0&0&0 \\
0&0&1&0&0&0&0 \\
0&0&0&1&0&0&0 \\
0&0&0&0&1&0&0 \\
0&0&0&0&0&1&0 \\
0&0&0&0&0&0&1
\end{bmatrix} ^n \begin{bmatrix}
1\\0\\0\\0\\0\\0\\0
\end{bmatrix} \\
&\vdots
\end{align*}$$ Similar to the derivation of Binet Formula, you may attempt to calculate a closed formula for these approximations using eigenvectors of these matrices, but this will not be covered here (Check out The Linear Algebra View of the Fibonacci Sequence for inspirations on how to approach this).
Let us compare the accuracy of these approximations. In the following graphic, values are highlighted blue if approximation equals the actual partition, green if larger than, and red is less than.
 |
| Values of $p_m$ Partition Approximations |
We will also notice the pairs of green and red rows. This seems to suggest that some approximations will always be under-approximation and others an over-approximation.
Let us see these characteristics continue with larger partitions. Quick disclaimer: due to the limitations of the program used to create the graphic, approximations may get too large (or small) and overflow, displaying the wrong value. To prevent any confusion, these incorrect values are erased and cleaned in the following graphic.
 |
| Values of $p_m$ Partition Approximation (Overflows Cleaned) |
Chapter 6: Partitions using Algorithms
|
| Partition Map for 28 terms |
$$0,0,2,1,4,2,6,3,8,4,10,5,\dots$$ Let $g(k)$ count the $k$th gap length. If we start with index 0, we can get the following piecewise definition.
$$g(k)=\left\{\begin{matrix}
k, & k \text{ is even}\\
\frac{k-1}{2} = \left \lfloor \frac{k}{2} \right \rfloor, & k\text{ is odd}
\end{matrix}\right. $$ Then, we can also notice that the term on the map comes in alternating pairs of +1s and -1s. Let $t(k)$ yield the term that comes after the $k$th gap. Then, we can define $t(k)$ as
$$t(k) = -1^{ \left \lfloor \frac{k}{2} \right \rfloor }=\left\{\begin{matrix}
1, & \left \lfloor \frac{k}{2} \right \rfloor \text{ is even}\\
-1, & \left \lfloor \frac{k}{2} \right \rfloor \text{ is odd}
\end{matrix}\right. $$ Using these two simple functions, we can easily and quickly generate Partition Map for any given length:
int g(int k){
if(k%2 == 0) return k;
else return k/2; //Relying on Truncation
}
int t(int k){
if( (k/2) % 2 == 0 ) return 1;
else return -1;
}
int[] map(int len){
int[] map = new int[len];
int counter = 0;
int index = 0;
while(index < length){
index += 1 + g(counter);
if(index < len) map[index] = t(counter);
else break;
counter++;
}
return map;
}
But remember that each term on the map can themselves be expanded using the same map. We only need to expand until we get to $P(0)$ because it does not make sense that $P(0) = 1$ is a sum of negative partitions which are all zeroes. Therefore, we should take it as a given that $P(0)=1$. With this in mind, let's compute $P(19)$ using this map-method. Because we know $P(19) = 1*P(19)$, we start with 1 in the 19th position and expand that one until we arrive at 0. |
| Calculating Partition of 19 using Expansion |
 |
| Calculating Partitions of Integers up to 19 using Expansion |
int[] partitions(int len){
int[] partitions = new int[len+1];
partitions[0] = 1;
for(int i = 0; i < len; i++){
int val = partitions[i];
int counter = 0;
int index = i;
while(true){
//Calculating the next gap length
if( counter%2 == 0) index += counter;
else index += counter/2;
index++; //Because each term take up one space
if(index > len) break;
//Expanding using the current value
if( (counter/2)%2 == 0) partitions[index] += val;
else partitions[index] -= val;
counter++;
}
}
return partitions;
}
This method of computing the partition has runtime of $O(n^2)$. Though this is still not a closed expression for $P(n)$, it is still a quite fast alternative. In addition, you only need to compute this partition once (if you know the upper limit fit for your context) and the array can act as a extremely fast look-up table. In fact, this method is more efficient the more often you need to look up the partition value for various integers because you get all $n$ partitions at once.We have looked into various approaches and explorations into more quickly and more cleanly compute large partitions, but we are still shy of reaching that closed functions to yield partitions in one elegant calculation. Hopefully this little journey peaked your interest in dealing with partitions and encouraged you to look into it yourself.
Comments
Post a Comment