1
$\begingroup$

There are n >= 4 students. The school has a Board of Directors, consisting of one president and three vice-presidents. The entire board consists of four distinct students. How can I prove that $$n\binom{n-1}{3} = (n-3)(\binom{n}{3})$$ by couting in two different ways, the number of ways to choose a board of director?

I know that out of 4 student there is 4 way to choose a president because anyone of the students can be choosen, which leave 3 students and out of those three student there is only 1 way of choosing a vice-president because the board consit of three vice-president. I can see that the equation also equals to 4=4 but how do i prove it by counting in two different ways?

$\endgroup$

2 Answers 2

1
$\begingroup$

First choose the vice presidents. There are $n$ selections for the first choice, $n-1$ for the second, and $n-2$ for the third. Since these are all taken in sequence, we multiply these numbers. Since the order of the group of three that we choose doesn't matter (there isn't a first-place vice president, second-place vice president, third-place vice president, in other words), we then cut out the number of ways we can arrange the group of three of our choice, leaving us $$\frac{n(n-1)(n-2)}{3*2*1}=\frac{n!}{(n-3)!3!}=\binom{n}{3}$$ ways to choose three vice presidents.

There are now $n-3$ people remaining, from which we must now choose a president. Putting this all together, we have $$(n-3)\binom{n}{3}=\frac{n(n-1)(n-2)(n-3)}{3*2*1}$$ ways to choose one president and three vice presidents.

Reverse the order in which you choose, i.e. now choose one president first, meaning $n$ choices, then from the group of $n-1$ remaining, make three choices (again, the order doesn't matter for the choices since the vice presidents are not distinguished from one another). You then have $$(n)\binom{n-1}{3}=n*\frac{(n-1)!}{(n-3-1)!3!}$$ ways to choose a president followed by three vice presidents. I will leave the final details to you to show that the above equation is equal to our first total.

$\endgroup$
0
1
$\begingroup$

Both sides of the equation are equal to the number of ways you can select a President and Vice Presidents as described.

For the left side, if you choose one of the students to be president first, there are $n$ possibilities. After this, you must choose 3 students from the remaining $n-1$ to be vice presidents, which gives $\binom{n-1}{3}$ possibilities. All up this gives

$$n\binom{n-1}{3}$$

ways of choosing a President and Vice Presidents.

For the right side, if you choose the three vice presidents first, from the $n$ students, there are $\binom{n}{3}$ ways of doing this. Then all that remains is to choose the president from the remaining $n-3$ students, for which there are $n-3$ possibilities. In total, this gives

$$(n-3)\binom{n}{3}$$

ways once again, of choosing a President and Vice Presidents.

Therefore $$n\binom{n-1}{3}=(n-3)\binom{n}{3}.$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .