The Fractal and the Recurrence Equations Concerning the Integer Partitions

Abstract

This paper introduced a way of fractal to solve the problem of taking count of the integer partitions, furthermore, using the method in this paper some recurrence equations concerning the integer partitions can be deduced, including the pentagonal number theorem.

Share and Cite:

Zhang, M. (2018) The Fractal and the Recurrence Equations Concerning the Integer Partitions. Advances in Pure Mathematics, 8, 624-630. doi: 10.4236/apm.2018.86036.

1. Introduction

A partition of a positive integer n is a way of writing n as a sum of positive integers. The number of partitions of n is given by the partition function $p\left(n\right)$ . In the history of researching the expression of $p\left(n\right)$,the methods such as generating functions and complex analysis are widely used. The fractal can not only describe lots of the natural phenomena, but also work in the recurrence equations. In this paper a new method of fractal will be used to deduce some recurrence equations concerning the integer partitions, including the pentagonal number theorem.

2. Preliminaries

It is well known that the Mandelbrot set  is generated by the recurrence equation ${Z}_{n+1}={Z}_{n}^{2}+\text{C}$,where ${Z}_{n}$ is a complex number and C is a complex constant   . In this paper let us call the recurrence equation ${Z}_{n+1}={Z}_{n}^{2}+\text{C}$  the generator of the Mandelbrot set. Next we should find the generator of the integer partition functions. It is defined that $p\left(m\right)=0$ if $m<0$ and $p\left(0\right)=1$ . Let us call the value m in $p\left(m\right)$ the tab of $p\left(m\right)$ . Here let us write an equation below,

$p\left(n\right)=\left\{p\left(0\right)\right\}+\left\{p\left(1\right)\right\}+\left\{p\left(2\right)\right\}+\cdots +\left\{p\left(i\right)\right\}+\cdots +\left\{p\left(n-1\right)\right\}$,(1)

where $\left\{p\left(i\right)\right\}$ is called a parcel here.

To accomplish the proof of the main theorem in the next section, some conceptions are required. Let us call the elements in the symbol { } and the symbol itself a parcel. Every parcel may generate other parcel(s). Let us call a parcel which has generated its child-parcel(s) a father-parcel. A parcel has a father-parcel if it is generated by other parcel.

Let us define that a parcel is surrounded with the symbol { } if it has not generated its child-parcel(s), otherwise the parcel and its child-parcel(s) are surrounded with the symbol [ ], let us call the elements in the symbol [ ] and the symbol itself a cell. The symbol [ ] has the same meaning with the brackets in arithmetic. In this paper the symbol [ ] is different from the symbol , denotes a rounding down function which will be used later. The child-parcel(s) are the repeated count in their father-parcel, they should be subtracted from their father-parcel. Here let us define that a parcel will lost the symbol { } out of itself if it has generated its child-parcel(s). Next we should find the expression of every parcel.

3. Deducing the Generator

Definition 1

$\Omega \left(n\right)$ is a function that can let n be written as an arbitrary partition.

For example, $\Omega \left(15\right)=7+8$ is an expression of the partitions of integer 15. The number of representations of $\Omega \left(n\right)$ is $p\left(n\right)$ .

Definition 2

m is called a fixed number if $n=m+\Omega \left(n-m\right)$,where m cannot be divided.

Let us assume the sum of the child-parcel(s) that a parcel will generate is

$\underset{i=0}{\overset{\lambda }{\sum }}\left\{p\left(i\right)\right\}$,we should find the $\lambda$ in it.

The Main Theorem

In a cell, let $\lambda$ denote the quantity of the child-parcel(s) that a parcel $\left\{p\left(\tau \right)\right\}$ will generate, let n denote the tab in its father-parcel, then $\lambda =2\tau -n$ . $\lambda =0$ if $2\tau -n\le 0$ .

Proof

When n is an odd number, let t and $\left\{p\left(n-t\right)\right\}$ be bijection. When $1\le t,let t be a fixed number, the count of partition mapped t is $p\left(n-t\right)$,here let us sign it $\left\{p\left(n-t\right)\right\}$ because $p\left(n-t\right)$ has repeat count.

Let us divide n into t and $n-t$,let $\xi \left(i\right)$ denote the number in the section $\left[t,n-t\right]$,where $t\le i\le n-t$ . Because $t+\xi \left(i\right)\le n$,let $\phi$ denote the largest $\xi \left(i\right)$,we have $\phi =n-t$ . (2)

