edit this page

# 1. Definition

An integer composition $\alpha$ of $n \in \mathbf{N}$ is a sequence $\alpha_1,\ldots,\alpha_m$ such that $\alpha_m > 0$ and $\sum_{1 \leq k \leq m} \alpha_k = n$.

# 2. Notation

By $\mathbf{C}_n$, we denote the collection of all integer compositions of $n$. We usually write $\alpha \in \mathbf{C}_n$ as $\alpha = (\alpha_1,\alpha_2, \ldots)$. Integer compositions of $n$ are in bijection with the subsets of $\{1,2,\ldots, n-1\}$. The set corresponding to the composition $\alpha$ will be denoted $D(\alpha)$ and is equal to the set $\{ \alpha_1, \alpha_1 +\alpha_2, \ldots, \alpha_1+\alpha_2+ \cdots + \alpha_{m-1} \}$. The composition corresponding to a set $D = \{ d_1, d_2, \ldots, d_{m-1} \}$ will be denoted $\alpha(D)$ and is equal to the composition $(d_1, d_2-d_1, d_3-d_2,\ldots, d_{m-1} - d_{m-2}, n-d_{m-1})$.

There are three obvious involutions on compositions corresponding to the reverse of the list, complementation of the set, and the composition of these two operations. They will be denoted as $\alpha^r$, $\alpha^c$ and $\alpha'$ where they are defined as $$\alpha^r = (\alpha_m, \alpha_{m-1}, \ldots, \alpha_1) = \alpha(\{ n-i : i \in D(\alpha) \})$$ $$\alpha^c = \alpha(\{1,2,\ldots, n-1\} - D(\alpha)),$$ $$\hbox{ and }\alpha' = (\alpha^r)^c = (\alpha^c)^r.$$

There are several ways of representing a composition with a picture. Sometimes they are thought of as a skew partition $\lambda/{\overline \lambda}$ where $$\lambda = (\alpha_1+\alpha_2+\cdots+\alpha_{m}-m+1, \alpha_1+\alpha_2+\cdots+\alpha_{m-1}-m+2, \ldots, \alpha_1+\alpha_2-1, \alpha_1)\hbox{ and }{\overline \lambda} = (\lambda_2-1,\lambda_3-1,\ldots,\lambda_m-1).$$ Also present example of **bar graph** and/or **skyline diagram**

# 3. Examples

$\mathbf{C}_1 = \{ [1]\}$

$\mathbf{C}_2 = \{ [2],[1,1]\}$

$\mathbf{C}_3 = \{ [3],[2,1],[1,2],[1,1,1]\}$

$\mathbf{C}_4 = \{ [4],[3,1],[1,3],[2,2], [2,1,1], [1,2,1], [1,1,2], [1,1,1,1]\}$

# 4. Properties

# 5. Statistics

We have the following **37 statistics** in the database:

The major index of the composition.

The number of standard immaculate tableaux of a given shape.

The absolute variation of a composition.

The variation of a composition.

The descent variation of a composition.

The size of the preimage of the map 'descent composition' from Permutations to In....

The size of the preimage of the map 'to inverse des composition' from Parking fun....

The largest part of an integer composition.

The first part of an integer composition.

The last part of an integer composition.

The smallest part of an integer composition.

The length of the longest weakly inreasing subsequence of parts of an integer com....

The length of the longest staircase fitting into an integer composition.

The length of the longest strictly decreasing subsequence of parts of an integer ....

The number of ascents in an integer composition.

The sum of the positions of the weak records of an integer composition.

The sum of the positions of the strong records of an integer composition.

The number of strong records in an integer composition.

The number of weak records in an integer composition.

The number of inversions of an integer composition.

The number of runs in an integer composition.

The number of peaks in an integer composition.

The major index of a composition.

The number of peaks of the associated bargraph.

The semiperimeter of the associated bargraph.

The sum of the heights of the valleys of the associated bargraph.

The number of up steps of the associated bargraph.

The number of standard composition tableaux of the composition.

The sum of the entries in the column specified by the composition of the change o....

The sum of the entries in the column specified by the composition of the change o....

The number of compositions obtained by rotating the composition.

The maximal number of repetitions of an integer composition.

The minimal number of repetitions of a part in an integer composition.

The minimal number of repetitions of an integer composition.

The number of different parts of an integer composition.

The maximal number of repetitions of an integer composition.

The number of different multiplicities of parts of an integer composition.

# 6. Maps

We have the following **13 maps** in the database:

Mp00038
Integer compositions ⟶ Integer compositions

reverse

Mp00039
Integer compositions ⟶ Integer compositions

complement

Mp00040
Integer compositions ⟶ Integer partitions

to partition

Mp00041
Integer compositions ⟶ Integer compositions

conjugate

Mp00054
Parking functions ⟶ Integer compositions

to inverse des composition

Mp00057
Parking functions ⟶ Integer compositions

to touch composition

Mp00071
Permutations ⟶ Integer compositions

descent composition

Mp00094
Integer compositions ⟶ Binary words

to binary word

Mp00097
Binary words ⟶ Integer compositions

delta morphism

Mp00100
Dyck paths ⟶ Integer compositions

touch composition

Mp00102
Dyck paths ⟶ Integer compositions

rise composition

Mp00128
Set partitions ⟶ Integer compositions

to composition

Mp00133
Integer compositions ⟶ Integer compositions

delta morphism

# 7. References

# 8. Sage examples