PERMUTATION AND COMBINATION A combinatorial argument, or combinatorial proof, is an argument that involves counting. APPLICATION 1: Pascal’s Identity. For integers n and k, nCk = n−1Ck−1 + n−1 C k . Proof . The LHS counts the number of ways to select k out of n children to have their face painted. The RHS counts the same thing according to two cases: either a specific child of the n, say Gary, is in the group selected, or he is not selected. In the first case the remaining k−1 children in the group must be selected from the remaining n−1 children. The number of ways to do this is n−1 C k−1. In the second case all k children in the groupmust be selected from the remaining n − 1 children. The number of ways to do this is n−1 C k . By the Rule of Sum, the number of selections is n−1 C k−1+n−1 C k . Hence, the result.
Posted on: Thu, 12 Sep 2013 18:28:55 +0000
Trending Topics
Recently Viewed Topics
© 2015