Composition (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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 
.
A function 
which is the composition of two other functions, say 
and 
, is sometimes said to be a composite function.
Faà di Bruno's formula gives an explicit formula for the 
thderivative 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,
A positive integer 
has 
compositions.
The number of compositions of 
into 
parts (where 0 is not allowed as a part) is given by
The number 
of compositions of a number 
of length 
(where 0 is allowed) is given by the formula
which is implemented as NumberOfCompositions[n, _k_] in the Wolfram Language package Combinatorica` . 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.
See also
Adem Relations, Bhargava's Theorem, Binary Operator, Binary Quadratic Form, Decomposition, Faà di Bruno's Formula, Nested Function, Permutation,Random Composition
Portions of this entry contributed by Christopher Stover
Explore with Wolfram|Alpha
References
Apostol, T. M. "Composite Functions and Continuity." §3.7 in Calculus, 2nd ed., Vol. 1: One-Variable Calculus, with an Introduction to Linear Algebra. Waltham, MA: Blaisdell, pp. 140-141, 1967.Klingsberg, P. "A Gray Code for Compositions." J. Algorithms 3, 41-44, 1982.Richmond, B. and Knopfmacher, A. "Compositions with Distinct Parts." Aeq. Math. 49, 86-97, 1995.Skiena, S. "Compositions." §2.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 60-62, 1990.
Referenced on Wolfram|Alpha
Cite this as:
Stover, Christopher and Weisstein, Eric W. "Composition." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Composition.html