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.
For integers 
, the number of compositions
of 
into 
positive parts is given by
 |  |  |
(9)
|
 |  |  |
(10)
|
For 
, 
.
A weak composition allows zero as a part. For integers 
and 
, the number 
of weak compositions
of 
of length 
is given by
 |  |  |
(11)
|
 |  |  |
(12)
|
The following table gives counts of weak compositions.
 | 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.
