The Fractal and the Recurrence Equations Concerning the Integer Partitions ()
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
. In the history of researching the expression of
,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 [1] is generated by the recurrence equation
,where
is a complex number and C is a complex constant [1] [2] . In this paper let us call the recurrence equation
[2] the generator of the Mandelbrot set. Next we should find the generator of the integer partition functions. It is defined that
if
and
. Let us call the value m in
the tab of
. Here let us write an equation below,
,(1)
where
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
is a function that can let n be written as an arbitrary partition.
For example,
is an expression of the partitions of integer 15. The number of representations of
is
.
Definition 2
m is called a fixed number if
,where m cannot be divided.
Let us assume the sum of the child-parcel(s) that a parcel will generate is
,we should find the
in it.
The Main Theorem
In a cell, let
denote the quantity of the child-parcel(s) that a parcel
will generate, let n denote the tab in its father-parcel, then
.
if
.
Proof
When n is an odd number, let t and
be bijection. When
,let t be a fixed number, the count of partition mapped t is
,here let us sign it
because
has repeat count.
Let us divide n into t and
,let
denote the number in the section
,where
. Because
,let
denote the largest
,we have
. (2)
because
. Now let us regard
as the fixed number, the partition count of
can be mapped as
because it has been counted when
is a fixed number. Using formula (2) we have
.
Also, we can regard every number in the section
as a fixed number.
Therefore, in the section
,every number can be mapped by order as
,
,
,
,
where “
” is a symbol of bijection.
Then let us calculate the count of the equations above, we have
.
Thus,
because
.
When
,there is no number in the section
,thus
because
if
.
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
. Let us regard
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
. 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”
entirely with 5 steps, which are shown below.
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)}]+[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
can be “zoomed in” on a form as
,
on the other hand, in fact, for
,the last term
in
can be mapped as the sum of n integer 1, there is only one way to express
,so the last term can be 1. Thus
can be “zoomed in” on a form as
.
Also, for p(10), it can be “zoomed in” entirely with 4 steps, we have
p(10)=
+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
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)=
+ë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
can be “zoomed in” entirely with fewer steps if we can find some proper functions and exchange the terms in
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
in a finite range. Here the last term
can be mapped as the sum of
integer 1 to add up, there is only one way to express
,so the last term is 1.
Let us assume
,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.
is the first parcel that will generate its child-parcel(s),
,then
,therefore,
.
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
.
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
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
in
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
directly.
Example: Calculate
and
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
when
,this is a preparing work for the next chapter. The process of analysis is as same as
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
,we have
. (11)
That is the pentagonal number theorem [3] - [8] when
.
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
,when n is an odd number, it equals
.
can be exchanged for because
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
,in fact, in a larger range, when
,after being
“zoomed in” entirely both for
and
,making
,we have
(k = 0 if n is even, k = 1 if n is odd). (14)
Let and let
, when
,after being “zoomed in”
entirely both for
and
,making
,we have
(k = 1 if n is even, k = 0 if n is odd). (15)
Let
and let
,when
,after
being “zoomed in” entirely both for
and
,making
,we have
. (16)
Let
and let
,also when
,after being “zoomed in” entirely both for
and
,making
,we have
(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
should be infinite, where
is a simple equation and
is a function of n. It is because of that the count of the terms that the equation
has can be infinite if n is infinite; in the first step of “zooming in”
,every term of the second half of the equation
can be exchanged for a function
freely.