# Permutations of sorted multisets

I am new to combinatorics and might ask a trivial question:

Given two ordered sets $S_a=\left\{1_a, 2_a, 3_a, \dots, n_a\right\}$ and $S_b=\left\{1_b, 2_b, 3_b, \dots, n_b\right\}$

How can I calculate all the possible permutations between $S_a$ and $S_b$ but keeping the order between the items of the set intact?

e.g.

$\left\{1_a, 1_b, 2_a, 2_b, 3_a, 3_b, \dots, n_a, n_b\right\}$

$\left\{1_b, 1_a, 2_a, 2_b, 3_a, 3_b, \dots, n_a, n_b\right\}$

$\dots$

$\left\{1_a, 1_b, 2_b, 3_b, 2_a, 3_a, \dots, n_a, n_b\right\}$

$\dots$

But you can never have something like this:

$\left\{1_a, 2_b, 1_b, 3_b, 2_a, 3_a, \dots, n_a, n_b\right\}$

• Please let me know if my answer below is satisfactory. I can explain it more, but would like you to get it for yourself it possible. Nov 26, 2015 at 16:25

The answer is $\dbinom{2n}{n}$. To see this, think of each $a$ as a step east, and each $b$ as a step north. Then the number of interleavings counts the number of different ways to get from $(0,0)$ to $(n,n)$ in the Cartesian plane moving only north or east. This is well known to be $\dbinom{2n}{n}$ (for example, look here
Another way to see that the answer is $\dbinom{2n}{n}$ is to note that all you are really doing is taking $2n$ elements and choosing $n$ of those (the $b$'s, for example).
• No, it's exactly the same: for three sets, for example, you want to choose $n$ $a$'s and $n$ $b$'s from $3n$ elements, so you get $\dbinom{3n}{n,n,n}$. Nov 26, 2015 at 17:04
In this specific case, the answer is $2n \choose n$, given that the sets have the same number of elements. Can you see why? In general, you could have $m + n \choose m$, given $m$ elements in one set and $n$ in the other. Even more general, for more than two sets, you look to the multinomial theorem.
• It's the same logic. You use the multinomial theorem. In the case of two sets, you choose the elements from the big set that are to be drawn from one (or the other) of the smaller sets. In general, you do this $n-1$ times, for any $n-1$ of the $n$ multisets. The formula is given in the link. Nov 26, 2015 at 17:08