0
$\begingroup$

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\}$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Colm Bhandal Nov 26 '15 at 16:25
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks a lot! btw if I wanted to do the same with more than 2 sets can I use the same logic or it is something entirely different? $\endgroup$ – Anastasios Andronidis Nov 26 '15 at 17:00
  • $\begingroup$ 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}$. $\endgroup$ – rogerl Nov 26 '15 at 17:04
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! btw if I wanted to do the same with more than 2 sets can I use the same logic or it is something entirely different? $\endgroup$ – Anastasios Andronidis Nov 26 '15 at 17:00
  • $\begingroup$ 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. $\endgroup$ – Colm Bhandal Nov 26 '15 at 17:08

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.