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** on **Integer compositions** 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'

Mp00071descent composition from Permutatio....

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** from and to **Integer compositions** 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