The nesting of two or more functions to form a single new function is known
as composition. The composition of two functions  and  is denoted  , where  is a function whose
domain includes the range of  . The notation
 | (1) |
is sometimes used to explicitly indicate the variable.
Composition is associative, so that
 | (2) |
If the functions  is continuous at  and  is continuous at
 , then  is also
continuous at  .
Faá di Bruno's formula gives an explicit formula for the  th derivative of the composition  .
A combinatorial composition is defined as an ordered arrangement of  nonnegative 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,
 |  |  | (3) |  |  |  | (4) |  |  |  | (5) |  |  |  | (6) |  |  |  | (7) |  |  |  | (8) |  |  |  | (9) |  |  |  | (10) |
A positive integer  has  compositions.
The compositions of  into  parts is given by
Compositions[n, k] in the
Mathematica
add-on package DiscreteMath`Combinatorica` (which can be loaded with the
command <<DiscreteMath`) . This command treats 0 as a significant
addend, so for example  and  are considered
distinct compositions of length 2. The number  of compositions
of a number  of length  is given by the
formula
 | (11) |
which implemented as NumberOfCompositions[n, k]
in the Mathematica
add-on package DiscreteMath`Combinatorica` (which can be loaded with the
command <<DiscreteMath`) . The following table gives
 | Sloane |  ,  , ... | | 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. |
