Transcript Document

461191 Discrete Math
Lecture 5: Counting
San Ratanasanya
CS, KMUTNB
Today’s topics





Review of Induction and Recursion
Administrivia
Basics of Counting
Prolog Tutorial
Python Tutorial
2
Induction





Based on the Rule of Inference (or Well-Ordering)
It has two steps: basis step and inductive step
If P(1) and k(P(k)  P(k+1)) are true for positive
integers then P(n) is true
Can be used to prove tremendous variety of results
Strong induction is more flexible proof technique. It
shows [P(1)P(2)  …  P(k)]  P(k+1) is true in the
inductive step instead of just showing only P(k) 
P(k+1) as in mathematical induction
3
Example
Prove this theorem: “All horse are the same color”
Proof:
Basis Step: no horse  vacuously true!
Inductive Step: assume k horse have the same color (inductive hypothesis) is true.
Then we have to show that k+1 horse also have the same color.
Second set of k horse having the same color
First set of k horse having the same color
k+1 horse having the same color
4
Example
“For any 2n x 2n board, we can chase Bill to the corner.”
Proof:
Basis Step: no board (n=0), no need to need to chase Bill with an L-shape tile.
Inductive Step: assume we can get Bill to the corner for 2n x 2n board.
We need to show it is true for 2n+1 x 2n+1
We are done!
5
Recursion




Another way to define function based on
induction
Specifies some initial terms and define
rules for finding subsequent values from
values already known – Recursive Definition
Use induction to prove recursive definition
Algorithms can also be recursively designed
6
Example
n
Give a recursive definition of  ai
i 0
0
a
i 0
i
 a0  0,
 n 
ai    ai   an 1

i 0
 i 0 
n 1
7
Program Verification



A method to verify that a designed procedure or program
always produce the correct answer
The verification is based on rules of inference
Initial assertion and Final assertion



properties that the input must have
The properties that output should have
Partial correctness vs. Total correctness


The correct answer is obtained if program terminates
The program always terminated
8
Example
procedure multiply (m, n: integers)
if n < 0 then a := -n
else a := n
k := 0
x := 0
Prove that this program is correct.
S1
S2
while k < a
begin
x := x + m
k := k + 1
end
if n < 0 then product := -x
else product := x
S3
S4
Let p: “m and n are integers” and q: p  (a=|n|). Then we can prove that p{S1}q is true.
Let r: q  (k=0)  (x=0). Then it can be proved that q{S2}r is true.
S4 can be proved in the same way as S1. Now, we have to show S3 is correct.
First, we find “loop invariant” in S3 which is s: “x=mk  k  a” or “x=ma  a=|n|”. If r is true,
we know that s is true before entering the loop. Moreover, this loop terminates when k = a and
x = ma. That is partial correctness is held. It follows that r{S3}s is true.
Now that we prove S1, S2, S3, and S4 are true so, by composition rule we could show that
[p{S1}q  q{S2}r  r{S3}s  t{S4}u]  p{S1;S2;S3;S4}u is true. p{S}u is correct.
9
Administrivia


Midterm Exam is in next 3 weeks. Please be
prepared!
All assignments MUST be submitted before
Midterm.
10
Basics of Counting
The Importance of Counting



To count the number of solutions to solve
the problem
Determine the Complexity of Algorithms
To Use Passwords for Computer Security
12
Combinatorics

Count the number of ways to put things
together into various combinations


e.g., If a password is 6-8 letters and/or digits,
how many passwords can there be?
Two main rules


Sum
Product
13
Sum Rule

Let us consider two tasks:



m is the number of ways to do task 1
n is the number of ways to do task 2
Tasks are independent of each other, i.e.,



Performing task 1 does not accomplish task 2 and
vice versa.
Sum rule: the number of ways that “either
task 1 or task 2 can be done, but not both”,
is m + n.
Generalizes to multiple tasks ...
14
Example

A student can choose a computer project from one of
three lists. The three lists contain 23, 15, and 19 possible
projects respectively. How many possible projects are
there to choose from?
15
Set Theoretic Version

If A is the set of ways to do task 1, and B
the set of ways to do task 2, and if A and B
are disjoint, then:
“the ways to do either task 1 or 2 are
AB, and |AB|=|A|+|B|”
16
Product Rule

Let us consider two tasks:



m is the number of ways to do task 1
n is the number of ways to do task 2
Tasks are independent of each other, i.e.,



Performing task 1does not accomplish task 2 and
vice versa.
Product rule: the number of ways that
“both tasks 1 and 2 can be done” in mn.
Generalizes to multiple tasks ...
17
Example

