(math) Weak compositions as products of compositions and weak compositions

26 Oct, 2026

Let us start by recalling the definitions of compositions and weak compositions. A composition of $n$ of length $k$ is a list of $k$ positive integers that sum to $n$ . A weak composition is the same idea but we are allowed to use zeros. Denote the former set by $C_{k} (n)$ and the set of weak compositions of $n$ of length $k$ by $W_{k} (n)$ . The list $(1, 2, 1, 3) \in C_{4} (7)$ and $(0, 1, 4, 0, 2) \in W_{5} (7)$ .

I am going to prove the following result for $n \geq 1$ ,
$W_{k} (n) = ⨆_{j = 1}^{k} C_{j} (n) \times W_{j + 1} (k - j)$ but before I do that, I wanna tell you how I ended here in the first place. A project of mine looks at the behavior of the ${\hat{s}}_{r}$ statistic on weak compositions. The details of this function don't matter at the moment. If I want to understand this function for an input composition $β$ , I first need to compute it on a subset of weak compositions and sum all the outputs. What is this particular subset? These are all the weak compositions of length $r$ which yield $β$ when I remove all the zeros and preserve the order of entries. So, for a composition $(1, 2, 1)$ and $r = 5$ , the subset would include the weak compositions $(0, 1, 0, 2, 1)$ , $(1, 0, 0, 2, 1)$ and so on. One method to generate this subset is to start with the composition, and insert zeros between the entries. For a composition of length $j$ , there are $j + 1$ spots to insert the zeros, and I can choose how to insert them.

Okay, it's now time for the proof! I will use exponential notation $a^{b}$ which means that $a$ appears $b$ times consecutively. If $b = 0$ , then $a^{b}$ is the empty string.

Proof. First pick $w \in W_{k} (n)$ . Define $β_{w}$ to be the composition obtained by removing all the zeros in $w$ while preserving the order of the entries. Suppose $β_{w}$ has $j$ entries, then let $v_{w} = (v_{0}, v_{1}, \dots, v_{j})$ be a weak composition where $v_{0}$ is the number of zeros in the beginning of $w$ , $v_{i}$ for $i = 1, 2, \dots, j - 1$ is the number of zeros to the right of $β_{i}$ and to the left of $β_{i + 1}$ , and $v_{j}$ is the number of zeros at the end of $w$ . This gives us the map from $w$ to the pair $(β_{w}, v_{w}) \in ⨆_{j = 1}^{k} C_{j} (n) \times W_{j + 1} (k - j)$ .
On the other hand, if we start with $(β, v) \in C_{j} (n) \times W_{j + 1} (k - j)$ , then we can define $w (β, v) = (0^{v_{0}}, β_{1}, 0^{v_{1}}, β_{2}, 0^{v_{2}}, \dots, 0^{v_{j - 1}}, β_{j}, 0^{v_{j}})$ , which is an element of $W_{k} (n)$ . $◻$

Bonus: the way to generate weak compositions in SageMath is by using IntegerVectors.