CS241 Lecture Notes - Lecture 17: Planar Graph, Graph Theory, Product Rule
23 Sep 2015
School
Department
Course
Professor
Document Summary
This section of the course focuses on counting problems and the methodology behind solving them. For the most part, a set of con gurations s must rst be de ned with a corresponding weight function. The answer will then be the number of con gurations with a speci c weight k. Here are several theorems that are often used in the computation of generating series coe cients. It will be useful to memorize the following formulae. Theorem 1. 1. 1 for non-negative integers n and k, the number of k-element subsets of an n-element set is(cid:18)n (cid:19) k n(n 1) . (n k + 1) k! Theorem 1. 1. 2 (binomial theorem) for non-negative integers n, (cid:18)n (cid:19) n(cid:88) k k=0 (1 + x)n = xk. Theorem 1. 1. 3 (binomial theorem for negative numbers) for any positive integer n, A function f : s > t is a bijection if and only if it is one-to-one and onto.
