# 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 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' from Permutations to In....
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 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