Unexpected result on the number of permutations with a restriction.

Question

Let $p=(p_1,p_2,\dots,p_n)$ be a weak composition of a positive integer number $n$ into $n$ non-negative integer parts and let $k_i$ be the count of the part $i$ ($i=0,1,2,\dots$) in the composition.

A permutation $\tilde p$ of $p$ is allowed if its partial sums obey the inequality: $$ \forall m (1\le m\le n):\ s_m\equiv\sum_{j=1}^m \tilde p_j\ge m. $$

The simple but rather unexpected result valid by numerical evidence is that the number of allowed permutations is $$ \frac{n!}{\displaystyle(k_0+1)!\prod_{i>0}k_i!}.\tag1 $$

This means that the number is exactly $n+1$ times less than the number of all permutations of the composition supplemented by an additional 0. This simplicity suggests that there should be almost obvious explanation of the fact but I could not find it.

Any hint is appreciated.

Answer 1

Given any weak composition $p = (p_1, p_2, \ldots, p_n)$, append an extra $0$ to it, and consider the rearrangement $ p' = (p_1' p_2', \ldots , p_n', p_{n+1}' )$.
There are $\frac{ (n+1)! } { (k_0 + 1) ! \prod k_i ! } $ such rearrangements.
We can naturally pair them up into groups of size $n+1$, obtained by cyclically permuting the indices.

For such a rearrangement, we associate it to the "up and right path" of:

• Start at $(0,0)$,
• Go up $p'_1$, go right 1.
• Go up $p'_2$, go right 1.
• $\ldots $
• Go up $p'_n$, go right 1.
• Go up $p'_{n+1}$, which brings us to $(n, n)$.

We use the bijection as described in the third proof of Catalan's number. The following is a section of the writeup which contains the necessary information, though I encourage you to read the full details on Wikipedia for more context.

The exceedance of the path is defined to be the number of vertical edges which lie above the diagonal.

Given a path whose exceedance is not 0, then we may apply the following algorithm to construct a new path whose exceedance is one less than the one we started with.

• Starting from the bottom left, follow the path until it first travels above the diagonal.
• Continue to follow the path until it touches the diagonal again. Denote by X the first such edge that is reached.
• Swap the portion of the path occurring before X with the portion occurring after X.

The algorithm will cause the exceedance to decrease by one, for any path that we feed it, because the first vertical step starting on the diagonal (at the point marked with a black dot) is the unique vertical edge that under the operation passes from above the diagonal to below it; all other vertical edges stay on the same side of the diagonal.

It is also not difficult to see that this process is reversible: given any path P whose exceedance is less than n, there is exactly one path which yields P when the algorithm is applied to it.

Using this algorithm, we conclude that the $n+1$ cyclic permutations each have a unique exceedance. Since this exceedance ranges from 0 to $n$, and there are $n+1$ of them, hence it's exactly the integers from 0 to $n$ (inclusive).

Here's the bijection for the case of $n = 3$.
The rows are cyclic permutations of $ (3,0,0,0), (2, 1, 0, 0), (1, 2, 0, 0), (2, 0, 1, 0), (1, 1, 1, 0)$.
The columns have exceedance $3, 2, 1, 0$.

_{(source: wikimedia.org)}

Now, verify that an allowed permutation has an associated staircase diagram that stays on or above the line $ y = x$, hence has exceedence exactly $n$.

Finally, the number of allowed permutations is (the desired): $$ \frac{1}{n+1} \times \frac{ (n+1)! } { (k_0 + 1) ! \prod k_i ! } = \frac{ (n)! } { (k_0 + 1) ! \prod k_i ! } $$

In the case of $n=3$, this corresponds to the first column, and the allowed permutations are $(3, 0, 0), (1, 2, 0), (2, 0, 1), (1, 1, 1)$.

---

Corollary: The total number of allowed permutations is the Catalan number $C_n$.