This site is supported by donations to The OEIS Foundation.

Partitions

From OeisWiki
There are no approved revisions of this page, so it may not have been reviewed.
Jump to navigationJump to search


This article needs more work.

Please help by expanding it!


A partition of an integer

n

is a multiset (or bag) of positive integers whose elements sum to

n

. This is an additive representation of

n

. A part in a partition is sometimes also called a summand. The set of partitions of

n

is denoted by

P (n)

. The partition function

p (n)

gives the number of partitions of

n

, that is

p (n)

is the cardinality of

P (n)

.

The set of partitions of 0 is a set containing the empty bag (its sum being the empty sum 0)

P (0) = {∅} = {​{ }​}, p (0) = 1.

The set of partitions of a negative integer is the empty set, since negative integers are not the sum of positive integers

P (n) = ∅ = { }, p (n) = 0, n < 0,

where the partition function of negative integers is useful in some recursive formulae for the partition function (e.g. the intermediate partition function formula).

Definition

[edit]

An ordinary partition (or line partition) of

n

is a one-dimensional arrangement of positive integers

n0,  n1,  n2,  n3,  ⋯

which are nonincreasing (weakly decreasing)

ni +1 ≤  ni ,

and which sum to

n
n  = 
 
i
∑
 
i
  
  ni .

A related concept is a composition (sometimes also called integer composition, ordered partition or ordered integer partition) of

n

.

Partition function

[edit]

The partition function

p (n)

gives the number of partitions of

n

.

Graphical representations of integer partitions

[edit]

Ferrers graphs and conjugate partitions

[edit]

Ferrers graphs (and Ferrers boards) are graphical representations of integer partitions where the parts of the partition are rows of dots (or squares in the case of Ferrers boards). By exchanging rows and columns of the Ferrers graph of a partition, we obtain its conjugate partition. This is equivalent to the transpose of a matrix of dots representing the Ferrers graph. For example, the conjugate partition of {4, 4, 2, 1, 1} is {5, 3, 2, 2}.

Ferrers graph
of
{4, 4, 2, 1, 1}
       
● ● ● ●
● ● ● ●
● ●
●
●
Ferrers graph
of
{5, 3, 2, 2}
       
● ● ● ● ●
● ● ●
● ●
● ●

Partition tree

[edit]

Integer partitions can be generated in a natural way as a binary tree.[1] [2]

Orderings of partitions

[edit]
Main article page: Orderings of partitions

Table of partitions in graded reverse lexicographic order

[edit]

The table adheres to the graded reverse lexicographic ordering of the partitions, also referred to as the “canonical” ordering of the partitions. Partitions of

n

derived from partitions of

n  −  1

by adding a single 1 part are in grey font (instead of black font).

“Canonical” ordering [graded reverse lexicographic ordering] of partitions
Partition Positive integer
representation
( 
∏

pi
 , where
part size
i
 ⇔
i
  thprime)
A129129 		Sum
of parts
n
 		Sum
