New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Honors Discrete Mathematics

by: Dino Corwin

Honors Discrete Mathematics MAD 2104

Dino Corwin
GPA 3.8

Jorge Viola-Prioli

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jorge Viola-Prioli
Class Notes
25 ?




Popular in Course

Popular in Mathematics Discrete

This 9 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 15 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.

Popular in Mathematics Discrete


Reviews for Honors Discrete Mathematics


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/12/15
7LISTS A set is a collection of objects called its elements usually denoted by means of curly brackets When denoting a set like 5 1 2 a the order is irrelevant and repetitions are not allowed Thus 5 above has 4 different elements The set 123 equals 321 and 312 However 1223 makes no sense In a set the elements can be of a different nature More often than not one wishes to considers collections in which objects are repeated Thus we need a concept different from that of a set A list is a nite ordered sequence of objects that is usually denoted by writing them between parentheses Therefore in a quotit the order is crucial and the elements can be repeated J Viola Prioli Moreover as in sets the elements can be of a different nature The number of entries in a list is called the length of the list Therefore 0 1 O O 1 is a list of length ve and 2 7 a John a a is a list of length six Two lists are equal if they have the same length and the same corresponding entries A list of length two is simply called an ordered pair A list of length three is referred to as an ordered triple In what follows we calculate the number of pairs and triples J Viola Prioli What is the number of ordered pairs if entries can be taken from a set of size n Since we are counting we may take the set to be 1 2 n without loss of generality Now it is easy to write down all the pairs 1 1 1 2 1 n 2 1 2 2 2 n 3 1 3 2 3 n n 1 n 2 n n J Viola Prioli Clearly they are all different and we have exhausted them all The number of ordered pairs is thus n2 How many ordered pairs a b are there if a comes from a pool of m distinct elements and b from a pool of n distinct elements In this case the arrangement looks like 1 1 1 2 1 n 2 1 2 2 2 n 3 1 3 2 3 n m 1 m 2 m n thus the answer is mxn J Viola Prioli We are ready to state and prove the following basic result that is Theorem 72 in the textbook FUNDAMENTAL COUNTING PRINCIPLE f task A can be performed in m different ways and after A has been completed task B can be performed in n different ways then the combined task A followed by task B can be performed in exactly mxn ways Proof We can identify quotA followed by Bquot with ordered pairs ab We have m choices for a and n choices for b so mxn pairs according to our previous computation We emphasize that the answer is not m n but mxn With the tool afforded by the Fundamental Counting Principle FCP we can next analyze longer lists J Viola Prioli How many ordered triples a b c are there if a has m different choices b has n different choices and c has k different choices To manufacture ordered triples a b c we can think of two tasks Task A construct the pair ab Task B complete the triple a b c For A we have mxn choices Once A has been completed we insert the entry c in k ways By the FCP we have mxn x k different ways We conclude that there are mxnxk ordered triples Thus there are 43 triples a b c if the entries come from 1 2 3 4 J Viola Prioli By repeated application of the FCP we have the following If there are 5 tasks to be considered one after the other and after taskj1 has been concluded the taskj can be performed in nj ways then the sequence of tasks can be completed in n1 x n2 x x nS TIP Counting problems involving lists can be complicated however they become manageable if we think in terms of tasks Let us discuss exercises 75 and 77 DEFINITION A binary string of length k also called a kbinary string is a list of length k whose entries come from 0 1 In brief quotis a list of O and 1 of length kquot Therefore 0 O 1 is a 3binary string and so is 1 1 1 J Viola Prioli Since each entry has 2 choices our Corollary above shows that there are 2n binary strings of length n The number of n length binary strings is 2n What happens if we do not allow repetitions More precisely suppose we must compute the number of lists of length k taken from a pool of n different objects if repetitions of the entries are not allowed The rst entry will have n choices the second entry will have only n l choices the third entry must be chosen from n 2 objects etc As a result the number of different arrays will be n x n l x n 2 x x n k1 This number so constructed is called the falling factorial usually indicated in calculators by the symbolnPk Notice that nPk is the product of k consecutive integers beginning with n in decreasing order Of course in all these cases n 2 k gt O J Viola Prioli For instance 7P5 7 x 6 x 5 x 4 x 3 2520 and nP1 n for all n gt 0 We can discuss now Exercise 711 and others J Viola Prioli


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.