n12345 6 7 8 910

P(n) 1 2 3 5 7 11 15 22 30 42

Pascal, Blaise 381

For instance, 20 + 15 + 5 and 5 + 20 + 15 are consid-

ered to be two different ordered partitions of the num-

ber 40.

There is just one ordered partition of the number

1, two ordered partitions of 2, four of 3, and eight

ordered partitions of the number 4:

1:1

2:1 + 1 = 2

3:1 + 1 + 1 = 2 + 1 = 1 + 2 = 3

4:1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2

= 2 + 2 = 1 + 3 = 3 + 1 = 4

This pattern persists:

A number nhas 2n–1ordered partitions.

(One can create an ordered partition of a number nby

first writing nas a sum of n1s, and then deleting some,

all, or none of the + signs between the 1s. As there are

n– 1 plus signs to consider, each providing a choice of

whether to leave or to erase, this provides 2n–1possibil-

ities in all.)

If the order of the terms in a partition is not con-

sidered important, then the partition is called

unordered. (For example, 20 + 15 + 5 and 5 + 20 + 15

are now considered the same partition of the number

40.) The symbol P(n) is usually used to denote the

number of unordered partitions a number npossesses.

For instance, P(4) = 5, since there are just five

unordered partitions of the number 4 (namely, 1 + 1 +

1 + 1, 2 + 1 + 1, 2 + 2, 3 + 1 and 4). The following

table shows the first 10 partition function values:

To this day, no one knows an exact formula for this

function, and generally very little is known about its

behavior.

In the mid-1700s L

EONHARD

E

ULER

studied this

function and found one truly remarkable relationship.

Consider those triangular

FIGURATE NUMBERS

that are

divisible by three: 3, 6, 15, 21, 36, 45, … Taking one-

third of those numbers yields the sequence: 1, 2, 5, 7,

12, 15, … Declaring P(0) = 1 and P(n) to be zero if nis

negative, Euler proved that the following formula holds:

P(n) – P(n– 1) – P(n– 2) + P(n– 5) + P(n– 7)

– P(n– 12) – P(n– 15) +…= 0

Here the signs between terms alternate in pairs. Notice

too that although the left side of this equation appears

to be an infinite sum, eventually all the terms in the

sum equal zero. Consequently one is required to add

and subtract only a finite list of numbers.

This formula allows us to compute higher values of

P(n).For instance, to find the value of P(11) use:

P(11) – P(10) – P(9) + P(6) + P(4) – P(–1) – P(–4) +…= 0

That is,

P(11) – 42 – 30 + 11 + 5 – 0 – 0 +…= 0

yielding

P(11) = 56

In the 1930s, mathematicians G

ODFREY

H

AROLD

H

ARDY

and S

RINIVASA

A

IYANGAR

R

AMANUJAN

proved

that if nis large, then the function P(n) is well approxi-

mated by the formula:

Thus, for instance, the value of P(1,000) is approxi-

mately .

Understanding the properties of the unordered par-

tition function is still an active area of research.

Pascal, Blaise (1623–1662) French Probability theory,

Calculus, Geometry, Philosophy Born on June 19,

1623, in Clermont-Ferrand, France, philosopher and

scientist Blaise Pascal is remembered for his work in

GEOMETRY

, hydrostatics, and

PROBABILITY

theory. Al-

though he did not invent the famous arithmetical trian-

gle that bears his name, he did make extensive use of its

properties in his development of probability and the

study of statistical distributions. He also worked on

problems of finding arc lengths and areas of curved fig-

ures. He is noted, in particular, for his work on the