Tuesday, June 19, 2018

combinatorics - Combinatorial Proof vs. Algebraic Proof



I'm learning combinatorics and need a little help differentiating between a combinatorial proof and an algebraic proof. Here is an example I came across:




Prove the following two formulas by combinatorial means and algebraic manipulation:



(i) For all $k$, $n \in \mathbb{N}$ with $k \leq n$.



${n \choose 2} + {n+1 \choose 2} = n^{2}$.



(ii) For all $k$, $n \in \mathbb{N}$ with $k \leq n$.



$k{n \choose k} = n{n-1 \choose k-1}$.



Answer



Algebraic manipulations consist of calculation using explicit formulas. In your two examples, we have:
$$
\binom{n}{2} + \binom{n+1}{2} = \frac{n(n-1) + (n+1)n}{2} = n^2,
$$

and
$$
k\binom{n}{k} = k\frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!} = n\frac{(n-1)!}{(k-1)!(n-k)!} = n\binom{n-1}{k-1}.
$$




Combinatorial proofs represent both sides of the equation as counting certain objects, and then exhibit a bijection between the two sides. In your two examples, we have:




  1. The left-hand side counts the size of two sets of ordered pairs: pairs of integers in $[n]$ (type A), and pairs of integers in $[n+1]$ (type B). The right-hand side counts the size of the set $[n]^2$. We exhibit a bijection between them in the following way:




    • A pair $i of type A is mapped to $(i,j)$.

    • A pair $i of type B with $j \neq n+1$ is mapped to $(j,i)$.

    • A pair $i of type B is mapped to $(i,i)$.





We can check that this is a bijection by giving the inverse mapping:




  • A pair $(i,j)$ with $i < j$ is mapped to the pair $i of type A.

  • A pair $(i,j)$ with $i > j$ is mapped to the pair $j of type B.

  • A pair $(i,i)$ is mapped to the pair $i of type B.




The second example is of a somewhat different kind.




  1. The left-hand side counts the number of $k$-element subsets of $[n]$ with a distinguished element. The right-hand side offers another way of counting the same set: first choose the distinguished element, and then choose the remaining $k-1$ elements out of the remaining $n-1$ elements. This is an example of double counting.



Another kind of proof which sometimes appears is probabilistic proofs, which are really a variant of combinatorial proofs. As an example,
$$ \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} = 1 $$
expresses the fact that if we toss $n$ many $p$-biased coins, then $k$ of them will turn up heads for exactly one value of $k$. (While this works only for $0 \leq p \leq 1$, the general result follows since two degree $n$ polynomials are equal whenever they agree on more than $n$ points.)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...