The chairs of an auditorium are to be labeled with a letter
and a positive integer not to exceed 100. What is the
largest number of chairs that can be labeled differently?
18
Set Theoretic Version


If A is the set of ways to do task 1, and B
the set of ways to do task 2, and if A and B
are disjoint, then:
The ways to do both task 1 and 2 can be
represented as AB, and |AB|=|A|·|B|
19
More Examples


How many different bit strings are there of
length seven?
Suppose that either a member of the CS
faculty or a student who is a CS major can
be on a university committee. How many
different choices are there if there are 37
CS faculty and 83 CS majors ?
20
More Examples

How many different license plates are
available if each plate contains a sequence
of three letters followed by three digits?

What is the number of different subsets of
a finite set S ?
21
Example Using Both Rules

Each user on a computer system has a password, which is
six to eight characters long where each character is an
uppercase letter or a digit. Each password must contain at
least one digit. How many possible passwords are there?
22
IP Address Example
(Internet Protocol vers. 4)

Main computer addresses are in one of 3 types:

Class A: address contains a 7-bit “netid” ≠ 17, and a 24-bit “hostid”
Class B: address has a 14-bit netid and a 16-bit hostid.
Class C: address has 21-bit netid and an 8-bit hostid.

Hostids that are all 0s or all 1s are not allowed.



How many valid computer addresses are there?
23
Example Using Both Rules:
IP address solution

