How do you do a combinatorial proof?

  • Thread starter saint_n
  • Start date
  • Tags
    Proof
In summary, combinatorial proofs involve counting the number of ways to select objects from a given set and finding alternative methods of counting them. One method is to look at coefficients in the expansion of (x+y)^n, while another involves creating an experiment with two different ways of selecting and ordering objects. These proofs require precise definitions and critical thinking.
  • #1
saint_n
31
0
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
 
Mathematics news on Phys.org
  • #2
you count. that's all it means.
 
  • #3
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
 
  • #4
(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?
 
  • #5
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.
 
  • #6
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.
 
  • #7
There is no "general" way of doing any kind of proofs. They require knowing the precise definition of all terms and THINKING.
 
  • #8
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
 

Q1: What is a combinatorial proof?

A combinatorial proof is a mathematical proof technique that uses counting and combinatorial arguments to prove the validity of a statement. It involves breaking down a problem into smaller, easier-to-solve subproblems and then using counting principles to show that the two sides of the equation are equal.

Q2: Why is a combinatorial proof useful?

Combinatorial proofs can often provide a more intuitive and visual understanding of a mathematical statement, making it easier to grasp and remember. They also allow for alternative and creative solutions to problems, and can be applied in various mathematical fields such as probability, algebra, and graph theory.

Q3: How do you do a combinatorial proof?

1. Define the problem: Clearly state the equation or statement that needs to be proven.2. Identify the objects involved: Determine the objects or elements that are being counted in the problem.3. Determine the counting method: Decide which counting principle or method will be used to count the objects.4. Set up the equation: Write out the equation or statement that relates the two sides of the problem.5. Prove the equality: Use combinatorial arguments, such as counting the same objects in two different ways, to show that both sides of the equation are equal.

Q4: What are some common counting principles used in combinatorial proofs?

Some common counting principles include the multiplication principle, addition principle, and the principle of inclusion-exclusion. Other techniques, such as bijections and generating functions, can also be used in combinatorial proofs.

Q5: Are there any tips for mastering combinatorial proofs?

Practice is key when it comes to mastering combinatorial proofs. Make sure to fully understand the counting principles and techniques before attempting to solve problems. It may also be helpful to break down the problem into smaller, easier subproblems and to draw diagrams or use visual aids to better understand the problem. Additionally, seeking out and analyzing examples of combinatorial proofs can also improve one's understanding of the concept.

Similar threads

  • General Math
Replies
6
Views
1K
  • General Math
Replies
4
Views
805
Changing the Statement Combinatorial proofs & Contraposition
  • Math Proof Training and Practice
Replies
5
Views
782
Replies
13
Views
776
  • Math Proof Training and Practice
Replies
5
Views
920
  • General Math
Replies
6
Views
2K
  • General Math
Replies
1
Views
220
Replies
4
Views
925
Replies
3
Views
778
  • General Math
Replies
13
Views
1K
Back
Top