Integer partitions

From Wikiversity
Jump to navigation Jump to search

A partition of a positive integer n is a way of writing n as a sum of positive integers ordered by size.
An integer n has Sloane'sA000041(n) partitions.
Sloane'sA000041(1..10) = (1, 2, 3, 5, 7, 11, 15, 22, 30, 42).

Sloane'sA002865(n) of them don't contain one as an addend.
Sloane'sA002865(1..10) = (0, 1, 1, 2, 2, 4, 4, 7, 8, 12).

The sequence Sloane'sA194602 contains all integer partitions converted to integers.
Each partition can be denoted by its index number in this sequence, which is always shown in violet.
It makes sense to see the positive values as a triangle with row lengths Sloane'sA002865 and row numbers starting with 2. See this illustration of rows 2 to 20.

The values of Sloane'sA194602 are binary numbers with runs of ones separated by single zeros. The smallest runlength is one.
They can be interpreted as integer partitions in two possible ways - one actually used here, and one theoretically possible:

  • Addends one are omitted, and the runlengths represent parts bigger by one.
Sloane'sA194602(5) = 11 = 0b1011 represents the equivalence class of the partitions 3+2 of 5, 3+2+1 of 6, 3+2+1+1 of 7, etc. (compare column 5 in this triangle).
  • The runlengths represent parts of the same size.
Sloane'sA194602(5) = 11 = 0b1011 represents the partition 2+1 of 3.

It should usually be more practical to express the partition 3+2+1 of 6 as the pair (5, 6). However, with the second interpretation it could simply be expressed as 24 (compare this triangle).

An integer partition is essentially the same as a multiset of integers.
Here the positive integers (N) are used, and ones are not ignored - so this is similar to the second of the above interpretations.
For subgroups of nimber addition this is how weight partitions are identified:
Sloane'sA194602(11) = 43 = 0b101011 as a multisubset of N is {1, 1, 2}.
Sloane'sA194602(24) = 183 = 0b10110111 as a multisubset of N is {1, 2, 3}.

The equivalence class of partitions that differ only by addends one can be represented in two ways:
The intuitive way to do this is just not to show the ones or to imply an indefinite number (like in the horizontal axis of this triangle).
A more elegant but potentially confusing way is to reduce all parts by one.
Such a partition, representing an equivalence class of partitions with addends greater by one, shall be called a thin partition.


Partitions of 10[edit]

There are Sloane'sA000041(10) = 42 partitions of 10, and Sloane'sA002865(10) = 12 of them don't have the addend one.
The last among them - the partition that has only the addend 10 - corresponds to a binary number with 9 ones, i.e. Sloane'sA194602(41) = 511.


Triangles[edit]

Parts ≥ k[edit]

Sloane'sA026807(n,k) = number of partitions of n in which every part is ≥ k. (more values)

   k    1  2  3  4  5  6  7  8  9 10
 n
 1      1
 2      2  1
 3      3  1  1
 4      5  2  1  1
 5      7  2  1  1  1
 6     11  4  2  1  1  1
 7     15  4  2  1  1  1  1
 8     22  7  3  2  1  1  1  1
 9     30  8  4  2  1  1  1  1  1
10     42 12  5  3  2  1  1  1  1  1

The first four columns are Sloane'sA000041, Sloane'sA002865, Sloane'sA008483 and Sloane'sA008484.

Smallest part k[edit]

Sloane'sA026794(n,k) = number of partitions of n in which the smallest part is k. (more values)

   k    1  2  3  4  5  6  7  8  9 10
 n
 1      1
 2      1  1
 3      2  0  1
 4      3  1  0  1
 5      5  1  0  0  1
 6      7  2  1  0  0  1
 7     11  2  1  0  0  0  1
 8     15  4  1  1  0  0  0  1
 9     22  4  2  1  0  0  0  0  1
10     30  7  2  1  1  0  0  0  0  1


Palindromes[edit]

    1        11          111
  101     11011      1110111
10101  11011011  11101110111 

Sloane'sA194602 contains all numbers whose binary expression has m runs of n ones.
The index numbers and values (Sloane'sA249543: Sloane'sA249544) can be seen in the following table.
Its top row is Sloane'sA000041(N)−1: Sloane'sA000225(N-1) and its left column is Sloane'sA000041(2N-1): Sloane'sA002450(N).

1 2 3 4 5
1 1: 1 2: 3 4: 7 6: 15 10: 31
2 3: 5 9: 27 20: 119 40: 495 75: 2015
3 7: 21 26: 219 72: 1911 171: 15855 379: 128991
4 15: 85 68: 1755 220: 30583 614: 507375 1559: 8255455
5 30: 341 159: 14043 603: 489335 1928: 16236015 5564: 528349151