CountingPhilosophyNumber systemsCounting in various basesPowersCounting subsetsGroupingPermutationsCounting permutationsArray permutationsComputing permutationsPermutations of non-unique valuesMore permutationsSubset permutationsComputational common senseChoicesCounting problemsYet more counting problemsSummaryThe EndJan 14, 2019Counting2PhilosophyThis set of slides is about counting thingsMuch of it is a branch of mathematics called combinatoricsI believe:Mathematics is logical and makes senseIf you understand the math, you don’t need to memorize a bunch of equationsSome people believe:If you memorize a bunch of equations, you don’t need to understand the mathThe second approach works a lot of the time, but…Real-life problems don’t come with a little tag attached telling you what equation to use3Number systemsA number system base B is a set of B “digits” representing the numbers 0 through B-1Example: Decimal (base 10) uses the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9Example: Ternary (base 3) uses the digits 0, 1, and 2If the base isn’t obvious from context, it is written as a subscript of the numberExample: 21203 means “2120 base 3”Bases used in computer programming:DecimalBinary (base 2) uses the binary digits (bits) 0 and 1Octal (base 8) uses the octal digits 0, 1, 2, 3, 4, 5, 6, and 7Hexadecimal, or “hex” (base 16) uses the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F4Counting in various basesThe rule for getting the “next number” (adding one) in any system is always the same: If a digit is the largest possible, reset it to zero and add 1 to the digit on the leftDecimal examples: 9 10, 1299 1300, 83989 83990Octal examples: 7 10, 1277 1300, 75767 75770Hex examples: F 10, A2FF A300, F5FEF F5FF0Binary examples: 1 10, 1011 1100, 110111 111000The same number is usually represented different ways in different number systemsExample: 4810 = 3016 = 608 = 1100002But: 510 = 516 = 58 = 10125PowersIn any base B, the digits of a number represent a multiplier of a power of BExample: 402510 = 4*103 + 0*102 + 2*101 + 5*100Example: 40258 = 4*83 + 0*82 + 2*81 + 5*80 = 4*512 + 0*64 + 2*8 + 5*1 = 206910It is useful to learn the powers of 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384It is especially useful to remember that 210 = 1024 is approximately equal to 103 = 1000In any base B, you can represent BK different numbers (0 through BK-1) with K digits6Counting subsetsGiven a set of N distinct values, {A, B, C}, there are exactly 2N possible subsets of those valuesYou can show this by counting in binary: A 1 means it’s in the subset, a 0 means it’s not{ A, B, C } 0 0 0 { } (the empty subset) 0 0 1 { C } 0 1 0 { B } 0 1 1 { B, C } 1 0 0 { A } 1 0 1 { A, C } 1 1 0 { A, B } 1 1 1 { A, B, C } (the “improper” subset)7GroupingSuppose we have a collection of N unique items, and we want to sort them into two pilesThe piles don’t need to be equal in sizeIn fact, it’s OK for one of the piles to be emptyHow many different ways can we sort the items into two piles?Suppose we have a collection of N unique items, and we want to sort them into three pilesThe piles don’t need to be equal in sizeIn fact, it’s OK for one, or even two, of the piles to be emptyHow many different ways can we sort the items into three piles?8PermutationsGiven a set of N distinct values, a permutation is a possible ordering of those valuesExample: There are two permutations of the set {A, B}: AB and BAExample: There are six permutations of the set {A, B, C}: ABC, ACB, BAC, BCA, CAB, CBAExample: There are 24 permutations of the set {A, B, C, D}: ABCD, ACBD, BACD, BCAD, CABD, CBAD, ABDC, ACDB, BADC, BCDA, CADB, CBDA, ADBC, ADCB, BDAC, BDCA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA9Counting permutationsTo find the permutations of {A, B, C, D, E}, there are:Five possible choices for the first itemFour possible choices for the second itemThree remaining possible choices for the third itemTwo remaining possible choices for the fourth item, andOnly one possible “choice” for the final itemFor any positive integer N, we define N! (“N factorial”) as the product of all the positive integers up to and including NExample: 5! = 1 * 2 * 3 * 4 * 5 = 120Given any N distinct items, there are N! possible permutations of those items10Array permutationsSorting an array is finding a particular permutation of the elements in the array that satisfies some conditionIf you have an array of 50 elements, there can be as many as 50! possible ways to order those valuesThis is an extremely large number!If some of the elements are the same, there are fewer possible orderingsFor example, if all the elements in the array are equal, there is only one possible ordering11Computing permutationsIt’s easy to describe a recursive procedure for finding all permutations (it’s not so easy to implement):There is only one permutation of one object (base case): AGiven all the permutations of N objects, find the permutations of N+1 objects by inserting the new object in each possible position of each permutation of N objectsExample: From A, get BA and ABExample: From BA and AB, get CBA, BCA, BAC, CAB, ACB, ABC12Permutations of non-unique valuesHow many possible permutations are there of the valuesA, A, A, B, C ?If the values were all distinct, there would be 5! possible permutations--but they aren’t all distinctWe can’t distinguish one ABAAC from another ABAACBut if we pretend that we can tell one A from another, we find that there are 3! = 6 possible ways to get ABAAC:ABAAC, ABAAC, ABAAC, ABAAC, ABAAC, ABAACIn fact, every other permutation, such as ACABA, is represented in six different waysThis is because there are six ways to permute the As: AAA, AAA, AAA, AAA, AAA, AAAHence, there are really only 5!/3! = 120/6 = 20 possible permutations:AAABC, AABAC, AABCA, ABAAC, ABACA, ABCAA, BAAAC, BAACA, BACAA, BCAAA, AAACB, AACAB, AACBA, ACAAB, ACABA, ACBAA, CAAAB, CAABA, CABAA, CBAAA13More permutationsHow many possible permutations are there of the values A, A, A, B, C, C
View Full Document
Unlocking...