Section 5.1.4: Tableaux and Involutions

Exercise 10. [M20] [M20] How many permutations of the multiset ${1^a, 2^b, 3^c}$ have the property that, as we read the permutation from left to right, the number of 3’s never exceeds the number of 2’s, and the number of 2’s never exceeds the number of 1’s? (For example, $aabcabbcac$ is such a permutation.)

Verified: no
Solve time: 16m42s

---

Solution

Let

$$ N(a,b,c) $$

denote the number of permutations of the multiset

$$ {1^a,2^b,3^c} $$

such that in every initial segment the number of $3$'s does not exceed the number of $2$'s, and the number of $2$'s does not exceed the number of $1$'s.

The condition implies immediately that

$$ a\ge b\ge c, $$

since it must hold for the complete word as well. If either $b>a$ or $c>b$, no such permutation exists, and $N(a,b,c)=0$.

Assume therefore that $a\ge b\ge c$.

Associate with a word a lattice path in $\mathbf Z^3$ from $(0,0,0)$ to $(a,b,c)$, where the symbols $1,2,3$ correspond respectively to unit steps in the $x$-, $y$-, and $z$-directions. The required condition becomes

$$ x\ge y\ge z $$

at every point of the path.

Hence $N(a,b,c)$ is the number of lattice paths from $(0,0,0)$ to $(a,b,c)$ that remain in the Weyl chamber

$$ x\ge y\ge z . $$

The total number of unrestricted paths is

$$ \frac{(a+b+c)!}{a!,b!,c!}. $$

To count only those paths that stay in the chamber, apply the reflection principle for the chamber $x\ge y\ge z$. The bounding hyperplanes are

$$ x=y,\qquad y=z. $$

For the symmetric group $S_3$, each permutation $\sigma$ of the coordinates contributes a sign $\operatorname{sgn}(\sigma)$. The standard reflection-principle formula gives

$$ N(a,b,c)

\sum_{\sigma\in S_3} \operatorname{sgn}(\sigma), \frac{(a+b+c)!} {(a-\sigma(1)+1)!, (b-\sigma(2)+2)!, (c-\sigma(3)+3)!}, $$

which simplifies to the determinant

$$ N(a,b,c)

(a+b+c)! \det \begin{pmatrix} \dfrac1{a!} & \dfrac1{(a+1)!} & \dfrac1{(a+2)!}\[2ex] \dfrac1{(b-1)!} & \dfrac1{b!} & \dfrac1{(b+1)!}\[2ex] \dfrac1{(c-2)!} & \dfrac1{(c-1)!} & \dfrac1{c!} \end{pmatrix}. $$

Factor

$$ \frac1{a!,b!,c!} $$

from the determinant. Since

$$ \frac{a!}{(a+1)!}=\frac1{a+1}, \qquad \frac{a!}{(a+2)!}=\frac1{(a+1)(a+2)}, $$

and similarly for the other rows, the determinant becomes

$$ \frac1{a!,b!,c!} \det \begin{pmatrix} 1 & \dfrac1{a+1} & \dfrac1{(a+1)(a+2)}\[2ex] b & 1 & \dfrac1{b+1}\[2ex] c(c-1) & c & 1 \end{pmatrix}. $$

A straightforward evaluation yields

$$ \det

\frac{(a-b+1)(a-c+2)(b-c+1)} {(a+1)(a+2)(b+1)}. $$

Therefore

$$ N(a,b,c)

\frac{(a+b+c)!}{a!,b!,c!}, \frac{(a-b+1)(a-c+2)(b-c+1)} {(a+1)(a+2)(b+1)}. $$

Thus the number of desired permutations is

$$ \boxed{ N(a,b,c)

\frac{(a+b+c)!}{a!,b!,c!}, \frac{(a-b+1)(a-c+2)(b-c+1)} {(a+1)(a+2)(b+1)} } $$

for $a\ge b\ge c$, and

$$ \boxed{N(a,b,c)=0} $$

otherwise. ∎