(# addrs)
= (# class A) + (# class B) + (# class C)
(by sum rule)

# class A = (# valid netids)·(# valid hostids)
(by product rule)



(# valid class A netids) = 27 − 1 = 127.
(# valid class A hostids) = 224 − 2 = 16,777,214.
Continuing in this fashion we find the answer is:
3,737,091,842 (3.7 billion IP addresses)
24
Inclusion-Exclusion Principle
(relates to the “sum rule”)



Suppose that km of the ways of doing task
1 also simultaneously accomplishes task 2.
(And thus are also ways of doing task 2.)
Then the number of ways to accomplish
“Do either task 1 or task 2” is mnk.
Set theory: If A and B are not disjoint, then
|AB|=|A||B||AB|.
25
Example

How many strings of length eight either
start with a 1 bit or end with the two bit
string 00?
26
More Examples

Hypothetical rules for passwords:



Passwords must be 2 characters long.
Each password must be a letter a-z, a digit 0-9,
or one of the 10 punctuation characters
!@#$%^&*().
Each password must contain at least 1 digit or
punctuation character.
27
Sol. Cont’d

A legal password has a digit or puctuation
character in position 1 or position 2.





These cases overlap, so the principle applies.
(# of passwords w. OK symbol in
position #1) = (10+10)·(10+10+26)
(# w. OK sym. in pos. #2): also 20·46
(# w. OK sym both places): 20·20
Answer: 920+920−400 = 1,440
28
Tree Diagrams
29
Pigeonhole Principle


If k+1 objects are assigned to k places,
then at least 1 place must be assigned ≥2
objects.
In terms of the assignment function:
If f:A→B and |A|≥|B|+1, then some element of
B has ≥2 pre-images under f.
i.e., f is not one-to-one.
30
Example

How many students must be in class to guarantee that at
least two students receive the same score on the final
exam, if the exam is graded on a scale from 0 to 100
points?
31
Generalized Pigeonhole Principle


If N≥k+1 objects are assigned to k places,
then at least one place must be assigned at
least N/k objects.
e.g., there are N=280 students in this class.
There are k=52 weeks in the year.

Therefore, there must be at least 1 week
during which at least 280/52= 5.38=6
students in the class have a birthday.
32
Proof of G.P.P.


By contradiction. Suppose every place has
< N/k objects, thus ≤ N/k−1.
Then the total number of objects is at most
N  
 N  
N
k     1  k    1  1  k    N
 
k
 k  
 k

So, there are less than N objects, which
contradicts our assumption of N objects!
□
33
G.P.P. Example


Given: There are 280 students in the class.
Without knowing anybody’s birthday, what
is the largest value of n for which we can
prove that at least n students must have
been born in the same month?
Answer:
280/12 = 23.3 = 24
34
More Examples

What is the minimum number of students required in a
discrete math class to be sure that at least six will receive
the same grade, if there are five possible grades, A, B, C,
D, and F?
35
Binomial Coefficients


The number of r-combinations from a set with n
elements is denoted by  n  also called binomial
r 
coefficient.
This number is the expansion of powers of
binomial expressions such as (a + b)n
36
Binomial Coefficients
THEOREM 1: The Binomial Theorem
Let x,y,n be positive integer
THEOREM 2: PASCAL’S IDENTITY
Let n and k be positive integer with n > k then
THEOREM 3: Let n be positive integer, then

More details in Section 5.4
37
Examples

(x + y)4 = ?
 4  4 j j
   x y
j 0  j 
4 4 4 3
4 2 2 4 3 4 4
   x    x y    x y    x y    y
 j
 j
 j
 j
 j
 x 4  4 x3 y  6 x 2 y 2  4 x y 3  y 4
4

What is the coefficent of x12y13 in the expansion
of (x + y)25?
 25 
25!
  
 5,200,300
13  12!13!
38
Permutations



A permutation of a set S of objects is an ordered
arrangement of the elements of S where each
element appears only once:
e.g., 1 2 3, 2 1 3, 3 1 2
An ordered arrangement of r distinct elements of
S is called an r-permutation.
The number of r-permutations of a set S with
n=|S| elements is
P(n,r) = n(n−1)…(n−r+1) = n!/(n−r)!
39
Example

How many ways are there to select a thirdprize winner from 100 different people
who have entered a contest?
40
More Examples




A terrorist has planted an armed nuclear bomb in
your city, and it is your job to disable it by cutting
wires to the trigger device.
There are 10 wires to the device.
If you cut exactly the right three wires, in exactly
the right order, you will disable the bomb,
otherwise it will explode!
If the wires all look the same, what are your
chances of survival?
41
More Examples

How many permutations of the letters
ABCDEFG contain the string ABC?
42
Combinations


The number of ways of choosing r elements
from S (order does not matter).
S={1,2,3}
e.g., 1 2 , 1 3, 2 3
The number of r-combinations C(n,r) of a set
with n=|S| elements is
n
n!
C (n, r )    
 r  r !(n  r )!
43
Combinations vs Permutations

Essentially unordered permutations …
P(n, r )  C (n, r ) P(r , r )
 n  P(n, r ) n! /( n  r )!
n!
C (n, r )    


r!
r!(n  r )!
 r  P(r , r )

Note that C(n,r) = C(n, n−r)
44
Combination Example

How many distinct 7-card hands can be
drawn from a standard 52-card deck?


The order of cards in a hand doesn’t matter.
Answer C(52,7) = P(52,7)/P(7,7)
= 52·51·50·49·48·47·46 / 7·6·5·4·3·2·1
17
10
7
8
2
52·17·10·7·47·46 = 133,784,560
45
More Examples

How many ways are there to select a committee to
develop a discrete mathematics course if the committee is
to consist of 3 faculty members from the Math
department and 4 from the CS department, if there are 9
faculty members from Math and 11 from CS?
46
Generalized
Permutations and Combinations



How to solve counting problems where
elements may be used more than once?
How to solve counting problems in which
some elements are not distinguishable?
How to solve problems involving counting
the ways we to place distinguishable
elements in distinguishable boxes?
47
Permutations with Repetition


The number of r-permutations of a set of n objects
with repetition allowed is n r
Example: How many strings of length n can be
formed from the English alphabet?
48
Combinations with Repetition

The number of r-combinations from a set with n
elements when repetition of elements is allowed
are C(n+r-1,r)
49
Combinations with Repetition
Example: How many ways are there to select 5 bills from a cash box
containing $1 bills, $2 bills, $5 bills, $10 bills, $20 bills, $50 bills, and
$100 bills? Assume that the order in which bills are chosen does not
matter and there are at least 5 bills of each type.
50
Combinations with Repetition
Approach: Place five markers in the compartments
i.e., # ways to arrange five stars and six bars ...
Solution: Select the positions of the 5 stars from 11 possible positions !
C(n+r-1,5)= C(7+5-1,5)=C(11,5)
n=7
r=5
compartments
and
dividers
markers
51
Combinations with Repetition

Example: How many ways are there to place 10
non-distinguishable balls into 8 distinguishable
bins?
52
Permutations and Combinations
with and without Repetition
53
Permutations with
non-distinguishable objects

The number of different permutations of n
objects, where there are n1 non-distinguishable
objects of type 1, n2 non-distinguishable objects
of type 2, …, and nk non-distinguishable objects
of type k, is
n!
n1 !n2 !...nk !
i.e., C(n,n1 )C(n - n1 ,n2)…C(n - n1 - n2 -…- nk 1 ,nk )
n1  n2  ...  nk  n
54
Permutations with
non-distinguishable objects

Example: How many different strings can be
made by reordering the letters of the word
SUCCESS
55
Distributing Distinguishable
Objects into Distinguishable Boxes

The number of ways to distribute n
distinguishable objects into k distinguishable
boxes so that ni objects are placed into box i,
i=1,2,…,k, equals
n!
n1 !n2 !...nk !
56
Distributing Distinguishable
Objects into Distinguishable Boxes

Example: How many ways are there to distribute
hands of 5 cards to each of 4 players from the
standard deck of 52 cards?
57
Generating
Permutations and Combinations

Often, we have to generate permutations
or combinations to determine the solution

A salesman must visit 6 different cities. In
which order should these cities be visited to
minimize total travel time?


generate 6! = 720 possibilities
Find a subset of 6 integers that has their sum
equals 100

possible subset is 26 = 64 subsets
58
Generating Permutations

Any set with n elements can be place in
one-to-one correspondence with the set {1,
2, 3, …, n}


Generate permutation of the n smallest
positive integers
Replace these integers with corresponding
elements
59
Example
procedure next permutation(a1a2…an: permutation of {1,2,…,n} not equal to n n-1 …2 1)
j := n -1
while aj > aj+1
j := j - 1
{j is the largest subscript with aj < aj+1}
k:= n
while aj > ak
k := k - 1
{ak is the smallest integer greater than aj to the right of aj}
interchange aj and ak
r := n
s := j + 1
while r > s
begin
interchange ar and as
r := r – 1
s := s + 1
end
{this puts the tail end of the permutation after the jth position in increasing order}
60
Generating Combinations

How to generate all combinations of the
elements of a finite set


Combination is a subset
Use the correspondence between subsets of
{a1, a2, …, an}
61
Examples
procedure next bit string(bn-1bn-2…b1: bit string not eqal to 11…11)
i := 0
while bi = 1
begin
bi := 0
See Section 5.6 for more details
i := i +1
end
procedure next r-combination(a1, a2, … , ar: proper subset of {1, 2, … ,n} not equal to
bi := 1
{n – r + 1, … , n} with a1 < a2 < … < ar)
i := r
while ai = n – r + i
i := i - 1
ai := ai + 1
for j := i + 1 to r
aj := ai + j - i
62
Prolog Tutorial
From “Learn Prolog Now”
http://www.coli.uni-saarland.de/~kris/learnprolog-now/lpnpage.php?pageid=online
63
Prolog Basics

Fact, Rules, and Queries





3 basic constructs in Prolog
A collection of facts and rules is called a knowledge base (or a
database).
Prolog programming is all about writing knowledge bases.
Prolog programs work by asking questions or querying about
the information stored in the knowledge base.
It makes sense for some applications such as Computational
Linguistic and AI.
64
Prolog Basics

Fact, Rules, and Queries
3 basic constructs in Prolog
 A collection of facts and rules is called a knowledge base (or a
database).
 Prolog programming is all about writing knowledge bases.
 Prolog programs work by asking questions or querying about
the information stored in the knowledge base.
 It makes sense for some applications such as Computational
Linguistic and AI.
The best way of learning Prolog is by learning Knowledge Base
(KB)
65


Prolog Basics

KB1: facts



woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
Each statement in Prolog ends with ‘.’
Prior to infer or conclude anything, we have to consult KB first.
To ‘consult’ KB is to load it to Prolog workspace.
66
Prolog Basics

KB2: rules




listensToMusic(mia).
happy(yolanda).
playsAirGuitar(mia) :- listensToMusic(mia).
playsAirGuitar(yolanda) :- listensToMusic(yolanda).
listensToMusic(yolanda):- happy(yolanda).
rules
There are no fact about “mia plays air guitar” in the KB
But there is a rule about “mia plays air guitar”
Prolog use Modus Ponens to infer that “mia plays air guitar” is
true
head :- body read as if the body is true, then the head is true
67
Prolog Basics

KB3: more rules





happy(vincent).
listensToMusic(butch).
playsAirGuitar(vincent):listensToMusic(vincent),
happy(vincent).
playsAirGuitar(butch):happy(butch).
playsAirGuitar(butch):listensToMusic(butch).
5 clauses: 3 rules and 2 facts
3 predicates: happy, listenToMusic,
and playsAirGuitar
In a KB, there is no fact saying
“vincent listens to music”
Hence, the query playsAirGuitar(vincent) is false
head :- body1, body2  (body1  body2)  head
68
Prolog Basics

KB4: variables





woman(mia).
woman(jody).
woman(yolanda).
A variable is in CAPITAL
loves(vincent,mia).
Uses a variable to ask
loves(marcellus,mia).
whose property it is.
loves(pumpkin,honey_bunny).
loves(honey_bunny,pumpkin).
‘;’ means ‘or’
‘,’ means ‘and’
loves(marcellus,X), woman(X)
should read “whom is a woman
Marcellus love?”
( “whom does Marcellus love and is woman?”)
69
Prolog Basics

KB5: more variables





loves(vincent,mia).
loves(marcellus,mia).
loves(pumpkin,honey_bunny).
loves(honey_bunny,pumpkin).
Now, we use variable in rules.
Predicate jealous(X,Y) means that an
individual X will be jealous of an
jealous(X,Y) :- loves(X,Z),loves(Y,Z).
individual Y if there is some
individual Z that X loves, and Y loves
that same individual Z too.
This is more general than previous KB.
jealous(marcellus,W) asks: can you find
an individual W such that Marcellus is jealous of W?
Furthermore, suppose we wanted Prolog to tell us
about all the jealous people: what query would we pose?
70
Prolog Basics

Terms




All facts, rules, and queries are made of terms.
There are 4 kinds of term in Prolog: atoms, numbers,
variables, and complex terms (or structures).
Atoms and numbers are lumped together under the
heading constants, and constants and variables
together make up the simple terms of Prolog.
Please consult websites, books or other
resources for further details.
71
Python Tutorial
From “Learn Python in 10 minutes”
http://www.poromenos.org/tutorials/python
72
Python Basics

Properties






dynamically, implicitly typed (i.e., do not have to
declare the type )
case sensitive
object-oriented
Use interpreter
To get help in Python, type help([object]) at the
prompt.
Type dir([object]) to ask Python how to use that
method
73
Python Basics
74
Python Basics

Syntax








No mandatory statement terminate character
Block is specified as indentation
Statement that expects indentation ends in colon (:)
Comments start with pound (#) and are single line
Use multi-line strings for multi-line comments
Values are assigned with the equal sign (=)
“==” is used for equality testing
“+=” and “-=” are used for increment and decrement,
respectively
75
Python Basics
76
Python Basics

Data types






Lists: one-dimensional array
Tuples: immutable one-dimensional array
Dictionaries: associative array (hash table)
Index starts from 0, negative number counts from
the end toward the beginning of list, -1 is the last
item
Variables can point to function
Can access array ranges using colon (:)
77
Python Basics
78
Python Basics

String



Use either single quote or double quote marks (‘ or
“) to create string
Multi-line strings are enclosed with triple double or
single quote
To fill a string with values, use %s and a tuple
79
Python Basics

Flow Control Statements



They are while, if, and for. No select.
Use for to enumerate through a list
Use range([number]) to obtain a list of numbers
80
Python Basics
81
Python Basics

Function






Declares with def keyword
Optional arguments are set in the function declaration after mandatory
arguments by being assigned a default value.
For named arguments, the name of the argument is assigned a value.
Functions can return a tuple.
Lambda functions are ad hoc functions that are comprised of a single
statement.
Parameters are passed by reference, but immutable types (tuples, ints,
strings, etc) cannot be changed. This is because only the memory location
of the item is passed, and binding another object to a variable discards the
old one, so immutable types are replaced.
82
Python Basics
83
Python Basics

Importing


Use import [libname] keyword to import
external library
Or use from [libname] use [funcname] to
import specified function from external
library
84
Python Basics

Miscellaneous




Conditions can be chained. 1 < a < 3 checks that a is both less than 3 and
more than 1.
You can use del to delete variables or items in arrays.
List comprehensions provide a powerful way to create and manipulate
lists. They consist of an expression followed by a for clause followed by
zero or more if or for clauses.
Global variables are declared outside of functions and can be read without
any special declarations, but if you want to write to them you must declare
them at the beginning of the function with the "global" keyword,
otherwise Python will bind that object to a new local variable (be careful of
that, it's a small catch that can get you if you don't know it).
85
Python Basics
See these links for further tutorials
http://docs.python.org/tutorial/
http://www.sthurlow.com/python/
86
Homework






Section 5.1
 2, 10, 18, 25, 33, 34, 43
Section 5.2
 1, 8, 10, 15, 32
Section 5.3
 8, 14, 24, 33, 35, 39
Section 5.4
 15, 28, 32
Section 5.5
 1, 13, 15, 16, 30, 37, 50, 59
Section 5.6


10, 13
Supplementary
 4, 11, 22, 27, 36, 42
87