$\phi =n-t>n/2>t$ because $t . Now let us regard $\phi$ as the fixed number, the partition count of $n=\phi +t+\Omega \left(n-t-\phi \right)$ can be mapped as $p\left(n-t-\phi \right)$ because it has been counted when $\phi$ is a fixed number. Using formula (2) we have $p\left(n-t-\phi \right)=\left\{p\left(0\right)\right\}$ .

Also, we can regard every number in the section $\left(t,\phi \right)$ as a fixed number.

Therefore, in the section $\left[t,\phi \right]$,every number can be mapped by order as

$\left\{p\left(n-t-\phi \right)\right\}=\left\{p\left(0\right)\right\}$ $↔$ $n=\phi +t+\Omega \left(n-t-\phi \right)$,

$\left\{p\left(n-t-\left(\phi -1\right)\right)\right\}=\left\{p\left(1\right)\right\}$ $↔$ $n=\left(\phi -1\right)+t+\Omega \left(n-t-\left(\phi -1\right)\right)$,

$\left\{p\left(n-t-\left(\phi -2\right)\right)\right\}=\left\{p\left(2\right)\right\}$ $↔$ $n=\left(\phi -2\right)+t+\Omega \left(n-t-\left(\phi -2\right)\right)$,

$\cdots$

$\left\{p\left(n-t-\left(t+1\right)\right)\right\}=\left\{p\left(n-2t-1\right)\right\}$ $↔$ $n=\left(t+1\right)+t+\Omega \left(n-t-\left(t+1\right)\right)$,

where “ $↔$ ” is a symbol of bijection.

Then let us calculate the count of the equations above, we have

$\lambda =n-2t-1-0+1=n-2t$ .

Thus,

$\lambda =n-2t=n-2\left(n-\tau \right)=2\tau -n$ because $\tau =n-t$ .

When $n/2\le t\le n$,there is no number in the section $\left[t,n-t\right]$,thus $\lambda =0$ because $n-2t\le 0$ if $\left(2\tau -n\right)\le 0$ .

In the situation of even, the process of analysis is as same as odd. This concludes the proof of the main theorem.

For example, let us use the generator to calculate $p\left(10\right)$ . Let us regard $p\left(10\right)$ as a father-parcel, using the main theorem (or it can be called the generator), at first, every parcel has not generated its child-parcel(s), so they are surrounded by the symbol { }, next, every parcel generates its child-parcel(s) and has become a cell, the child-parcel(s) are arranged by order according to their tabs, their first child-parcel should be $p\left(0\right)$ . The quantity of the child-parcel(s) that a parcel will generate is given by the main theorem. Therefore the tab of the last child-parcel equals the quantity of the child-parcel(s) minus 1. The process of generating will be continued until there is no parcel can generate its child-parcel(s). We can “zoom in” $p\left(10\right)$ entirely with 5 steps, which are shown below.

p(10)= $\underset{i=0}{\overset{9}{\sum }}\left\{p\left(i\right)\right\}$

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−{p(0)}−{p(1)}]+[p(7)−{p(0)}

−{p(1)}−{p(2)}−{p(3)}]+[p(8)−{p(0)}−{p(1)}−{p(2)}−{p(3)}

−{p(4)}−{p(5)}]+[p(9)−{p(0)}−{p(1)}−{p(2)}−{p(3)}−{p(4)}

−{p(5)}−{p(6)}−{p(7)}]

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−{p(0)}

−{p(1)}]]+[p(9)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−{p(0)}]−[p(6)

−{p(0)}−{p(1)}−{p(2)}]−[p(7)−{p(0)}−{p(1)}−{p(2)}−{p(3)}

−{p(4)}]]

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)−p(1)]]

+[p(9)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)]−[p(6)−p(0)−p(1)

−p(2)]−[p(7)−p(0)−p(1)−p(2)−p(3)−[p(4)−{p(0)}]]]

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)−p(1)]]

+[p(9)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)]−[p(6)−p(0)−p(1)

−p(2)]−[p(7)−p(0)−p(1)−p(2)−p(3)−[p(4)−p(0)]]]

=42. (3)

