2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.