of parts^2 		Number
of parts 		Largest
part 		Smallest
part
{ } (empty product) 1 0 0 0    
{1} 2 1 1 1 1 1
{2} 3 2 4 1 2 2
{1,1} 4 2 2 2 1 1
{3} 5 3 9 1 3 3
{2,1} 6 3 5 2 2 1
{1,1,1} 8 3 3 3 1 1
{4} 7 4 16 1 4 4
{3,1} 10 4 10 2 3 1
{2,2} 9 4 8 2 2 2
{2,1,1} 12 4 6 3 2 1
{1,1,1,1} 16 4 4 4 1 1
{5} 11 5 25 1 5 5
{4,1} 14 5 17 2 4 1
{3,2} 15 5 13 2 3 2
{3,1,1} 20 5 11 3 3 1
{2,2,1} 18 5 9 3 2 1
{2,1,1,1} 24 5 7 4 2 1
{1,1,1,1,1} 32 5 5 5 1 1
{6} 13 6 36 1 6 6
{5,1} 22 6 26 2 5 1
{4,2} 21 6 20 2 4 2
{4,1,1} 28 6 18 3 4 1
{3,3} 25 6 18 2 3 3
{3,2,1} 30 6 14 3 3 1
{3,1,1,1} 40 6 12 4 3 1
{2,2,2} 27 6 12 3 2 2
{2,2,1,1} 36 6 10 4 2 1
{2,1,1,1,1} 48 6 8 5 2 1
{1,1,1,1,1,1} 64 6 6 6 1 1
{7} 17 7 49 1 7 7
{6,1} 26 7 37 2 6 1
{5,2} 33 7 29 2 5 2
{5,1,1} 44 7 27 3 5 1
{4,3} 35 7 25 2 4 3
{4,2,1} 42 7 21 3 4 1
{4,1,1,1} 56 7 19 4 4 1
{3,3,1} 50 7 19 3 3 1
{3,2,2} 45 7 17 3 3 2
{3,2,1,1} 60 7 15 4 3 1
{3,1,1,1,1} 80 7 13 5 3 1
{2,2,2,1} 54 7 13 4 2 1
{2,2,1,1,1} 72 7 11 5 2 1
{2,1,1,1,1,1} 96 7 9 6 2 1
{1,1,1,1,1,1,1} 128 7 7 7 1 1
{8} 19 8 64 1 8 8
{7,1} 34 8 50 2 7 1
{6,2} 39 8 40 2 6 2
{6,1,1} 52 8 38 3 6 1
{5,3} 55 8 34 2 5 3
{5,2,1} 66 8 30 3 5 1
{5,1,1,1} 88 8 28 4 5 1
{4,4} 49 8 32 2 4 4
{4,3,1} 70 8 26 3 4 1
{4,2,2} 63 8 24 3 4 2
{4,2,1,1} 84 8 22 4 4 1
{4,1,1,1,1} 112 8 20 5 4 1
{3,3,2} 75 8 22 3 3 2
{3,3,1,1} 100 8 20 4 3 1
{3,2,2,1} 90 8 18 4 3 1
{3,2,1,1,1} 120 8 16 5 3 1
{3,1,1,1,1,1} 160 8 14 6 3 1
{2,2,2,2} 81 8 16 4 2 2
{2,2,2,1,1} 108 8 14 5 2 1
{2,2,1,1,1,1} 144 8 12 6 2 1
{2,1,1,1,1,1,1} 192 8 10 7 2 1
{1,1,1,1,1,1,1,1} 256 8 8 8 1 1

Positive integer representation of partitions

[edit]
“Canonical” ordering [graded reverse lexicographic ordering] of partitions
Positive integer representation ( 
∏

pi
 , where part size
i
 ⇔
i
  thprime)
n
 		Partitions of
n
 (positive integer representation)*
Partitions of
n
 with an even integer representation are italicized.**
A129129 (concatenated rows) 		Partitions of
n

with odd representation
p (n)

A000041
0 1 1 1
1 2   1
2 3, 4 3 2
3 5, 6, 8 5 3
4 7, 10, 9, 12, 16 7, 9 5
5 11, 14, 15, 20, 18, 24, 32 11, 15 7
6 13, 22, 21, 28, 25, 30, 40, 27, 36, 48, 64 13, 21, 25, 27 11
7 17, 26, 33, 44, 35, 42, 56, 50, 45, 60, 80, 54, 72, 96, 128 17, 33, 35, 45 15
8 19, 34, 39, 52, 55, 66, 88, 49, 70, 63, 84, 112, 75, 100, 90, 120, 160, 81, 108, 144, 192, 256 19, 39, 55, 49, 63, 75, 81 22

_______________

* Row

n

: first term is

n

th noncomposite (A008578), last term is

2 n

(A000079).
** All the partitions of

n

with an even integer representation are obtained by doubling all the integer representations of the partitions of

n  −  1

(which corresponds to adding a part of size 1 to each of the partitions of

n  −  1

, since

p1 = 2

). All the partitions of

n

with an odd integer representation are not obtained by adding any nonzero number of parts of size 1 to any of the partitions of

k < n

.

Restricted partitions

[edit]

See restricted partitions.

Sequences

[edit]

A000041 The number of partitions

p (n)

of

n, n   ≥   0

.

{1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, ...}

A002865 The number of partitions

p (2, n)

of

n, n   ≥   0

, that do not contain 1 as a part (and corresponds to

p (n)  −  p (n  −  1), n   ≥   0

).

{1, 0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 41, 55, 66, 88, 105, 137, 165, 210, 253, 320, 383, 478, 574, 708, 847, 1039, 1238, 1507, 1794, 2167, 2573, 3094, 3660, 4378, 5170, 6153, 7245, 8591, ...}

A000070 The summatory function of the partition function:

∑
n

k  = 0
  p (k)

, where

p (k) =

number of partitions of

k

(A000041).

{1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, ...}

A080577 Triangle read by rows in which row

n

lists all the parts of all the partitions of

n

, in “canonical” ordering [i.e. graded reverse lexicographic ordering].

{1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 4, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 1, 3, 3, 3, 2, 1, 3, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 6, 1, 5, 2, 5, 1, 1, 4, 3, 4, 2, 1, 4, 1, 1, 1, 3, 3, 1, 3, 2, ...}

