Composition (number theory)

Composition (number theory)

In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of (strictly) 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 partition of that number. Any integer has finitely many distinct compositions. Negative numbers do not have any compositions, but 0 has one composition, the empty sequence. Any positive integer n has 2n−1 distinct compositions. This is a power of two, because every composition matches a binary number.

Bijection between 3 bit binary numbers and compositions of 4

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 any 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.

Contents

Examples

The 32 compositions of 6

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
...
1 + 5
6
The 11 partitions of 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.

Compare this with the three partitions of 5 into distinct terms:

  • 5
  • 4+1
  • 3+2.

Number of compositions

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


    \big(\,
      \overbrace{1\, \square\, 1\, \square\, \ldots\, \square\, 1\,
      \square\, 1}^n\,
    \big)

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 is given by the binomial coefficient {n-1\choose k-1}. Note that by summing over all possible number of parts we recover 2n−1 as the total number of compositions of n:

 \sum_{k=1}^{n} {n-1 \choose k-1} = 2^{n-1}.

For weak compositions, the number is {n+k-1\choose k-1}, since each k-composition of n + k corresponds to a weak one of n by the rule [a + b + ... + c = n + k] → [(a − 1) + (b − 1) + ... + (c − 1) = n].

References

  • "Combinatorics of Compositions and Words", Silvia Heubach, Toufik Mansour, CRC Press, 2009, ISBN 9781420072679.

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Partition (number theory) — Young diagrams associated to the partitions of the positive integers 1 through 8. They are so arranged that images under the reflection about the main diagonal of the square are conjugate partitions. In number theory and combinatorics, a… …   Wikipedia

  • Composition — may refer to: Composition (logical fallacy), in which one assumes that a whole has a property solely because its various parts have that property Compounding is also known as composition in linguistic literature in computer science Object… …   Wikipedia

  • Theory — The word theory has many distinct meanings in different fields of knowledge, depending on their methodologies and the context of discussion.In science a theory is a testable model of the manner of interaction of a set of natural phenomena,… …   Wikipedia

  • Theory of conjoint measurement — The theory of conjoint measurement (also known as conjoint measurement or additive conjoint measurement) is a general, formal theory of continuous quantity. It was independently discovered by the French economist Gerard Debreu (1960) and by the… …   Wikipedia

  • Theory of computation — In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata… …   Wikipedia

  • Theory of relations — This article is about the theory of relations with regard to its specifically combinatorial aspects. For a general discussion of the basic definitions, see Binary relation and Finitary relation. The theory of relations treats the subject matter… …   Wikipedia

  • Composition series — In abstract algebra, a composition series provides a way to break up an algebraic structure, such as a group or a module, into simple pieces. The need for considering composition series in the context of modules arises from the fact that many… …   Wikipedia

  • Modular representation theory — is a branch of mathematics, and that part of representation theory that studies linear representations of finite group G over a field K of positive characteristic. As well as having applications to group theory, modular representations arise… …   Wikipedia

  • Galois theory — In mathematics, more specifically in abstract algebra, Galois theory, named after Évariste Galois, provides a connection between field theory and group theory. Using Galois theory, certain problems in field theory can be reduced to group theory,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”