5

I've been trying to get a general formula for this, but I couldn't find anything exactly what I need. What I want is, let's say we have 3 groups:

(x,y,z),(a,b,c) and (k,l,m)

What is the total number of permutations of these three occurring in a single group while they keep their initial order, but can intertwine with other groups? Is there a general formula for this or can we derive it somehow?

e.g. (x,a,b,k,y,c,l,m,z) or (k,l,a,x,b,y,z,m,c)

notice that x always comes before y and y always comes before z in the combined group, same goes for other groups too.

In a small scale with 2 groups:

(1,2) and (3,4)

All possibilities: (1,2,3,4) (1,3,4,2) (1,3,2,4) (3,4,1,2) (3,1,2,4) (3,1,4,2)

Is there a formula which would give me the number "6" for these two groups?

Thanks!

pdace
  • 153
  • Do it one group at a time. Consider the groups $(a,b,c) $ and $(a',b',c') $. Start with $a, b, c $, leaving 4 gaps to place the other letters from the other letter group. Consider how many combinations of filling the gaps you can have. – Will Fisher Jul 18 '16 at 00:47
  • @WillFisher what are you talking about gaps for? Order within a gap matters and multiple can be placed into the same gap... – JMoravitz Jul 18 '16 at 00:58
  • @JMoravitz Yes a simple set of nested summations can account for order. Upon doing that, a group of letters being placed in the same gap will only occur once (permutations of those letters in the gap won't be additionally counted) at which point you assume the order of the letters in the gap to be in order. – Will Fisher Jul 18 '16 at 01:03
  • @WillFisher It sounds like then, using the same notation I use below for groups and number of elements in each group, that you propose: take the first group, weave the second group into the first in $\binom{\alpha+\beta}{\beta}$ ways. Weave the third group into the result in $\binom{\alpha+\beta+\kappa}{\kappa}$ ways, etc... I will admit, I have never seen the multinomial coefficient formula derived in reverse like this, usually I see $\binom{N}{\alpha}\binom{N-\alpha}{\beta}\dots$ instead. The formula for multinomials should already be known, so I still think deriving it again is overkill. – JMoravitz Jul 18 '16 at 01:15

2 Answers2

6

Let your groups be group $A = (a_1,a_2,\dots,a_\alpha)$ group $B = (b_1,b_2,\dots,b_\beta)$, on up to group $K = (k_1,k_2,\dots,k_\kappa)$ with intended order $a_1<a_2<\dots<a_\alpha$ and similarly for the other letters as well.

Let $\alpha+\beta+\dots+\kappa = N$

Relate this problem to the problem of arranging letters in the word:

$$\underbrace{aaaaa\dots a}_{\alpha~\text{copies}}\underbrace{bbbbb\dots b}_{\beta~\text{copies}}\dots\underbrace{kkkkkk\dots k}_{\kappa~\text{copies}}$$

From earlier example, we know the number of arrangements to be:

$$\binom{N}{\alpha,\beta,\dots,\kappa} = \frac{N!}{\alpha!\beta!\dots\kappa!}$$

Given an arrangement of the word $aa\dots k$ as above, replace each $a$ by $a_1,a_2,\dots,a_\alpha$ with the leftmost $a$ as $a_1$, the second leftmost $a$ as $a_2$, etc... Similarly for the other letters.

Your example of $(1,2)$ and $(3,4)$, we have two groups of two, and a total of four elements for a total of $\binom{4}{2,2}=\frac{4!}{2!2!}=6$ arrangements.

Your example of $(x,y,z),(a,b,c),(k,l,m)$ we have three groups of three for a total of nine elements and therefore a total of $\binom{9}{3,3,3}=\frac{9!}{3!3!3!} = 1680$ arrangements.

JMoravitz
  • 79,518
2

If you haven't graduated to the multinomial coefficient, here is a simple way.

Using the same example of $(x,y,z),(a,b,c),(k,l,m)$, imagine $9$ slots are available.

Place $(x,y,z)\;$ in this order$\;$ in $\binom 93$ ways,
and $(a,b,c)$, similarly in the remaining slots in $\binom63$ ways,
to get a total of $\binom 93 \binom 63$ ways

[ The last group, of course, automatically goes into the remaining $3$ slots ]

true blue anil
  • 41,295