47
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
47
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Computing Fundamentals 2
Lecture 5
Combinatorial Analysis
Lecturer: Patrick Browne
http://www.comp.dit.ie/pbrowne/
Room K408
Based on Chapter 16.
A Logical approach to Discrete Math
By David Gries and Fred B. SchneiderCombinatorial Analysis
• Counting
• Permutations
• Combinations
• The Pigeonhole Principle
• ExamplesCombinatorial Analysis
• Combinatorial analysis deals with
permutations of a set or bag and
combinations of a set, which lead to
binomial coefficients and the Binomial
Theorem.Rules of Counting
• Rule of sums: The size of the union on n
finite pair wise disjoint sets is the sum of
their sizes.
• Rule of product: The size of the cross
product of n sets is the product of their
sizes.
• Rule of difference: The size of a set with a
subset removed is the size of the set
minus the size of the subset.Product Rule Example
• If each license plate contains 3 letters and
2 digits. How many unique licenses could
there be?
• Using the rule of products.
• 26 x 26 x 26 x 10 x 10 = 1,757,600
Permutation of a set
• A permutation of a set of elements is a linear
ordering (or sequence) of the elements e.g.
• {1,4,5}
• Permutation A : 1, 4, 5
• B : 1, 5, 4
• An anagram is a permutation of words.
• There are
n • (n – 1) • (n - 2) .. 1
permutations of a set of n elements.
• This is factorial n, written n!Calculating Factorial
module FACT {
protecting(INT)
-- Two notations for factorial
op _! : Nat -> NzNat {prec 10}
op fact : Nat -> NzNat
var N : Nat
-- Notation 1
eq 0 ! = 1 .
ceq N ! = N * (N - 1) ! if N > 0 .
-- Notation 2
eq fact(0) = 1 .
ceq fact(N) = N * fact(N - 1) if N > 0 .
}
open FACT
red 4 ! .
red fact(4) .Permutation of a set
• Sometimes we want a permutation of size
r from a set of size n.
• (16.4) P(n,r) = n!/(n-r)!
• The number of 2 permutations of BYTE is
• P(4,2) = 4!/(4-2)! = 4 • 3 = 12
• BY,BT,BE,YB,YT,YE,TB,TY,TE,EB,EY,ET
• P(n,0) = 1
• P(n,n-1) = P(n,n) = n!
• P(n,1) = nCalculating Permutations and
Combinations of sets
mod CALC{
pr(FACT)
op permCalc : Int Int -> Int
op combCalc :
vars N R : Int
-- Compute permutation where order matters abc =/= bac
-- A permutation is an ordered combination.
-- perm calculates how many ways R items can be selected from N items
eq permCalc(N , R) = fact(N) quo fact(N - R) .
-- combination of N things taking R at a time
-- Note extra term in divisor.
eq combCalc(N , R) = fact(N) quo (fact(N - R) * fact(R)) .}
open CALC
-- Permutation from 10 items taking 7 at a time
red permCalc(10,7) . – gives 604800
-- Combination from 10 i
red combCalc(10,7) . – gives 120Permutation with repetition of a set
• An r-permutations is a permutation that allows
repetition. Here are all the 2-permutation of the
letters in SON:
SS,SO,SN,OS,OO,ON,NS,NO,NN.
• Given a set of size n, in constructing an r-
permutation with repetition, for each element we
have n choices.
• (16.6) The number of r permutations with
r
repetition of a set of size n is n , repetition is
allowed in the permutation not in the original set.