5
$\begingroup$

I have these base values "$a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4,c_1,c_2,c_3,c_4$" and I have to find how many different ways I can arrange them. Rules are these, for example $a_2$, can't come before $a_1$, all a's have to be in order. same goes for b's and c's. But for example $b_1$ or $c_1$ can come before $a_2$ etc.

Here is incorrect line: $a_1,b_1$,$a_3$, $a_2$,$b_2,b_3,b_4,c_1,c_2,c_3,c_4,a_4$ // $a_3$ comes before $a_2$, so a's are not in correct order.

Here is correct line: $b_1,a_1,a_2,c_1,a_3,b_2,a_4,c_2,b_3,b_4,c_3,c_4$ // everything is fine.

I'd like to know is there any formulas that can solve this?

$\endgroup$
5
$\begingroup$

Take $4$ red sticks, $4$ blue sticks and $4$ yellow sticks and arrange them in a row of $12$ sticks.

The positions for the red sticks can be chosen in $\binom {12}{4}$ ways.

The blue sticks have to be fitted into the eight positions which remain, which can be done in $\binom 84$ ways, and the yellow sticks fit in the four remaining places. This is $\binom 44$ ways if you like to be neat.

The first red stick is the position for $a_1$, the second for $a_2$ etc. The blue sticks locate the $b_i$ and the yellow sticks the $c_i$. It is easy to see there is a bijection between the two kinds of arrangement - colours and letters - each determines the other.

So the answer is $$\binom {12}{4}\binom 84\binom 44=\binom {12}{4}\binom 84$$

$\endgroup$
1
$\begingroup$

There are $12$ symboles, so $12!$ possibilities to order them without taking into account rules. Let $A$ be the set of all these sequences.

Let $S_4$ be the group of permutations of 4 elements. $(S_4)^3$ acts on $A$ in the following way: For example, let $\sigma=(\sigma_a,\sigma_b,\sigma_c)\in(S_4)^3$, then $$\sigma(b_1,a_1,a_2,c_1,a_3,b_2,a_4,c_2,b_3,b_4,c_3,c_4) =b_{\sigma_b (1)},a_{\sigma_a (1)},a_{\sigma_a (2)},c_{\sigma_c (1)},a_{\sigma_a (3)},b_{\sigma_b (2)},a_{\sigma_a (4)},c_{\sigma_c (1)},b_{\sigma_b (3)},b_{\sigma_b (4)},c_{\sigma_c (3)},c_{\sigma_c (4)}.$$ The correct sequences are representant of each orbit of this group action. So the number of correct sequences is the number of orbits: $$\mathrm{Card}(A)/\mathrm{Card}((S_4)^3)=12!/((4!)^3)=34\ 650.$$

$\endgroup$
  • 1
    $\begingroup$ Note that we (obviously) find the same result as @MarkBennet :$$\binom {12}{4}\binom 84\binom 44=\frac{12!}{4!8!}\frac{8!}{4!4!}\frac{4!}{4!1!}=\frac{12!}{4!} \frac{1}{4!} \frac{1}{4!}=\frac{12!}{(4!)^3}.$$ $\endgroup$ – Gilles Bonnet Sep 2 '13 at 20:53

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.