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 11 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.

# 6. Maps

We have the following 5 maps in the database:

reverse
complement
to partition
conjugate
to binary word

# 8. Sage examples

IntegerCompositions (last edited 2015-10-30 15:54:33 by ChristianStump)