5
$\begingroup$

Given 4 flags of different colours, how many different signals can be generated. If a signal requires the use of 2 flags one below the other?

Le the colours be R , B , G , O.

My book answers it as = 4 *3 = 12 which is right answer but not conceptually right .

4 means 4 choices I.e R,B,G,O. Then for 3 choices , we have B,G,O.

Now , if you see . Total combinations it will give is RB RG RO , BB BG BO , GB GG GO , OB OG OO. Here , OO GG BB are wrong combinations .

So , if I remove them there are total 9 now. But we need 3 more . Those are BR , OR and GR.

Please tell if i am right till here ?

How to consider them then ? Now , all this cutting and then adding made the solution way also long .

Is there a shorter way of doing and how to revive those BR , OR , GR without counting it knowing and also to cut BB , GG , OO without counting.

$\endgroup$
6
$\begingroup$

The answer that the book provides you is the direct application of the following formula: $$ nP_k = {\displaystyle\prod_{i=0}^{k-1} (n - i)}=\dfrac{n!}{(n-k)!} $$

If we plug $n=4$ (our pool of distinct flags) and $k=2$ (the number of flags to sample in order to build a signal), according to the problem statement, the formula will yield: $$ 4P_2 = \dfrac{4!}{(4-2)!}=\dfrac{4!}{2!} = \dfrac{4\cdot 3\cdot 2\cdot 1}{2\cdot 1}= 4\cdot 3 = 12 $$

As you correctly pointed out that $12$ is the right answer.

Now for the intuition behind the problem and in general when we have to deal with ordered permutations, we can think of the problem as follows:

Let's suppose that we have two placeholders for any of the available flags, denoted as $F_1 \, F_2$ . Furthermore, since the order of the flags matters $F_1 \, F_2 \ne F_2 \, F_1$, this leaves us with $n=4$ possible options for the $F_1$ placeholder and $n-1=3$ for the $F_2$ placeholder. This is because initially the whole set of flags is available for selection e.g. $F=\{R,B,G,O\}$, picking any flag from this set leaves us only three of the rest flags available for selection:

  • Case 1: First choice is $\color{red}R$ from the whole set of flags $\{R,B,G,O\}$ $$R \, F_2$$ this entails that the second flag must be sampled from the following set $\{B,G,O\}$. This leads to, the following three permutations: $$\mathbf{\color{red}R}\color{blue}B, \, \mathbf{\color{red}R}\color{green}G, \, \mathbf{\color{red}R}\color{orange}O$$

  • Case 2: First choice is $\color{blue}B$, then the possible values for $F_2$ are $\{R,G,O\}$ $$\mathbf{\color{blue}B}\color{red}R, \, \mathbf{\color{blue}B}\color{green}G, \, \mathbf{\color{blue}B}\color{orange}O$$

  • Case 3: First choice is $\color{green}G$, then the possible values for $F_2$ are $\{R,B,O\}$ $$\mathbf{\color{green}G}\color{red}R, \, \mathbf{\color{green}G}\color{blue}B, \, \mathbf{\color{green}G}\color{orange}O$$

  • Case 4: First choice is $\color{orange}O$, then the possible values for $F_2$ are $\{R,B,G\}$ $$\mathbf{\color{orange}O}\color{red}R, \, \mathbf{\color{orange}O}\color{blue}B, \, \mathbf{\color{orange}O}\color{green}G$$

Each of the $4$ cases having $3$ possible permutations. Putting it all together we have $12$ permutations: $$\mathbf{\color{red}R}\color{blue}B, \, \mathbf{\color{red}R}\color{green}G, \, \mathbf{\color{red}R}\color{orange}O, \, \mathbf{\color{blue}B}\color{red}R, \, \mathbf{\color{blue}B}\color{green}G, \, \mathbf{\color{blue}B}\color{orange}O, \, \mathbf{\color{green}G}\color{red}R, \, \mathbf{\color{green}G}\color{blue}B, \, \mathbf{\color{green}G}\color{orange}O, \, \mathbf{\color{orange}O}\color{red}R, \, \mathbf{\color{orange}O}\color{blue}B, \, \mathbf{\color{orange}O}\color{green}G$$

