TOPICS
Search

Composition


The nesting of two or more functions to form a single new function is known as composition. The composition of two functions f and g is denoted f degreesg, where f is a function whose domain includes the range of g. The notation

 (f degreesg)(x)=f(g(x)),
(1)

is sometimes used to explicitly indicate the variable.

Composition is associative, so that

 f degrees(g degreesh)=(f degreesg) degreesh.
(2)

If the functions g is continuous at x_0 and f is continuous at g(x_0), then f degreesg is also continuous at x_0.

A function h(x)=f(g(x)) which is the composition of two other functions, say f and g, is sometimes said to be a composite function.

Faà di Bruno's formula gives an explicit formula for the nth derivative of the composition f(g(t)).

A combinatorial composition is defined as an ordered arrangement of k nonnegative integers which sum to n (Skiena 1990, p. 60). It is therefore a partition in which order is significant. For example, there are eight compositions of 4,

4=4
(3)
=3+1
(4)
=2+2
(5)
=2+1+1
(6)
=1+3
(7)
=1+2+1
(8)
=1+1+2
(9)
=1+1+1+1.
(10)

A positive integer n has 2^(n-1) compositions.

The number of compositions of n into k parts (where 0 is not allowed as a part) is given by

C_k(n)=(n-1; k-1)
(11)
=((n-1)!)/((k-1)!(n-k)!).
(12)

The number C_k(n) of compositions of a number n of length k (where 0 is allowed) is given by the formula

C_k^'(n)=(n+k-1; k-1)
(13)
=((n+k-1)!)/(n!(k-1)!),
(14)

which is implemented as NumberOfCompositions[n, k] in the Wolfram Language package Combinatorica` . The following table gives counts of compositions where 0 is allowable.

kOEISC_k^'(1), C_k^'(2), ...
2A0000272, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
3A0002173, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, ...
4A0002924, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, ...
5A0003325, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, ...
6A0003896, 21, 56, 126, 252, 462, 792, 1287, 2002, 3003, 4368, ...
7A0005797, 28, 84, 210, 462, 924, 1716, 3003, 5005, 8008, 12376, ...
8A0005808, 36, 120, 330, 792, 1716, 3432, 6435, 11440, 19448, ...
9A0005819, 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 2x^2+15y^2 and 3x^2+10y^2 is given by 6x^2+5y^2, and in this case, the product of 17 and 13 would be represented as (6·36+5·1=221). 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

Composition

Cite this as:

Stover, Christopher and Weisstein, Eric W. "Composition." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Composition.html

Subject classifications