-1
$\begingroup$

Consider the identity: $k(k-1)C(n,k)$=$n(n-1)C(n-2,k-2)$

A- verify the identity for n=10, k=5

B- give an algebraic proof of the identity

C- give a combinatorial proof of the identity.

Can someone help me with this problem. I'm not sure if we plug in exactly the n number and k number into the formula for part A.

$\endgroup$

closed as off-topic by Namaste, Brevan Ellefsen, Magdiragdag, Shailesh, darij grinberg Apr 25 '17 at 8:17

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Brevan Ellefsen, Magdiragdag, Shailesh, darij grinberg
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

For part (a), just plug in and verify. For part (b), I suspect this should be straightforward by just expanding out the combination notation in terms of factorials and cancelling some stuff.

For part (c), consider the problem where out of a group of $n$ people, we need to form a committee of $k$ people with one person being the chair of the committee and another (distinct) person being the vice chair. One way to do this is to first form the committee which can be done in $C(n,k)$ ways, then pick the chair from within the committee ($k$ ways), then pick the vice chair from the remainder of the committee ($k-1$ ways). By the multiplication principle, there are $k(k-1)C(n,k)$ ways to pick everything.

Alternatively, we could first pick the chair from the $n$ people ($n$ ways), pick the vice chair from the remaining people ($n-1$ ways), then form the other $k-2$ members of the committee from the remaining $n-2$ people ($C(n-2,k-2)$ ways). By the multiplication principle, there are $n(n-1)C(n-2,k-2)$ ways to pick everything.

Since the number of ways to form the committee and the chair/vice-chair is the same in both cases, it must be that $k(k-1)C(n,k)=n(n-1)C(n-2,k-2)$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the explanation. $\endgroup$ – Zaid Apr 8 '17 at 2:31
  • $\begingroup$ No problem, in general, the proof technique is called double counting (see en.m.wikipedia.org/wiki/Double_counting_(proof_technique) ). The idea is that we can show two expressions are equal by showing that they are both ways of describing the size of some set or the number of ways to count something. $\endgroup$ – benguin Apr 8 '17 at 2:35
  • $\begingroup$ I've got 5040 for part A for both cases, so how do you start with part B again? $\endgroup$ – Zaid Apr 8 '17 at 2:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.