How do you do a combinatorial proof?

[saint_n]

How do you do a combinatorial proof?

hey ppl!

Im having a hard time trying to do a combinatorial proof!
How do you start?
WHat do you look at??
A general method would really help!
Thanx
SAint_n

 

[matt grime]

you count. that's all it means.

 

[saint_n]

I still don't get how you do that... eg summation from k=0 to n (n k) {k is underneath n so basically its choosing k from n} = 2^n

 

[matt grime]

(n k) is the binomial coefficient? so you're summing from 0 to n the number of ways of picking k objects from n. What else do you know that sum as? what's (x+y)^n? enumeration of power sets, there's two proofs for you to start on.

there is no method for doing combinatorial questions, that's often why they are so hard and interesting.

the flavour of them is to think how you're counting things, what are you counting, and is there another way of doing it?

 

[Gokul43201]

You can look at the problem in terms of coefficients in the expansion of (x+y)^n, as Matt suggests. Another technique I like to use - and this requires thinking about how and what you are counting - is to find an experiment that involves selecting (and ordering) objects which can be looked at in two different ways.

In this case, you ask yourself how many ways there are of picking 'any' number of objects out of the given set of n objects. One way, is to find the no. of ways of picking zero objects + the number of ways of picking 1 object + ...+ the no. of ways of picking all n objects. So that covers all cases, and is exactly the LHS of the equation you want to prove. The other way of do this same thing is to look at each object and decide whether to pick it or not. This way, you are assigning 2 values to each of the n objects. The total number of ways of doing such an assignment is your RHS.

This kind of approach is probably just what Matt was talking about. The above example should give you somewhere to start from.

 

[Caldus]

Here is an example:

If there are 26 people in a committee and if the president and vice president have to be part of the committee, then how many ways can you choose 8 people to be part of this committee?

The answer is that since 2 people are already part of the committee, then there has to be (24 6) ways to form the rest of the committee. Notice something here: Order does not matter. The objects that are being chosen (people) are not distinct (other then the president and vice president). Combinatorial problems like these involve manipulating n objects taken k at a time. Permutations involve order. In this problem, order does not matter for choosing the other 6 people. So what I said above is pretty much a proof itself (maybe not a formal one, but I am pretty sure it is one nonetheless). Hope this helps.

 

[HallsofIvy]

There is no "general" way of doing any kind of proofs. They require knowing the precise definition of all terms and THINKING.

 

[saint_n]

helps a bit so i wil just try some more of the exercises and see how it gows
thanx..will ask if i need more help
Saint