Transcript Lesson 11A - Simple Combinatorics

Counting Number of Possible Solutions
– Simple Combinatorics
Combination - an un-ordered collection of distinct elements,
usually of a prescribed size and taken from a given set. Given
such a set S, a combination of elements of S is just a subset of S,
where as always for (sub)sets the order of the elements is not
taken into account (two lists with the same elements in different
orders are considered to be the same combination). Also, as
always for (sub)sets, no elements can be repeated more than
once in a combination; this is often referred to as a "collection
without repetition".
Counting Number of Possible Solutions
– Simple Combinatorics
Permutations - a sequence containing each element from a finite
set once, and only once. The concept of sequence is distinct from
that of a set, in that the elements of a sequence appear in some
order: the sequence has a first element (unless it is empty), a
second element (unless its length is less than 2), and so on. In
contrast, the elements in a set have no order; {1, 2, 3} and {3, 2,
1} are different ways to denote the same set.
However, there is also a traditional more general meaning of the
term "permutation" used in combinatorics. In this more general
sense, permutations are those sequences in which, as before,
each element occurs at most once, but not all elements of the
given set need to be used.
Counting Number of Possible Solutions
– Simple Combinatorics
Combination – the number of combinations that can be made
when choosing k items from a set of n items is denoted as
Example – how many different hands of 5 cards can be dealt from a
pack of 52 cards?
Counting Number of Possible Solutions
– Simple Combinatorics
Permutation– the number of permutations that can be made from a
set of n items is: n!
Or in general, the number of permutations of size r that can be
formed from a set of n items is:
Example – how many sequences can you form from the numbers
1,2,3?
Answer – 3! = 6
1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1
Counting Number of Possible Solutions
– Simple Combinatorics
Traveling salesman problem: For the term
project consisting of 48 cities, how many
possible solutions exist?
Answer: 48! = 1.24 x 1061
Counting Number of Possible Solutions
– Simple Combinatorics
Knapsack problem: For the 20 item knapsack
homework problem, how many possible
solutions exist?
Answer:
 20   20   20 
 20 
         ...   
1 2 3
 20 
=
20!
20!
20!
20!
20!
20!
20!


 ... 
 ... 


1!(19!) 2!(18!) 3!(17!)
10!(10!)
18!(2!) 19!(1!) 20!(0!)
=
20 + 190 + 1140 + … + 184756 + ... + 1140 + 190 + 20 + 1