A129129 An irregular triangular array of natural numbers read by rows, with shape sequence A000041

 (n)

related to sequence A060850. (“Canonical” ordering [graded reverse lexicographic ordering] of partitions mapped one-to-one to positive integers.)

{1, 2, 3, 4, 5, 6, 8, 7, 10, 9, 12, 16, 11, 14, 15, 20, 18, 24, 32, 13, 22, 21, 28, 25, 30, 40, 27, 36, 48, 64, 17, 26, 33, 44, 35, 42, 56, 50, 45, 60, 80, 54, 72, 96, 128, 19, 34, 39, 52, 55, 66, 88, 49, 70, 63, 84, 112, 75, 100, 90, 120, 160, 81, 108, 144, 192, 256, ...}

A063008 The canonical partition sequence (see A080577) encoded by prime factorization. (The partition

[P1 + P2 + P3 + ⋯]

with

P1   ≥   P2   ≥   P3   ≥   ⋯

is encoded as

2 P1 ⋅  3 P2 ⋅  5 P3 ⋅  ⋯

)

{1, 2, 4, 6, 8, 12, 30, 16, 24, 36, 60, 210, 32, 48, 72, 120, 180, 420, 2310, 64, 96, 144, 240, 216, 360, 840, 900, 1260, 4620, 30030, 128, 192, 288, 480, 432, 720, 1680, 1080, 1800, 2520, 9240, 6300, ...}

A036036 Triangle read by rows in which row

n

lists all the parts of all the partitions of

n

, in Abramowitz-Stegun order [i.e. graded reflected colexicographic ordering].

{1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 4, 1, 3, 2, 2, 1, 1, 2, 1, 1, 1, 1, 5, 1, 4, 2, 3, 1, 1, 3, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 6, 1, 5, 2, 4, 3, 3, 1, 1, 4, 1, 2, 3, 2, 2, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 7, 1, 6, 2, 5, 3, 4, 1, 1, 5, 1, 2, 4, 1, 3, 3, 2, 2, 3, 1, 1, 1, ...}

A185974 Partitions in Abramowitz-Stegun order [i.e. graded reflected colexicographic ordering] A036036 mapped one-to-one to positive integers.

{1, 2, 3, 4, 5, 6, 8, 7, 10, 9, 12, 16, 11, 14, 15, 20, 18, 24, 32, 13, 22, 21, 25, 28, 30, 27, 40, 36, 48, 64, 17, 26, 33, 35, 44, 42, 50, 45, 56, 60, 54, 80, 72, 96, 128, 19, 34, 39, 55, 49, 52, 66, 70, 63, 75, 88, 84, 100, 90, 81, 112, 120, 108, 160, 144, 192, 256, 23, 38, 51, 65, 77, 68, 78, ...}

A185975 Prime number factorization of

n, n   ≥   2,

mapped to

a (n)

-th partition in Abramowitz-Stegun order [i.e. graded reflected colexicographic ordering].

{1, 2, 3, 4, 5, 7, 6, 9, 8, 12, 10, 19, 13, 14, 11, 30, 16, 45, 15, 21, 20, 67, 17, 22, 31, 25, 23, 97, 24, 139, 18, 32, 46, 33, 27, 195, 68, 47, 26, 272, 35, 373, 34, 37, 98, 508, 28, 49, 36, 69, 50, 684, 40, 48, 38, 99, 140, 915, 39, 1212, 196, 53, 29, 70, 51, 1597, 72, 141, 52, 2087, 42, ...}

A116084 Number of partitions of 1 into distinct fractions

i
 j 

with

1   ≤   i < j   ≤   n

,

i

and

j

coprime, for

n   ≥   1

.

{0, 0, 1, 2, 4, 6, 10, 15, 23, 36, 47, 70, 87, 132, 283, 434, 471, 772, 825, 1834, 4368, 5545, 5648, 9923, 16464, 19943, 32323, 75912, 76167, 140801, 141140, 238513, 537696, 598295, 2556064, 4674084, ...}

See also

[edit]




Notes

[edit]
  1. ↑ Partition-tree of 6, Partition-tree of 7, Partition-tree of 8, Partition-tree of 9, where the seemingly unary branches of the binary tree are actually either a left or right branch with the other branch being an empty branch. (from Peter Luschny, Counting with Partitions, 2009-02-20.)
  2. ↑ See also User:Peter Luschny/IntegerPartitionTrees.
[edit]
Retrieved from "https://oeis.org/wiki/Partitions"