What is a combinatorial proof exactly? It almost seems as though a combinatorial proof is "Explain the intuition behind this relationship (using normal words) to explain why it is true." 
I'm a little lost as to how this is a proof exactly, since I always thought proofs were meant to be very rigorous. I can't think of a counter-example but it seems possible to come up with a combinatorial proof that sounds right but is actually wrong when you get down to the algebra.
Is my understanding correct? Are there any other conditions that a combinatorial proof must meet to be considered a valid proof?
 A: The essence  of a  combinatorial proof  is to provide a  bijection  between the elements of a known set and the elements of the set under consideration.

A nice characterization is given by R.P. Stanley in section 1.1 "How  to  Count" in his classic Enumerative Combinatorics volume 1:  
  
  
*
  
*In accordance with the principle from other branches of mathematics that it is better to exhibit an explicit isomorphism between two objects
  than merely prove that they are isomorphic, we adopt the general principle that it is better to exhibit an explicit one-to-one correspondence (bijection) between two  finite sets than merely to prove that they have the same number of elements.
A proof that shows that a certain set $S$ has a certain number $m$ of elements by constructing  an explicit bijection between $S$ and some other set that is known to have $m$ elements is called a combinatorial proof or bijective proof.

A: There are typically a few ways to prove a combinatorics question. One common way is to use algebra, where you reduce the given equation or relation using algebra to an identity. Another way is by block-walking where you prove the result using Pascal's triangle. Finally the third way is to use a committee-forming argument where you prove the result using the logic of a committee.
I get what you are saying about combinatorics proofs sometimes not being very rigorous since they seem informal. Sometimes a combinatorial identity can be proved just using words and without equations at all. But there is no one form of doing a combinatorics prove that is more valid than the other. 
A: There are many proofs that need not be rigorous but are right, like the proof for $ |A \cup B| = |A| + |B| - |A \cap B| $, or Bayes theorem. For a combinatorial proof, you need to define first a set S first and then count the it in two different ways and since they count the same set S so they are equal and such proofs are as good as any other rigorous proof.
Using combinatorial proof is usually a much better approach though to remember many identities like the hockey-stick identity or Vandermonde Identity.