One can note that the equation above has the feature: self-similarity, of course, this is the property of the fractal.

On the one hand $p\left(n\right)$ can be “zoomed in” on a form as $p\left(n\right)=\underset{i=0}{\overset{n-1}{\sum }}\left\{p\left(i\right)\right\}$,

on the other hand, in fact, for $p\left(n\right)$,the last term $\left\{p\left(n-1\right)\right\}$ in $p\left(n\right)$ can be mapped as the sum of n integer 1, there is only one way to express $\left\{p\left(n-1\right)\right\}$,so the last term can be 1. Thus $p\left(n\right)$ can be “zoomed in” on a form as

$p\left(n\right)=\underset{i=0}{\overset{n-2}{\sum }}\left\{p\left(i\right)\right\}+1$ .

Also, for p(10), it can be “zoomed in” entirely with 4 steps, we have

p(10)= $\underset{i=0}{\overset{8}{\sum }}\left\{p\left(i\right)\right\}$ +1

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−{p(0)}−{p(1)}]+[p(7)−{p(0)}

−{p(1)}−{p(2)}−{p(3)}]+[p(8)−{p(0)}−{p(1)}−{p(2)}−{p(3)}

−{p(4)}−{p(5)}]+1

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−{p(0)}

−{p(1)}]]+1

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)−p(1)]]+1

=42. (4)

It is easy to find that $p\left(n\right)$ also can be “zoomed in” on a form as if we have gotten the content which will be discussed later. Also p(10) can be “zoomed in” entirely with 3 steps, we have

p(10)= $\underset{i=0}{\overset{7}{\sum }}\left\{p\left(i\right)\right\}$ +ë10/2û+1

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−{p(0)}−{p(1)}]+[p(7)−{p(0)}

−{p(1)}−{p(2)}−{p(3)}]+10/2+1

=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)−p(1)]+[p(7)−p(0)−p(1)

−p(2)−p(3)]+10/2+1

=42. (5)

In the fact that $p\left(n\right)$ can be “zoomed in” entirely with fewer steps if we can find some proper functions and exchange the terms in $p\left(n\right)$ for these functions.

4. The Application of the Generator

Now let us reach an agreement that the main theorem in the section above is called the generator. As an example, let us use the generator to calculate $p\left(n\right)$ in a finite range. Here the last term $\left\{p\left(n-1\right)\right\}$ can be mapped as the sum of $\left(n-1\right)$ integer 1 to add up, there is only one way to express $\left\{p\left(n-1\right)\right\}$,so the last term is 1.

Let us assume $2\le n\le 12$,at first we have

p(n)={p(n−n)}+ ∙∙∙ +{p(ën/2û)}+{p(n−x)}+ ∙∙∙ +{p(n−2)}+1. (6)

We should calculate x first. $\left\{p\left(n-x\right)\right\}$ is the first parcel that will generate its child-parcel(s), $n-x>n/2$,then $x,therefore, $x<6$ .

The tabs in the equation from left to right are arranged from small to large, therefore x should has the largest value in the range. Thus we know $x=5$ .

Using the generator, we know the quantity of child-parcel(s) that a parcel will generate, also we know the first child-parcel should be $p\left(0\right)$ and the child-parcel(s) are arranged by order according to their tabs. The quantity of the child-parcel(s) that a parcel will generate is given by the generator, therefore the tab of the last child-parcel equals the quantity of the child-parcel(s) minus 1. because the number in and the number $\left(n-5\right)$ in $p\left(n-5\right)$ should be continuous, we have

p(n)={p(n−n)}+ ∙∙∙ +{p(ën/2û)}+{p(n−5)}+ ∙∙∙ +{p(n−2)}+1

=p(n−n)+ ∙∙∙ +p(n−6)

+[p(n−5)−p(n−12)−p(n−11)]

+[p(n−4)−p(n−12)−p(n−11)−p(n−10)−p(n−9)]

+[p(n−3)−p(n−12)−p(n−11)−p(n−10)−p(n−9)−p(n−8)−[p(n−7)

−p(n−12)]]

+[p(n−2)−p(n−12)−p(n−11)−p(n−10)−p(n−9)−p(n−8)−p(n−7)

−[p(n−6)−p(n−12)−p(n−11)]−[p(n−5)−p(n−12)−p(n−11)

−p(n−10)−p(n−9)]]+1. (7)

