Community hub
0 subscribers8 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Composition (combinatorics).
Nothing was collected or created yet.
Composition (combinatorics)
View on Wikipediafrom Wikipedia
In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of positive integers. Two sequences that differ in the order of their terms define different compositions of their sum, while they are considered to define the same integer partition of that number. Every integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Each positive integer n has 2n−1 distinct compositions.
A weak composition of an integer n is similar to a composition of n, but allowing terms of the sequence to be zero: it is a way of writing n as the sum of a sequence of non-negative integers. As a consequence every positive integer admits infinitely many weak compositions (if their length is not bounded). Adding a number of terms 0 to the end of a weak composition is usually not considered to define a different weak composition; in other words, weak compositions are assumed to be implicitly extended indefinitely by terms 0.
To further generalize, an A-restricted composition of an integer n, for a subset A of the (nonnegative or positive) integers, is an ordered collection of one or more elements in A whose sum is n.[1]
Examples
[edit]
1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
. . .
1 + 5
6
1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
. . .
3 + 3
6
The sixteen compositions of 5 are:
- 5
- 4 + 1
- 3 + 2
- 3 + 1 + 1
- 2 + 3
- 2 + 2 + 1
- 2 + 1 + 2
- 2 + 1 + 1 + 1
- 1 + 4
- 1 + 3 + 1
- 1 + 2 + 2
- 1 + 2 + 1 + 1
- 1 + 1 + 3
- 1 + 1 + 2 + 1
- 1 + 1 + 1 + 2
- 1 + 1 + 1 + 1 + 1.
Compare this with the seven partitions of 5:
- 5
- 4 + 1
- 3 + 2
- 3 + 1 + 1
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1.
It is possible to put constraints on the parts of the compositions. For example the five compositions of 5 into distinct terms are:
- 5
- 4 + 1
- 3 + 2
- 2 + 3
- 1 + 4.
Number of compositions
[edit]
Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2n−1 compositions of n ≥ 1; here is a proof:
Placing either a plus sign or a comma in each of the n − 1 boxes of the array
produces a unique composition of n. Conversely, every composition of n determines an assignment of pluses and commas. Since there are n − 1 binary choices, the result follows. The same argument shows that the number of compositions of n into exactly k parts (a k-composition) is given by the binomial coefficient . Note that by summing over all possible numbers of parts we recover 2n−1 as the total number of compositions of n:
For weak compositions, the number is , since each k-composition of n + k corresponds to a weak one of n by the rule
It follows from this formula that the number of weak compositions of n into exactly k parts equals the number of weak compositions of k − 1 into exactly n + 1 parts.
For A-restricted compositions, the number of compositions of n into exactly k parts is given by the extended binomial (or polynomial) coefficient , where the square brackets indicate the extraction of the coefficient of in the polynomial that follows it.[2]
![{\displaystyle {\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7738915aaa1ad7fefe7ed8d9c49aa675c15c48df)
Homogeneous polynomials
[edit]The dimension of the vector space of homogeneous polynomial of degree d in n variables over the field K is the number of weak compositions of d into n parts. In fact, a basis for the space is given by the set of monomials such that . Since the exponents are allowed to be zero, then the number of such monomials is exactly the number of weak compositions of d.
![{\displaystyle K[x_{1},\ldots ,x_{n}]_{d}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6929b765b118e9d173c9187a4d35fee3d1893550)
See also
[edit]References
[edit]- ^ Heubach, Silvia; Mansour, Toufik (2004). "Compositions of n with parts in a set". Congressus Numerantium. 168: 33–51. CiteSeerX 10.1.1.484.5148.
- ^ Eger, Steffen (2013). "Restricted weighted integer compositions and extended binomial coefficients" (PDF). Journal of Integer Sequences. 16.
- Heubach, Silvia; Mansour, Toufik (2009). Combinatorics of Compositions and Words. Discrete Mathematics and its Applications. Boca Raton, Florida: CRC Press. ISBN 978-1-4200-7267-9. Zbl 1184.68373.
External links
[edit]Composition (combinatorics)
View on Grokipediafrom Grokipedia
Definition and Basics
Formal Definition
A composition of a positive integer is an ordered tuple of positive integers that sum to , where the order matters, so that distinct permutations of the summands are regarded as different compositions. For instance, both and are compositions of 3, but they are distinct.[6][7] Such a composition is typically denoted by the equation , where each is a positive integer () and is the number of parts (or length) of the composition.[6][1] The standard definition restricts parts to positive integers; an extension permitting non-negative integers (including zeros) is termed a weak composition.[4][8]Distinction from Partitions
In combinatorics, the primary distinction between compositions and partitions of a positive integer lies in the treatment of order among the summands. A composition of is an ordered tuple of positive integers that sum to , meaning that different permutations of the same parts are considered distinct. In contrast, a partition of is an unordered multiset of positive integers summing to , where the order of parts does not matter, and parts are typically listed in non-increasing order for uniqueness. For instance, the sequences 1+2 and 2+1 both represent compositions of 3 but correspond to the same partition {2,1}.[9][10] This ordered structure in compositions lends itself to a natural bijection with placements of separators among units, often illustrated via a variant of the stars and bars theorem. Specifically, each composition of can be visualized by lining up stars (representing the units) and placing bars in the gaps between them to separate the parts; the positions of the bars determine the lengths of the ordered summands. For example, for , the stars are *** , and possible bar placements yield: *** (no bars, composition 3), |* (one bar after first star, 1+2), *| (1+2 wait, | is 2+1), and || (two bars, 1+1+1). This combinatorial representation underscores how compositions inherently encode sequential divisions, differing from partitions which abstract away such ordering.[4] The implications of this distinction are significant: compositions enumerate more structures than partitions for , as multiple ordered arrangements map to each unordered one. For , there are four compositions (3, 2+1, 1+2, 1+1+1) but only three partitions (3, 2+1, 1+1+1). This multiplicity arises directly from permutations of parts, leading to compositions being studied separately when order conveys meaningful structure, such as in modeling sequences of events or divisions.[9][4] Compositions are thus motivated for applications where sequential order is essential, such as representing run lengths in binary strings, decompositions of words in combinatorics on words, or step sizes in lattice paths, whereas partitions suit scenarios involving unordered collections like frequency distributions or multiset sums. This separation allows for tailored analytic tools and identities unique to each, reflecting their distinct roles in enumerative problems.[1]Examples and Illustrations
Integer Examples
A composition of a positive integer is an ordered tuple of positive integers that sum to . For , there is only one such composition: .[2] For , the compositions are and .[2] For , the compositions are , , , and ; representations involving zero, such as , are invalid since all parts must be positive integers.[2] For , the compositions are , , , , , , , and .[1] These cases show the number of compositions growing from 1 for to 8 for , exhibiting a doubling trend that reflects the combinatorial choices in ordering the parts.[6] Unlike integer partitions, where order is irrelevant and has only three partitions (, , ), compositions count permutations as distinct.[6]Visual and Sequential Representations
One common visual representation of integer compositions employs the stars and bars method, where the integer to be composed is depicted as stars (or dots) in a horizontal row, and the parts of the composition are formed by inserting bars into the gaps between these stars to separate them into groups.[11] For example, the composition of is visualized as **|, where the two stars before the bar represent the part 2, and the single star after represents the part 1; similarly, appears as | , and as *** with no bars. This approach intuitively illustrates the ordered nature of compositions by showing how the placement of bars divides the fixed sequence of stars into contiguous segments of positive length.[4] A linear sequence view further emphasizes this by interpreting compositions as divisions of a row of indistinguishable beads into ordered runs, where each run corresponds to a part whose length is the number of beads in that group. For , the four compositions—, , , and —can be seen as: three single beads separated by dividers (• | • | •), a single followed by two together (• | ••), two followed by one (•• | •), or all three undivided (•••). This bead-run analogy highlights the sequential ordering and the requirement that each part is at least one bead, providing an accessible way to enumerate and distinguish compositions without relying on numerical listing alone.[11] Block diagrams offer another graphical method, portraying each part of a composition as a horizontal block (or rectangle) whose width equals the part's value, arranged side by side to sum visually to . For the composition of , this appears as a single-unit block adjacent to a two-unit block: [■] [■■]. Extending to , the composition is rendered as [■■] [■] [■], while is a single [■■■■] block; such diagrams make the additive structure immediate and allow easy comparison of different orderings, like versus . These representations aid in building intuition for how permutations of parts yield distinct compositions.[11] Compositions can also be conceptualized as "words" formed over the infinite alphabet of positive integers, where the letters are the parts and their "length" (numerical value) contributes to the total sum . In this linguistic analogy, the composition of is akin to the word "211" in this alphabet, distinct from "121" or "112", underscoring the ordered sequence aspect; for , the words are "111", "12", "21", and "3". This perspective connects compositions to broader combinatorial structures like sequences and strings, facilitating analysis in contexts such as random generation or pattern avoidance.[12]Enumeration of Compositions
Unrestricted Compositions
A fundamental result in the enumeration of compositions states that the number of unrestricted compositions of a positive integer is .[13] This count can be understood through a natural bijection with the power set of , which has cardinality . Imagine indistinguishable units (or "stars") aligned in a row, creating possible gaps between them. Each subset of these gaps indicates where to insert a "break" (or "bar"), dividing the row into consecutive groups whose sizes form the parts of the composition; the empty subset yields the single-part composition .[14] To verify, consider small values of . For , the sole composition is , matching . For , the compositions are and , totaling 2, as . For , they are , , , and , totaling 4, as . These examples illustrate the exponential growth: unlike the number of partitions , which asymptotically behaves as and grows much more slowly, the compositions double approximately with each increment in .[15]Recursive and Closed-Form Formulas
Let denote the number of compositions of the positive integer . This function satisfies the recurrence relation where the initial condition corresponds to the empty composition of 0.[16] The relation follows from classifying compositions of by the size of their last part, with the preceding parts then forming a composition of .[16] An equivalent and simpler recurrence is To see this, note that every composition of can be obtained from a composition of in exactly two ways: either by inserting a new part 1 at the beginning, or by adding 1 to the first part of the original composition. These operations are reversible and cover all cases without overlap.[17] Iterating the second recurrence immediately suggests the closed-form expression A formal proof proceeds by induction on . For the base case , there is one composition (1), and . Assume the formula holds for ; then completing the induction.[17] An alternative combinatorial argument establishes the closed form via a bijection between the compositions of and the binary strings of length . Represent as a row of stars: . There are gaps between these stars. Placing a bar (separator) in a gap corresponds to a 1 in the binary string at that position, while no bar corresponds to a 0; each such choice divides the stars into ordered groups whose sizes form a composition of . For example, for , the binary strings 00, 01, 10, and 11 yield the compositions (3), (2+1), (1+2), and (1+1+1), respectively. Since there are exactly binary strings of length , the bijection confirms .[14]Analytic Tools
Generating Functions
The ordinary generating function for the number of unrestricted compositions of the positive integer , denoted , is the power series . This series equals for , where the radius of convergence is determined by the nearest singularity at .[1] To derive this generating function combinatorially, note that each part in a composition is a positive integer at least 1, so the generating function for a single part is . A composition consists of one or more such parts in sequence, yielding the geometric series .[1] The series expansion confirms the coefficients: , matching . This basic form facilitates further analytic study of compositions, such as extracting coefficients or deriving asymptotic behavior.[1] For weak compositions allowing non-negative integer parts (including zeros), the generating function for a single part is ; however, with an unrestricted number of parts, the total count for each becomes infinite due to arbitrary insertions of zeros, so such cases typically fix the number of parts , yielding . The focus here remains on positive-part compositions.Combinatorial Identities
Combinatorial identities for integer compositions often arise from bijections, recursive relations, or generating function manipulations, providing elegant connections to binomial coefficients and other sequences. One fundamental identity counts the compositions by the number of parts. The number of compositions of a positive integer into exactly parts, where , is given by the binomial coefficient .[18] This follows from viewing a composition as aligned units (stars) with bars separating the parts; there are gaps between the units, and choosing of these gaps to place bars yields the count.[18] Summing over all possible numbers of parts recovers the total number of unrestricted compositions of . Specifically, , which equals the total number of compositions of .[19] This identity can be verified directly via the binomial theorem, as the sum is the expansion of .[19] The result also admits a direct bijective proof: each composition corresponds to a subset of the internal positions in a line of units where separators are placed.[19] Restricted compositions yield further identities linking to well-known sequences. For compositions of using only parts of 1 or 2, the number is the -th Fibonacci number , where the Fibonacci sequence is defined by , , and for .[20] This holds because such compositions satisfy the same recurrence: the count for , denoted , splits into those ending in 1 (preceded by a composition of ) or 2 (preceded by a composition of ), yielding with initial conditions and , matching the shifted Fibonacci sequence.[20] Generating functions provide a tool for deriving additional identities, such as those for compositions with parts restricted to even or odd sizes. For example, the ordinary generating function for unrestricted compositions is ; modifying the part generating function to for even parts (at least 2) leads to the composition generating function , whose coefficients count even-part compositions and satisfy a related recurrence.[19] Similar manipulations apply for odd parts, yielding , whose coefficients are the nth Fibonacci numbers and connect to Fibonacci-like sequences.[19]Restricted and Generalized Compositions
Compositions with Part Constraints
In combinatorics, compositions with part constraints impose restrictions on the sizes of the summands in an ordered partition of a positive integer , such as requiring each part to be at most a fixed integer . These constraints lead to modified enumeration techniques, often involving generating functions or recurrences tailored to the bounds. Such restricted compositions arise in applications like tiling problems or modeling sequences with limited step sizes.[21] The ordinary generating function for the number of compositions of with each part at most is given by where accounts for the empty composition, and for counts the non-empty ones; equivalently, the generating function for non-empty compositions is .[22] The coefficients satisfy the linear recurrence for , with initial conditions and for . This recurrence arises from considering the possible sizes of the last part in a composition of .[21] For the specific case where parts are at most 1 (i.e., ), there is exactly one composition of : ones, so for all . When parts are at most 2 (i.e., ), only 1s and 2s are allowed, and the number of such compositions of is the -th Fibonacci number , where the Fibonacci sequence is defined by , , and for . This follows from the generating function , whose coefficients are the Fibonacci numbers shifted by one index, and the recurrence for , with and .[23] For general , the enumeration parallels the bounded case, with satisfying the higher-order recurrence and initial conditions determined by smaller values of .[21] To illustrate, consider compositions of with parts at most 2. There are such compositions:Compositions with Fixed Number of Parts
A composition of a positive integer into exactly parts is an ordered tuple of positive integers that sum to . The number of such compositions, denoted , is given by the binomial coefficient .[6] This formula arises from a bijection between the set of compositions of with parts and the ways to choose positions out of possible gaps between indistinguishable units (stars) to place dividers (bars), ensuring each part is at least 1. Specifically, represent as a line of stars, with gaps between them; selecting of these gaps for bars divides the stars into nonempty groups, each corresponding to a part. This stars-and-bars construction guarantees the parts are positive integers summing to , establishing the count .[6] For example, the compositions of into exactly parts are , , and , totaling .[6] The ordinary generating function for the number of compositions of with exactly parts is the coefficient of in , which expands to . This follows from the fact that each of the parts has generating function (for positive integers), and the product yields the joint count.[24] Summing over all possible from 1 to , the total number of unrestricted compositions of is , recovered via the binomial theorem applied to .[6]Applications and Connections
Relation to Homogeneous Polynomials
The multinomial theorem provides a direct algebraic connection between integer compositions and the expansion of homogeneous polynomials. It states that for indeterminates and nonnegative integer , where the sum runs over all weak compositions of into exactly parts (allowing zeros), and the multinomial coefficient is .[25] Each monomial in this expansion corresponds uniquely to such a weak composition, with the coefficient counting the number of ways to distribute indistinct units into distinct bins of sizes given by the parts .[25] This correspondence arises because the theorem enumerates the terms of the homogeneous polynomial of degree in variables, where the exponents form an ordered tuple summing to . In the commutative ring of polynomials, like terms with permuted exponents combine, so the coefficient incorporates the symmetry; for instance, if all are distinct and positive, it equals the number of distinct permutations of that composition. More generally, for restricted compositions where parts lie in a set , the generating function has coefficients that sum over compositions into parts, generalizing the binomial case for unrestricted positive parts.[26] The dimension of the vector space of homogeneous polynomials of degree in variables over a field (such as or ) equals the number of monomials of total degree , which is the number of weak compositions of into parts: .[27] A standard monomial basis consists precisely of these . For illustration, expand . The quadratic term arises from the weak composition with coefficient , while corresponds to (and permutations), where the coefficient accounts for the two ways to order the parts 1 and 1 across the distinct variables and .[25] This structure highlights how compositions encode the combinatorial structure underlying polynomial expansions.Links to Binary Sequences and Other Structures
A fundamental bijection exists between the set of all compositions of the positive integer and the set of binary strings of length . This correspondence arises from the stars-and-bars representation: align indistinguishable stars (units) in a row, creating gaps between them. Each gap is either empty (denoted 0, indicating continuation of the current part) or contains a bar (denoted 1, indicating a break to start a new part). The resulting part sizes are the numbers of consecutive stars between bars (or ends). For , the mappings are:- : *** →
- : *| →
- : |* →
- : || →