Please help me at least get started

[zhupolongjoe]

Supppose you have a club of 10 people, and want to make up a committee of 4 of them. How many different ways are there to make up the committee? Consider a smaller example - suppose we want to make up a committee of 2 people out of a club of 4. Let's call the 4 people Ann, Bob, Charley, and Dale. Let's consider two groups of committees: those that don't have Ann as a member and those that do.

If a two person committee does not have Ann as a member, we are faced with choosing the whole committee of 2 out of the remaining 3 people, which can be done in 3 ways:

Bob, Charley

Bob, Dale

Charley, Dale

If the two person committee does include Ann we have to choose the other member of committee from Bob, Charley, and Dale, i.e. one person out of three. This gives us three committees:

Ann, Charley

Ann, Bob

Ann, Dale

Since each of these incudes Ann, and the first set does not, no committee can be in both lists.

So the number of ways to choose 2 people out of 4 is the number of ways to choose 2 out of 3 (that is, 4-1) plus the number of ways to choose 1 (that is, 2-1) out of 3 (that is, 4-1).

Similarly the number of ways to choose 4 out of 10 is the number of ways to choose 4 out of 10 - 1 (84 ways) plus the number of ways to choose 4-1 out of 10-1 (126 ways), giving 84+126 = 210 ways to choose 4 out of 10.

 

There are two simpler cases: there is only one way to choose n out of n, e.g. 3 out of 3, and there are n ways to choose 1 out of n. e.g. 3 ways to choose 1 out of 3.

 

Write a function ways(t, c) that calculates the number of ways we can choose c people out of a total of t, Your function must be recursive, using the relationship above.

 

 

I have no idea what I'm doing, please help!

[sasa]

1. check that imput is regular c cant be > t (if c > t return 0)

2. solve one specijal case for c=1 (if c=1 return ...)

3. do recursion:

    calculate ways that don't have Ann total is one less, and c is same (ways(c,t-1))

    calcolaate ways with Ann (ways(c-1,t-1))

    sum and return