3
$\begingroup$

I encountered this question recently:

Suppose there are 3 benches in the front row and 7 benches in the second row, how many ways a group of 10 children can be seated in such arrangement?

There were given two solutions to the same problem:

  1. Its an Arrangement hence there are $10!$ ways. The solution seem easy to understand.
  2. The other solution was like:

We can choose $3$ children for the first row in $10\choose 3$ ways, those $3$ can be arranged in $3!$ ways and the remaining $7$ can be arranged in $7!$ ways in the back row. So, the total number of ways are ${10 \choose 3}*3!*7!$ which equals $10!$.

I seriously got bowled over by the second solution, it went over my head like anything.

I am new to discrete math and as far as I know counting boils down to two simple rules sum and product. Both of the above solutions are using the same product rule but why I am failing to understand the second one?

Question

I know the product rule but still the multiplication of the sub-parts is not making sense to me. How, to understand or get better mental model of it?

$\endgroup$
  • $\begingroup$ Imagine the following scenario, you have twelve balls, each of which numbered and distinct. Six of which are red, and Six of which are blue (e.g. red1, red2, ... red 6, blue 1, blue 2,... blue 6). How many ways can you draw one ball? Well, there are twelve balls, so twelve different ways. We could have seen this a different way as -Pick the color first: $2$ choices. -Pick which number is on the ball: $6$ choices. There are then $2\cdot 6 = 12$ options. Yes, you can use fewer steps to solve, but in both scenarios you describe a unique outcome via each choice of results of steps. $\endgroup$ – JMoravitz May 3 '16 at 17:58
  • 1
    $\begingroup$ What aspect of the second solution does not make sense to you? $\endgroup$ – N. F. Taussig May 3 '16 at 18:46
  • $\begingroup$ The approach of counting some things in two different ways, and thereby proving a "surprise" identity, is known as a "combinatorial proof". He're you've counted the seatings in two ways, so $10! = \binom{10}{3} \cdot 3! \cdot 7!$. Thus you have a combinatorial proof of $\binom{10}{3} = \frac{10!}{3!7!}$. $\endgroup$ – hardmath May 3 '16 at 21:49
  • $\begingroup$ @N.F.Taussig the multiplication part. Its an easy question but as I am progressing I am seeing its done more deliberately in questions like poker hands. So, I need to understand how do we know we have to multiply the parts? $\endgroup$ – CodeYogi May 4 '16 at 2:30
  • $\begingroup$ The Multiplication Principle states that if a task can be done in $m$ ways and a second task can be done independently of the first in $n$ ways, there are $mn$ ways of doing both tasks. In this case, we first choose which children sit on the front benches, then we arrange them, then we arrange the remaining children on the back benches. I am too tired to give a detailed response now, but I will be happy to do so should you still need one when I wake. $\endgroup$ – N. F. Taussig May 4 '16 at 2:45
2
$\begingroup$

The rule of multiplicatinn is simple.   If there are $x$ ways to perform a subtask and $y$ ways to perform a second (independent) subtask, and the tasks are performed in serial then there are $xy$ ways to perform whole task.

Think of it as branching paths.   If the path branches into $x$ paths and then each of these branches into $y$, how many ways are they to take?

Similarly if you take a bushwalk which has $x$ paths to get from $A$ to $B$ and there are $y$ paths from $B$ to $C$, then how many different ways are there to go from $A$ to $B$ to $C$?

When independent subtasks are performed in serial then multipling the counts of subtasks obtains the count of the whole task.

[Serial: both tasks must be performed; Parallel: the tasks are alternatives.]


We write $3!$ as the count of ways to arrange three distinct items; and likewise $7!$ and $10!$ are the ways to arrange seven, or ten, distinct items, respectively.

Well, now we write $\binom {10}3~$, or sometimes $~^{10}\mathbb C_3$, to represent the count of ways to choose three from ten distinct things.

But what exactly is this $\binom {10}{3}$ notation?   How do we find its value?

You have examined two ways to count how to arrange ten children among ten seats; when the seats are in two rows; three and seven.

Because these are ways to perform the exact same task; the counts must be the same.

  • You have counted the ways to select three of ten children, then arrange them among three seats, and finally arrange the remaining children among seven seats.   This is: $~\binom{10}3\cdot 3!\cdot 7!$.

  • You have also counted the ways to simply arrange all ten children among all ten seats.   That is: $~10!~$.

Hence we find that: $\dbinom{10}3 = \dfrac{10!}{3!\,7!}$ .


In general we find that $\dbinom{n}{r} ~=~ \dfrac{n!}{r!~(n-r)!}$ for all non-negative integer $r,n$ such that $0\leq r\leq n$

You use verify this with smaller examples: What are $\binom 3 1$ and $\binom 4 2$ ?

$\endgroup$
  • $\begingroup$ My main concern is regarding the multiplication part and not about what is n choose k, but your explanation seems to help me a bit. Things done serially needs to multiplied. Like here we are performing actions in sequence and to get the final answer all the actions are necessary, we can't preform things in parallel like choosing 3 children and arranging them are not independent task and can't be done in the same time frame. Its like clock is ticking and we are doing something one after other to get the things done. Ah! the clock ticking things is making sense here :), right ? $\endgroup$ – CodeYogi May 4 '16 at 4:12
  • $\begingroup$ Serial subtasks are those performed at different time or space (ie: one after another, or by different people), but exactly all must be performed to complete the task. Parallel subtasks are those performed as alternatives--a choice is made somewhen--and only at least one of them must be completed to complete the task. $\endgroup$ – Graham Kemp May 4 '16 at 4:28
  • $\begingroup$ @CodeYogi The subtasks are considered independent. Certainly the first subtask must be completed before the second or third subtasks can begin, but the subtask's result doesn't affect the other subtasks' procedure. It does not matter which three children were selected by the first subtask, the second subtask is to arrange three distinct children, and the third subtask is to arrange seven distinct children. $\endgroup$ – Graham Kemp May 4 '16 at 4:34
  • $\begingroup$ So, can I visualize the product rule as tree? where each node represents the result of a choice? $\endgroup$ – CodeYogi May 13 '16 at 2:53
  • $\begingroup$ @CodeYogi Yes .. you are counting procedural pathways. $\endgroup$ – Graham Kemp May 13 '16 at 3:01
0
$\begingroup$

No matter if the bench is in the front row or in the back row, all 10 benches are distinctive. That's why the result is $10!$.

You can also think of it this way. We need to pick 3 kids to sit in the first 3 seats, and these 3 kids can be any 3 of the 10 kids. There are $\displaystyle \binom{10}{3}$ ways to do this. Then we don't have choice over who belongs in the other 7 benches, because there are only 7 other kids left.

For each option of which 3 kids sit in the front row, we have $7! \times 3!$ ways to seat the kids.

$\displaystyle \binom{10}{3}$ is the number of ways to group the 10 kids into a group of 3 and a group of 7. And $\displaystyle \binom{10}{3}$ would give the same result.

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