Question

In this problem, you are being asked to come up with an identity that can be proved combinatorially. Suppose that 2 srsn and that you are picking a committee of r people out of n people. The problem is that Jed and Fred are among the n people, and they refuse to be on the same committee since they have some sort of longstanding feud. Use two different counting arguments to count the number of ways to pick a committee of r people which don't contain both Jed and Fred to obtain a general identity involving n and r. (You may wish to read Example 9.5.6 in your text.) Your answer should consist of the identity and also an explanation of the counting argument you used to obtain each side of your identity.

Answer 1

The number of committees in which Jed is there but Fed is not there is
1
since Jed is always there but Fed is not there, we have to choose members from people

Similarly, the number of committees in which Fed is there, but not Jed is

1

And the number of committees in which neither are there is

2

Total number of committees is

1 2 2

Of course, without restriction we have $\binom{n}{r}$ committees but this includes the committees in which both Jed and Fred are there, which is in number

2

So that we must have

+ 2

That is,

n-2 7-1 7-2