If we think about the product series from the $nP_{k}$ formula we can see its connection to the physical intuition. $$ \begin{aligned} nP_k &= {\displaystyle\prod_{i=0}^{k-1} (n - i)} \\ &= n \cdot {\displaystyle\prod_{i=1}^{k-1} (n - i)} \\ &= n\cdot (n-1) \cdot {\displaystyle\prod_{i=2}^{k-1} (n - i)} \\ &= n \cdot (n-1) \cdot (n-2) \cdot {\displaystyle\prod_{i=3}^{k-1} (n - i)} \end{aligned} $$

What one might notice is that each increment of the product series index variable $i$ multiplies the current product by the cardinality of the remaining set of flags e.g. the number of the available flags in the current set. This will carry on until all $k$ placeholders are filled, again considering all remaining flags currently in the set, according to its index number e.g. the current cardinality of the set, denoted as $n-i$ with $i \in [0, k) \subset \mathbb N_0$.

Note :
  This problem is about permutations, your attempt to solve the problem suggests that you calculated the cartesian product of the set with itself and then correctly waived out the invalid combinations namely $RR, GG, BB, OO$. The latter is a hint that any flag once chosen from the set, is not placed back in it, i.e. there is no replacement of the flags in the set. The second hint about the problem is that order matters that is $F_1F_2 \ne F_2F_1$ i.e. $RB \ne BR$. This suggests that counting the combinations (unordered edition of the problem) is not the answer. However, had the order been irrelevant, then you could use the $nC_k = \dfrac{n!}{(n-k)!\cdot k!}$ to calculate all possible unordered combinations. It might be apparent to you that $nP_k$ and $nC_k$ relate through $ nP_k = k! \cdot nC_k$. Since $k=2$ this means that $nP_2 = 2\cdot nC_2$ which could be intuitively derived from the fact that once you have written down the unordered combinations then you must add them again but in flipped order, to account for the other combinations that you have pointed out. Beware that this only works when $k=2$.

$\endgroup$
4
$\begingroup$

We have one flag each of $4$ colors - $R, B, G, O$. We need to make a signal with two flags and order matters.

So if we pick any of the color as first, we have $3$ choices for the second color. If $R$ is first, we have $3$ choices for second $B, G, O$. If $B$ is first, we again have $3$ choices for second color - $R, G, O$.

Hence total number of different signals that we can make $ = 4 \times 3 = 12$, which is $4$ choices for the first color and $3$ choices for the second for each of the first.

$\endgroup$
2
  • 3
    $\begingroup$ Yes, this is the issue - whatever you choose for the first flag gives three options for the second, but not the same three options. $\endgroup$ Feb 11 at 13:53
  • $\begingroup$ @EspeciallyLime yes that is correct. $\endgroup$
    – Math Lover
    Feb 11 at 13:55
0
$\begingroup$

The remaining three colors with be a different set of three colors depending on the color you pick first.

If you pick $R$ first the remaining three colors are $B,G,O$ for three signals: $RB,RG,RO$.

But if you pick $B$ first your remain three colors are $R,G,O$ for tree signals: $BR, BG, BO$.

And if you pick $G$ first your remaining three colors are $R,B,O$ for $GR, GB,GO$.

And if pick $O$ first your remaining three colors are $R,B, G$ for $OR,OB, OG$. Those are the $12$.

We didn't have to count them. We knew there where $4$ options for the first color, and we knew once we picked the first color there would be $3$ remaining colors for the second. That they would be different set of three colors wouldn't matter as long as we knew there'd be $3$ remaining colors.

So we calculate $4\times 3 = 12$.

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