Given a nonnegative integer n, now let us use the generator to calculate $p\left(n\right)$ directly.

Example: Calculate $p\left(11\right)$ and $p\left(12\right)$ by using the generator.

p(11)=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)]+[p(7)−p(0)−p(1)−p(2)]

+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)]+[p(9)−p(0)−p(1)−p(2)−p(3)

−p(4)−[p(5)−p(0)]−[p(6)−p(0)−p(1)−p(2)]]+1

=56, (8)

p(12)=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+p(6)+[p(7)−p(0)−p(1)]+[p(8)−p(0)

−p(1)−p(2)−p(3)]+[p(9)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)]]

+[p(10)−p(0)−p(1)−p(2)−p(3)−p(4)−p(5)−[p(6)−p(0)−p(1)]−[p(7)

−p(0)−p(1)−p(2)−p(3)]]+1

=77. (9)

Let us calculate $p\left(n-1\right)$ when $2\le n\le 12$,this is a preparing work for the next chapter. The process of analysis is as same as $p\left(n\right)$ above.

p(n−1)={p((n−1)−(n−1))}+ ∙∙∙ +{p(ë(n−1)/2û)}+{p(n−1−5)}+ ∙∙∙ +

{p(n−1−2)}+1

=p(n−n)+ ∙∙∙ + p(n−7)

+[p(n−6)−p(n−12)]

+[p(n−5)−p(n−12)−p(n−11)−p(n−10)]

+[p(n−4)−p(n−12)−p(n−11)−p(n−10)−p(n−9)−p(n−8)]

+[p(n−3)−p(n−12)−p(n−11)−p(n−10)−p(n−9)−p(n−8)−[p(n−7)

−p(n−12)]

−[p(n−6)−p(n−12)−p(n−11)−p(n−10)]]+1. (10)

5. Deducing Some Recurrence Equations

Now let us consider the Equation (7) and (10), let $p\left(n\right)-p\left(n-1\right)$,we have

$p\left(n\right)=p\left(n-1\right)+p\left(n-2\right)+p\left(n-12\right)-p\left(n-5\right)-p\left(n-7\right)$ . (11)

That is the pentagonal number theorem  -  when $2\le n\le 12$ .

Let us change the tail of the Equation (7) or (10) to get some new results.

It is easy to prove that when n is an even number, the count of the integer partitions which 2 is the largest number equals $n/2$,when n is an odd number, it equals $\left(n-1\right)/2$ .

$\left\{p\left(n-2\right)\right\}$ can be exchanged for because $\left\{p\left(n-2\right)\right\}$ equals the count of the integer partitions which 2 is the largest number.

Therefore, p(11) and p(12) can be calculated as follows:

p(11)=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+[p(6)−p(0)]+[p(7)−p(0)−p(1)−p(2)]

+[p(8)−p(0)−p(1)−p(2)−p(3)−p(4)]+(11−1)/2+1

=56, (12)

p(12)=p(0)+p(1)+p(2)+p(3)+p(4)+p(5)+p(6)+[p(7)−p(0)−p(1)]+[p(8)−p(0)

−p(1)−p(2)−p(3)]+[p(9)−p(0)−p(1)−p(2)−p(3)−p(4)−[p(5)−p(0)]]+

12/2+1

=77. (13)

Now we can see that if we let and let $p\left(n-1\right)=\underset{i=0}{\overset{n-3}{\sum }}\left\{p\left(i\right)\right\}+1$,in fact, in a larger range, when $2\le n\le 24$,after being

“zoomed in” entirely both for $p\left(n\right)$ and $p\left(n-1\right)$,making $p\left(n\right)-p\left(n-1\right)$,we have

$p\left(n\right)=p\left(n-1\right)+p\left(n-6\right)+p\left(n-8\right)+p\left(n-20\right)+p\left(n-21\right)+p\left(n-22\right)$

$+2p\left(n-23\right)+2p\left(n-24\right)-p\left(n-11\right)-2p\left(n-13\right)-p\left(n-14\right)-p\left(n-15\right)$

$-p\left(n-16\right)-p\left(n-17\right)+\left(n-k\right)/2$ (k = 0 if n is even, k = 1 if n is odd). (14)

Let and let , when $2\le n\le 24$,after being “zoomed in”

