# 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

• $|\mathbf{C}_n| = 2^{n-1}$.

# 5. Statistics

We have the following 37 statistics on Integer compositions in the database:

St000008 Integer compositions ⟶ ℤ
The major index of the composition.
St000047 Integer compositions ⟶ ℤ
The number of standard immaculate tableaux of a given shape.
St000089 Integer compositions ⟶ ℤ
The absolute variation of a composition.
St000090 Integer compositions ⟶ ℤ
The variation of a composition.
St000091 Integer compositions ⟶ ℤ
The descent variation of a composition.
St000277 Integer compositions ⟶ ℤ
The size of the preimage of the map 'descent composition' Mp00071descent composition from Permutatio....
St000285 Integer compositions ⟶ ℤ
The size of the preimage of the map 'to inverse des composition' from Parking fun....
St000381 Integer compositions ⟶ ℤ
The largest part of an integer composition.
St000382 Integer compositions ⟶ ℤ
The first part of an integer composition.
St000383 Integer compositions ⟶ ℤ
The last part of an integer composition.
St000657 Integer compositions ⟶ ℤ
The smallest part of an integer composition.
St000757 Integer compositions ⟶ ℤ
The length of the longest weakly inreasing subsequence of parts of an integer com....
St000758 Integer compositions ⟶ ℤ
The length of the longest staircase fitting into an integer composition.
St000760 Integer compositions ⟶ ℤ
The length of the longest strictly decreasing subsequence of parts of an integer ....
St000761 Integer compositions ⟶ ℤ
The number of ascents in an integer composition.
St000762 Integer compositions ⟶ ℤ
The sum of the positions of the weak records of an integer composition.
St000763 Integer compositions ⟶ ℤ
The sum of the positions of the strong records of an integer composition.
St000764 Integer compositions ⟶ ℤ
The number of strong records in an integer composition.
St000765 Integer compositions ⟶ ℤ
The number of weak records in an integer composition.
St000766 Integer compositions ⟶ ℤ
The number of inversions of an integer composition.
St000767 Integer compositions ⟶ ℤ
The number of runs in an integer composition.
St000768 Integer compositions ⟶ ℤ
The number of peaks in an integer composition.
St000769 Integer compositions ⟶ ℤ
The major index of a composition.
St000805 Integer compositions ⟶ ℤ
The number of peaks of the associated bargraph.
St000806 Integer compositions ⟶ ℤ
The semiperimeter of the associated bargraph.
St000807 Integer compositions ⟶ ℤ
The sum of the heights of the valleys of the associated bargraph.
St000808 Integer compositions ⟶ ℤ
The number of up steps of the associated bargraph.
St000816 Integer compositions ⟶ ℤ
The number of standard composition tableaux of the composition.
St000817 Integer compositions ⟶ ℤ
The sum of the entries in the column specified by the composition of the change o....
St000818 Integer compositions ⟶ ℤ
The sum of the entries in the column specified by the composition of the change o....
St000820 Integer compositions ⟶ ℤ
The number of compositions obtained by rotating the composition.
St000899 Integer compositions ⟶ ℤ
The maximal number of repetitions of an integer composition.
St000900 Integer compositions ⟶ ℤ
The minimal number of repetitions of a part in an integer composition.
St000902 Integer compositions ⟶ ℤ
The minimal number of repetitions of an integer composition.
St000903 Integer compositions ⟶ ℤ
The number of different parts of an integer composition.
St000904 Integer compositions ⟶ ℤ
The maximal number of repetitions of an integer composition.
St000905 Integer compositions ⟶ ℤ
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