Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Counting Number of Possible Solutions – Simple CombinatoricsCombination - 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 CombinatoricsPermutations - 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 CombinatoricsCombination – the number of combinations that can be made when choosing k items from a set of n items is denoted asExample – how many different hands of 5 cards can be dealt from a pack of 52 cards?Counting Number of Possible Solutions – Simple CombinatoricsPermutation– 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! = 61-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1Counting Number of Possible Solutions – Simple CombinatoricsTraveling salesman problem: For the term project consisting of 48 cities, how many possible solutions exist?Answer: 48! = 1.24 x 1061Counting Number of Possible Solutions – Simple CombinatoricsKnapsack problem: For the 20 item knapsack homework problem, how many possible solutions exist?Answer:= = 20 + 190 + 1140 + … + 184756 + ... + 1140 + 190 + 20 +