Exercise 13. [M23] Show that (16) is the number of permutations of $p+q+1$ distinct elements having the pattern (15).

Verified: yes
Solve time: 2m21s

Solution

Pattern (15) is the unimodal pattern

$$ x_0 < x_1 < \cdots < x_p > x_{p+1} > \cdots > x_{p+q}, $$

on $p+q+1$ distinct elements.

To count the permutations having this pattern, let the underlying set of values be

$$ {1,2,\ldots,p+q+1}. $$

The element at the peak, $x_p$, must be the largest value $p+q+1$. If any smaller value occupied the peak position, the larger value would have to occur somewhere to the left or right, contradicting the inequalities on that side.

After fixing $x_p=p+q+1$, there remain $p+q$ values. Choose which $p$ of these values will occupy the positions

$$ x_0,x_1,\ldots,x_{p-1}. $$

There are

$$ \binom{p+q}{p} $$

ways to make this choice.

Once the set of values on the left side has been chosen, their order is forced, since

$$ x_0<x_1<\cdots<x_{p-1}<x_p. $$

They must therefore appear in increasing order.

The remaining $q$ values occupy the positions

$$ x_{p+1},\ldots,x_{p+q}. $$

Their order is also forced, since

$$ x_p>x_{p+1}>\cdots>x_{p+q}. $$

They must therefore appear in decreasing order.

Hence each choice of $p$ values for the left side determines exactly one permutation having pattern (15), and every permutation having pattern (15) arises from exactly one such choice.

Therefore the number of permutations of $p+q+1$ distinct elements having pattern (15) is

$$ \binom{p+q}{p}

\frac{(p+q)!}{p!,q!}. $$

This is precisely equation (16). Therefore (16) is the number of permutations of $p+q+1$ distinct elements having the pattern (15).

This completes the proof.

∎

TAOCP 3.3.2 Exercise 13

Solution

$$ \binom{p+q}{p}