Combinatorial proofs & Contraposition

[CGandC]

I have a question regarding to combinatorial proofs and predicate logic. It seems to me that in some combinatorial proofs there is a use of contraposition ( although not explicitly stated in the books where I've read so far ), for example If we to prove that $C(n,k) = C(n,n-k)$ combinatorically, the explanation is:

" (1) we have $C(n,k)$ ways to create k subsets
(2) we have $C(n,n-k)$ ways to not create k subsets
And since both ways of counting are equivalent, we finished. "

However, why these two statements ( statements (1) and (2) ) are equivalent? is it because "$C(n,n-k)$ ways to not create k subsets" is the contrapositive of " $C(n,k)$ ways to create k subsets " ?
But how do you even find the contrapositive of a sentence like " $C(n,k)$ ways to create k subsets "? ( it doesn't seem like an implication to me )

 

[fresh_42]

The easiest way is probably to show that the formulas are identical.

The way the argument above uses is: Whenever I choose $k$ elements out of $n$, then I have simultaneously chosen $n-k$ elements, which do not belong to the set. Hence if I pick $k$ or $n-k$ elements does not matter.

I simply label the resulting bowls of $C(k,n)$ as chosen and not chosen. Of course, I can exchange the labels that I have put on my selections afterwards anyway without even repeating the process. So both results depend on a sign I used to mark them, not the process of selection. But that was deliberate.

 

[martinbn]

$C(n,k)$ is the number of ways to choose $k$ elements out of $n$. That is the same as to choose $n-k$, because whether you choose $k$ and leave $n-k$ behind or you choose $n-k$ and leave $k$ behind is the same.

 

[CGandC]

In terms of predicate and quantificational logic, is" $C(n,k)$ ways to create k subsets" can be considered as a predicate? does it have a True/False value? I'm having hard time to interpret the logic behind this phrase and what to classify it as ( maybe there's advanced logic behind that's discussed in a course about Logic ).

 

[fresh_42]

I tried to write it with logical symbols, but it is quite a bit troublesome for such an obvious result. One has to define subsets with $k$ elements and make a statement about the size of the set of such sets, and sets of sets is always a bit clumsy.

Why don't you think of partitioning a set of $n$ elements into two sets, one with $k$ the other one with $n-k$ elements. This demonstrates the symmetry in the argument.

 

[CGandC]

Ok I understand, thanks. I tried looking at combinatorial proofs as statements with quantifiers and such like when I was learning predicate and quantificational logic. But I think I'll have to exercise such proofs to get an idea of what's going on.