# DARTMOUTH COSC 030 - 05sumproduct (6 pages)

Previewing pages 1, 2 of 6 page document
View Full Document

## 05sumproduct

Previewing pages 1, 2 of actual document.

View Full Document
View Full Document

## 05sumproduct

57 views

Pages:
6
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
##### Discrete Math Computer Sci Documents
• 4 pages

• 4 pages

• 5 pages

• 3 pages

• 2 pages

• 9 pages

• 5 pages

• 10 pages

Unformatted text preview:

Counting Problems CS 30 Discrete Mathematics Amit Chakrabarti Basic Counting Principles Sum Principle Basic sum principle If A and B are disjoint A B A B Extended sum principle If A1 A2 Ak are pairwise disjoint A1 A2 Ak A1 A2 Ak How many people are signed up on this course s canvas page Students Staff Students 37 Staff 7 Answer 37 7 44 Extended Sum Principle Application Exchange sort algorithm pseudocode for i 1 to n 1 for j i 1 to n if A i A j exchange A i and A j How fast is this How many comparisons SimpliRication record comparison A i A j as pair i j Extended Sum Principle Application How many pairs i j occur below for i 1 to n 1 for j i 1 to n S1 1 2 1 3 1 4 1 n S2 2 3 2 4 2 n Sn 1 n 1 n S1 n 1 S2 n 2 Sn 1 1 Total S1 S2 Sn 1 n 1 n 2 1 n n 1 2 Sum Principle Basic sum principle If A and B are disjoint A B A B Extended sum principle If A1 A2 Ak are pairwise disjoint A1 A2 Ak A1 A2 Ak Generalized sum principle For all A and B A B A B A B General Non Disjoint Unions S set of all current Dartmouth students A s S s has registered for CS 30 B s S s has registered for CS 75 C s S s registered for CS 30 or CS 75 A 37 B 25 C A B 37 25 What if I told you A B 3 Another Counting Problem Dartmouth invited to send a delegation of one student and one professor to the International Awesomeness Convention How many ways to choose Students Professors Students 4500 Professors 650 Product Principle Basic product principle For all A and B A B A B Extended product principle For all A1 A2 Ak A1 A2 Ak A1 A2 Ak Counting Telephone Numbers Rules Let X denote a digit from 0 through 9 Let N denote a digit from 2 through 9 Let Y denote a digit that is 0 or 1 In the old plan in use in the 1960s the format was NYX NNX XXXX In the new plan the format is NXX NXX XXXX Solution Use the product principle There are 8 2 10 160 area codes with the format NYX 8 10 10 800 area codes with the format NXX 8 8 10 640 ofRice codes with the format NNX 10 10 10 10 10 000 station codes with the format XXXX Old plan 160 640 10 000 1 024 000 000 telephone numbers New plan 800 800 10 000 6 400 000 000 telephone numbers Counting Telephone Numbers The North American numbering plan NANP says a telephone number has a 3 digit area code a 3 digit ofRice code and a 4 digit station code There are some restrictions on the digits Let X denote a digit from 0 through 9 Let N denote a digit from 2 through 9 Let Y denote a digit that is 0 or 1 In the old plan 1960s the format was NYX NNX XXXX In the new plan the format is NXX NXX XXXX How many different telephone numbers are possible under the old plan Under the new plan Counting Variable Names in Minimal BASIC Rules At most two characters Each character is either an uppercase letter or a digit The Rirst character cannot be a digit Solution V1 v v is a one character variable name V2 w w is a two character variable name x x is a letter y y is a letter or a digit V1 V2 names V1 V2 V1 V2 26 26 36 962 Bijection Principle Bit Strings For Rinite sets If there exists a bijection f A B then A B We ve seen this before V2 w w is a two character variable name L letters D digits We said V2 L L D Actually there is a natural bijection from V2 to L L D AA A A AB A B FX F X J2 J 2 etc A 3 bit string is a sequence of 3 bits 000 001 010 011 100 101 110 111 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Elements of 0 1 0 1 0 1 0 1 3 An n bit string is a sequence of n bits 00 000 00 001 00 010 11 111 Elements of 0 1 0 1 0 1 n Problem How many n bit strings in all Use product principle answer 0 1 n 2n Counting the Power Set Problem Determine P S in terms of S Assume S Rinite Let n S List all elements S e1 e2 en We ll deRine a bijection f P S 0 1 n as follows for A P S let f A b1 b2 bn where for each i bi 1 if ei A and bi 0 if ei A Why bijection Because this f has an inverse f 1 b1 b2 bn ei S bi 1 Bijection principle P S 0 1 n 2n Super important Subsets of Size 2 Let T 1 2 n Let U A T A 2 What is U 1 1 2 1 3 1 n 1 1 2 1 3 1 4 1 n 2 2 2 3 2 4 2 n 3 2 3 3 3 4 3 n n 2 n 3 n 4 n n How many pairs above Can t quite use product principle Not what we wanted to count anyway Generalized Product Principle Subsets of Size 2 Solution Need to make a sequence of k choices a1 a2 ak n1 ways to choose a1 for each a1 there are n2 ways to choose a2 for each a1 a2 there are n3 ways to choose a3 for each a1 a2 ak 1 there are nk ways to choose ak Let T 1 2 n Let U A T A 2 What is U Then there are n1n2n3 nk ways to choose the sequence Generalized product principle pairs n n 1 2 pairs for every subset A in U so U n n 1 2 k to 1 Correspondence A function f A B such that b B a f a b k 1 2 x 3 4 y 5 6 This function is a 3 to 1 correspondence 1 1 2 1 3 1 n 1 1 2 1 3 1 4 1 n 2 2 2 3 2 4 2 n 3 2 3 3 3 4 3 n n 2 n 3 n 4 n n Division Principle If A and B are Rinite sets and a k to 1 correspondence f A B then B A k Problem T 1 2 n Let U A T A 2 What is U Solution Let P i j T T i j P 1 2 1 3 1 4 …

View Full Document

Unlocking...