Main Applications Identities History FAQ Algorithms

Combinatorial proof of symmetry rule

    While the idea of symmetry of Pascal's Triangle is pretty obvious when you look at the factorial fractional formula,  , it can also be made clear by the idea of "n choose k".

    If I choose to take k things out of a set of n things, I have simultaneously chosen to leave n-k things behind; every different way to choose k things corresponds directly to a different way to leave n-k things behind, so the number of ways defined by "n choose k" must be the same as "n choose (n-k)".

    Likewise, if we think of a bit pattern of n bits, any way of having k bits = 1 and (n-k) bits = 0 corresponds directly to the complementary pattern, where every 1 becomes a 0 and every 0 becomes a 1; since "n choose k" also gives us the number of bit patterns of length n with k bits = 0 and (n-k) bits = 1.