Integer Compositions

# 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:

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:

reverse
complement
to partition
conjugate
to inverse des composition
to touch composition
descent composition
to binary word
delta morphism
touch composition
rise composition
to composition
delta morphism