I&C SCI 6D Lecture Notes - Lecture 10: Bijection, Product Rule, Discrete Mathematics

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 6D
• Professor: Sandra Irani

Document Summary

Goal in discrete math is to count the cardinality of a finite set given a description of the set. Two basic rules of counting are the sum and product rule. Product rule - provides a way to count sequences. Many sets can be expressed as sets of sequences. If is a set of characters (called an alphabet) then n is the set of all strings of length n whose characters come from the set . Eg: if = {0,1}, then . 6 is the set of all binary strings with 6 bits. The product rule can be applied directly to determine the number of strings of a given length over a finite alphabet: The number of binary strings of length n is 2 n since the size of the alphabet ({0,1}) is 2. Product rule can also be used to determine the number of strings in a set when one or more of the characters are restricted.