# How To Count Shuffle permutations

Let $n\in \mathbb{N}$ and $S(n)$ the permutation group on $\{1,\ldots,n\}$.

For any $p,q\in \mathbb{N}$ with $p+q=n$, the set $Sh(p,q)\subset S(n)$ is the set of all permutations $\tau$ such that $\tau(1)< \cdots \tau(p)$ and $\tau(p+1)<\cdots <\tau(n)$, usually called the set of $(p,q)$-shuffles.

More generally for any $k;p_1,\ldots,p_k\in\mathbb{N}$ with $p_1+\cdots +p_k=n$, the set of $(p_1,\ldots,p_k)$-shuffles $Sh(p_1,\ldots,p_k)\subset S(n)$ is the set of all permutations $\tau$, such that $\tau(1)< \cdots \tau(p_1)$, $\tau(p_1+1)<\cdots <\tau(p_2)$ (up to) $\tau(n-p_k+1)<\cdots <\tau(n)$.

====

Now the question is: HowTo calculate the cardinality $|Sh(p_1,\ldots,p_k)|$?

I know that $|Sh(p,q)|=\binom{p+q}{q}$ but just as a fact. From empirical tests I would 'guess' $|Sh(p_1,\ldots,p_k)|=\binom{n}{p1,\ldots,p_k}$, where the expression on the left means the multinomial coefficient, but I'm more interested in deriving such an appropriate expression.

Choose $p$ numbers from the set $1..n$ and there is a unique shuffle such that $\tau(1)..\tau(p)$ to have those $p$ values and the other $q$ fill in the remaining places. The multinomial coefficinet $n\choose p_1...p_k$ is the number of ways to partition $1..n$ into subsets of cardinality $p_i$, and each subset can again be ordered each such partition is a unique shuffle.