entirely both for $p\left(n\right)$ and $p\left(n-1\right)$,making $p\left(n\right)-p\left(n-1\right)$,we have

$p\left(n\right)=p\left(n-1\right)+p\left(n-3\right)+p\left(n-12\right)+p\left(n-14\right)+p\left(n-16\right)+p\left(n-18\right)$

$+p\left(n-20\right)-p\left(n-7\right)-p\left(n-9\right)-p\left(n-11\right)-p\left(n-13\right)+k$ (k = 1 if n is even, k = 0 if n is odd). (15)

Let $p\left(n\right)=\underset{i=0}{\overset{n-1}{\sum }}\left\{p\left(i\right)\right\}$ and let $p\left(n-1\right)=\underset{i=0}{\overset{n-2}{\sum }}\left\{p\left(i\right)\right\}$,when $2\le n\le 24$,after

being “zoomed in” entirely both for $p\left(n\right)$ and $p\left(n-1\right)$,making $p\left(n\right)-p\left(n-1\right)$,we have

$p\left(n\right)=2p\left(n-1\right)+p\left(n-6\right)+p\left(n-8\right)+p\left(n-12\right)+p\left(n-15\right)-p\left(n-3\right)$

$-p\left(n-5\right)-p\left(n-7\right)-p\left(n-13\right)-p\left(n-16\right)-p\left(n-24\right)$ . (16)

Let $p\left(n\right)=\underset{i=0}{\overset{n-2}{\sum }}\left\{p\left(i\right)\right\}+1$ and let $p\left(n-1\right)=\underset{i=0}{\overset{n-3}{\sum }}\left\{p\left(i\right)\right\}+1$,also when

$2\le n\le 24$,after being “zoomed in” entirely both for $p\left(n\right)$ and $p\left(n-1\right)$,making $p\left(n\right)-p\left(n-1\right)$,we have

$p\left(n\right)=p\left(n-1\right)+p\left(n-2\right)+p\left(n-12\right)+p\left(n-15\right)-p\left(n-5\right)-p\left(n-7\right)$

$-p\left(n-22\right)$ (the pentagonal number theorem). (17)

6. Conclusions

All the recurrence equations appearing above are deduced by the generator which has been deduced in this paper. The pentagonal number theorem is a special case between them, in fact, we can get more recurrence equations.

There is an inference that the count of the kinds of the recurrence equations like above whose form is $F\left(p\left(n\right),p\left(n-1\right),\cdots ,p\left(0\right)\right)+G\left(n\right)=0$ should be infinite, where $F\left({x}_{0},{x}_{1},\cdots ,{x}_{n}\right)$ is a simple equation and $G\left(n\right)$ is a function of n. It is because of that the count of the terms that the equation $p\left(n\right)$ has can be infinite if n is infinite; in the first step of “zooming in” $p\left(n\right)$,every term of the second half of the equation $p\left(n\right)$ can be exchanged for a function $G\left(n\right)$ freely.

Conflicts of Interest

The authors declare no conflicts of interest.

  Mandelbrot, B.B. (1982) The Fractal Geometry of Nature. W. H. Freeman Co Ltd., New York, 3-26.  Schroeder, M.R. (2009) Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. Dover Publications Inc., New York, 12-25.  Andrews, G.E. (1984) The Theory of Partitions. Cambridge University Press, Cambridge, 1-10. https://doi.org/10.1017/CBO9780511608650  Andrews, G.E. and Eriksson, K. (2004) Integer Partitions. Cambridge University Press, Cambridge, 3-9. https://doi.org/10.1017/CBO9781139167239  Hardy, G.H. and Wright, E.M. (2008) An Introduction to the Theory of Numbers. 5th Edition, Oxford University Press, Oxford, 361-389.  Alder, H.L. (1969) Partition Identities—From Euler to the Present. The American Mathematical Monthly, 76, 733-746. https://doi.org/10.2307/2317861  Andrews, G.E. (1983) Euler’s Pentagonal Number Theorem. Mathematics Magazine, 56, 1-12. https://doi.org/10.1080/0025570X.1983.11977058  Stanley, R.P. (1971) Ordered Structures and Partitions. Thesis, Harvard University, Cambridge, MA, 1-89.     customer@scirp.org +86 18163351462(WhatsApp) 1655362766  Paper Publishing WeChat 