DOC PREVIEW
UCF COT 3100 - Lecture Notes

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Let’s go through a problem that utilizes both of these rules:Here are the rules for a valid phone number:1) The first three digits must all be different.2) The first digit can not be a 1.3) If the first digit is a 5, the last four digits must all be thesame.Based on our rules, we must group our phone numbers intotwo separate groups:A: All numbers that start with 5B: All numbers that do NOT start with 5First, we will count all the phone numbers that fit in group A.___ ___ ___ - ___ ___ ___ ___ 1 9 8 10 1 1 1For the first number, we have 1 choice, 5.For the second number, we have 9 choices, everything but 5.For the third number, we have 8 choices.For the fourth number we have all 10 choices, but for the rest we only have 1 choice, based on our rules.Thus, we have 1x9x8x10x1x1x1 = 720 phone numbers thatstart with 5.Now, let’s count the phone numbers that do not start with 5:___ ___ ___ - ___ ___ ___ ___ , 8 9 8 10 10 10 10for a total of 8x9x8x10x10x10x10 = 5760000 phone numbersthat do not start with 5.Using the sum rule, we add this to our other value to get a totalof 5,760,720 total possible phone numbers under the givenrules.Here is a quick problem for you guys:How many 3 letter words can you form that have twoconsonants and a vowel?PermutationsA permutation of objects is simply an arrangement of thoseobjects. A common example of permutations deals with words.How many “words” can you form out of the letters A, B, C,and D, without repeating a letter. Essentially, the question boilsdown to how many ways can you order a set of objects. In thiscase, we know we have four choices for the first object. Oncewe have made that choice, it is clear that we will always havethree choices for the next object. In particular, we find thefollowing:____ ____ ____ ____ 4 x 3 x 2 x 1 = 24 possible permutations.In general, imagine the number of ways to permute n objects.Using the same process as above we find:____ ____ ____ ____ n x(n-1)x ... 2 x 1 = n! possible permutations.(Note: For those of you unfamiliar with the ! notation, it is readas “factorial”. n! is simply defined as the product of all thepositive integers in between 1 and n, inclusive.)Now, consider the following problem:Given n distinct objects, how many permutations are there of rof those objects, where 1  r  n.Using the product rule as before, we find:____ ____ ... ______ n x(n-1)x ... (n–k+1) = n!/(n–k)! possible permutations.Now, consider a situation where you are permuting objects,where some of those objects are indiscernible. For example,how many permutations are there of the word BEER? At firstwe would say 24, but the problem is that we can not tell thedifference between the two E’s. To look at the problem moreclosely, imagine giving subscripts to the 2 Es to discern them,and THEN listing out the permutations as follows:BEER B E1 E2 R B E2 E1 RBERE B E1 R E2B E2 R E1BREE B R E1 E2B R E2 E1EBER E1 B E2 R E2 B E1 REBRE E1 B R E2E2 B R E1EEBR E1 E2 B R E2 E1 B REERB E1 E2 R B E2 E1 R BERBE E1 R B E2E2 R B E1EREB E1 R E2 B E2 R E1 BRBEE R B E1 E2R B E2 E1REBE R E1 B E2R E2 B E1REEB R E1 E2 B R E2 E1 BThus, we see that there are really 12 distinct permutations ofBEER. (12 pack, 12 permutations, coincidence? Hmmm....)In particular, for every distinct permutation of BEER there are2 “possibilities” listed on the RHS with all the permutations,assuming distinct E’s. In fact, we can see that if we had a wordwith 3 E’s, there would be six “possibilities listed, 1 for eachpermutation of the 3 E’s, assuming that they are distinct. In general, the number of permutations of n letters, where thenumber of repetitions of each letter are n1, n2, n3, ... nk, isn!/(n1! n2! ...nk!)The reasoning behind this is the following:If we assume that each of the n letters is distinct (ie. if all thesimilar letters had subscripts to distinguish them) then n! is thecorrect answer. But, as we saw in our example before, usingthis method of counting, we count the same “word” multipletimes. Our goal is to figure out HOW many times we counteach word.If letter 1 appears n1 times, then we can rearrange each ofthose n1 characters in exactly n1! ways, keeping our originalpermutation unchanged.For each of those n1! arrangements, we have the following:If letter 2 appears n2 times, then we can rearrange each ofthose n2 characters in exactly n2! ways, keeping our originalpermutation unchanged.Since these are independent “events” so to speak, we use theproduct rule to calculate the total number of times we haverecounted the same permutation. The final answer ends upbecoming the product of all the frequencies of all the letters, ormore mathematically, n1! n2! ...nk!Thus, to get the true number of permutations with repeats, youmust divide n! by the value above.Example of a Combinatorial ProofLet n=2k, where k is a positive integer. In this situation, it turnsout that n!/2k is an integer. We can actually prove this using acombinatorial argument, which goes as follows:Consider counting the number of permutations of the nsymbols x1 , x1 , x2 , x2 , ... xk , xk. Using the formula derivedabove, we calculate this value to be:n!/(2!)k. But we know that 2! = 2, this the final value isn!/2k, which MUST BE an integer since the number ofpermutations of a group of letters is ALWAYS an integer.CombinationsNow, consider the following two questions:1) Given a set of n objects, how many total possible subsets canyou have of those objects? A subset simply is any group (with asize in between 0 and n, inclusive) of the n objects. The order inwhich the members of the subset are picked does not matter.2) Given a set of n objects, how many subsets of size k can youhave of those objects.For the first question, we can view creating a subset of a groupof n objects in the following manner:First, decide whether or not element #1 is in the subset.Next, decide whether or not element #2 is in the subset....Each of these choices is independent from each of the otherchoices, and for each choice we have two options. Thus, we canuse the product rule to count the total number of possiblesubsets:___ , ___ , ___ , ... ___ 2 x 2 x 2 x ... 2 = 2n total subsets of


View Full Document

UCF COT 3100 - Lecture Notes

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?