CS349 Study Guide - Final Guide: Bijection, Binary Tree, Weight Function
Document Summary
The rst half of the math 239 course, which is the one that accounts for most of the material in the midterm, is the one about enumeration problems. We will speak about sets of con gurations, each of them with an associated non-negative weight. In our problems, we will want to know how many con gurations are there of an speci c weight. For any real number a and non-negative integer k, we de ne a choose k, denoted (cid:0)a k(cid:1), as a(a 1) . (a k + 1) k(k 1) . If a is equal to an integer n, then (cid:0)n of a set of size n: k(cid:1) is the number of subsets of size k. However, there are k (k 1) (k 2) . 1 ways to permute each list of k elements (by choosing the rst element, then the second element, and so on).