On another page (inverse operators), I discuss the possibility that partitioning is the logical opposite of addition rather than subtraction. G.W. Leibniz asked Bernouilli if he had investigated the number of ways a given number can be separated into two, three or many parts, and remarked that the problem seemed difficult but important. Other mathematicians such as Euler, Legendre, Catalan, De Morgan, Cauchy, Jacobi, Cayley, Sylvester, Ramanujan and many others contributed to the field of partition theory. On this page, I present a few of the things we know about partitions.
Any integer (N) can be "split" or partitioned into from 1 to N parts.
For example, 5 can be split into 7 such partitions:
(1,1,1,1,1), (1,1,1,2), (1,1,3), (1,2,2), (1,4), (2,3), and 5 itself.
I am not totally convinced that the number itself is a valid partition, so
perhaps, for example, 5 really has only 6 partitions rather than 7. However,
the inclusion of the number as a partition is the accepted method, so for
now, I will focus on this.
The symbol p(N) is used to represent the total number of ways that N can be
partitioned. For successive values of N, beginning at 1, we have the
following sequence:
P(N) = 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, ...
There is an amazing recursive formula to provide the nth term of this
sequence:
Let p(0)=1
Stop the following process when the index of a term becomes less than zero.
p(n) = p(n-1) + p(n-2) (m = 1)
-p(n-5) - p(n-7) (m = 2)
+p(n-12) + p(n-15) (m = 3)
- ................
+- p(n-m(3m-1)/2) +- p(n-m(3m+1)/2) (m >= 1)
The last line is the general form for the pairs of terms.
When m is odd, add the two terms, and when m is even, subtract them.
For example: p(12)= p(11) + p(10) - p(7) - p(5) + p(0)
= 56 + 42 - 15 - 7 + 1 = 77
In addition, the Indian mathematician, Ramanujan, proved the following three
amazing rules that reveal patterns of factors in p(n). 5, 7 and 11 are the
only three factors that are known to occur periodically in p(n) as follows:
5 is a factor of p(n) if n==4(mod 5)
7 is a factor of p(n) if n==5(mod 7)
11 is a factor of p(n) if n==6(mod 11)
The symbols (==) above mean congruency.
Why only these three prime factors occur predictably, remains a mystery.
Other mathematicians have shown that powers of 5, 7 and 11 also occur
somewhat predictably.
There are several relations that are known for partitions.
For example, let n and r be any positive integers. The number of partitions
of n in which there are not more than r parts, is equal to the number of
partitions of (n+r) into which there are exactly r parts.
Another known relation is p(n-r,r) = p(n,r) - p(n-1,r-1)
where p(n,r) is the number of partitions of n into r parts.
Many of these relations can be proven using Ferrers diagrams or graphs, after
its inventor N.M. Ferrers. A Ferrers diagram looks as follows:
x x x x x x x This diagram illustrates that the number 21
x x x x x is split into 6 parts equal to
x x x x x (7,5,5,2,1,1) if you read the diagram by rows,
x x and 7 parts equal to (6,4,3,3,3,1,1)
x if you read the diagram by columns.
x These two types are known as conjugate partitions
when the rows and columns are reversed.
If you wish to explore the field of partition theory further, an excellent
book that describes many more of these relationships is called :
"Discrete Mathematics" by Norman L. Biggs, Oxford Science Publications, 1985.
Another classical book (although somewhat outdated now) is L.E. Dickson's
History of the Theory of Numbers (3 volume set), Chelsea Pub.Co., 1966.
Enjoy.