A composition of a positive integer 
is an ordered arrangement of positive integers which sum to
(Skiena 1990, p. 60). It is therefore
a partition in which order is significant. For example,
there are eight compositions of 4,
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
A positive integer 
has 
compositions.
The nesting of two or more functions to form a new function is known as function composition.
The number of compositions of 
into 
parts (where 0 is not allowed as a part) is given by
 |  |  |
(9)
|
 |  |  |
(10)
|
The number 
of compositions of a number 
of length 
(where 0 is allowed) is given by the formula
 |  |  |
(11)
|
 |  |  |
(12)
|
The following table gives counts of compositions where 0 is allowable.
 | OEIS |  ,  , ... |
| 2 | A000027 | 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... |
| 3 | A000217 | 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, ... |
| 4 | A000292 | 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, ... |
| 5 | A000332 | 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, ... |
| 6 | A000389 | 6, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, ... |
| 7 | A000579 | 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, ... |
| 8 | A000580 | 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, ... |
| 9 | A000581 | 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, 43758, ... |
An operation called composition is also defined on binary quadratic forms. For two numbers represented by two forms, the product can then
be represented by the composition. For example, the composition of the forms 
and 
is given by 
, and in this case, the product of 17 and 13 would
be represented as (
). There are several algorithms for computing
binary quadratic form composition, which is the basis for some factoring methods.
