### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete Mathematics CS 220

WVU

GPA 3.77

### View Full Document

## 199

## 0

## Popular in Course

## Popular in ComputerScienence

This 3 page Class Notes was uploaded by Abe Jones on Saturday September 12, 2015. The Class Notes belongs to CS 220 at West Virginia University taught by Subramani in Fall. Since its upload, it has received 199 views. For similar materials see /class/202758/cs-220-west-virginia-university in ComputerScienence at West Virginia University.

## Reviews for Discrete Mathematics

### 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: 09/12/15

Discrete Mathematics Scrimmage 11 Solutions K Subramani LCSEE West Virginia University Morgantown WV ksmani cseewvuedu 1 Problems 1 N Prove or disprove AUB X C AUB X AUC Solution Set B lt15 and C A In this case the LHS is A U 15 X C A U 15 A On the other hand the RHS is A U 15 X A U A A X A Since A y A X A for arbitrary A the proposed conjecture is false B Let A B and C denote three sets where A B and C are subsets of a set S Prove that a 73A U 73B Q 73A U B b AUC A BUC B A Bi Solution a Let X E 73A U73B It follows that X 6 73A or X E 73B or both Assume that X 6 73A It follows that X Q A and hence X Q A U B Hence X E 73A U B In similar fashion we can show that if X E 73B then X E 73A U B Thus 73A U 73B Q 73AU B b Observe that AUC A BUC B A U C F B F A U B F C commutativity A U C F B F A U C distributitivity A U C F A U C F B commutativity A U C F A U C F B associativity A F C U C F B distributivity complement properties A S B A F B identity properties D 3 Among a banks 214 customers 189 have checking accounts 73 have regular savings accounts 114 have money market savings accounts and 69 have both checking and regular savings accounts No customer is allowed to have both regular savings and money market savings accounts How many customers have both checking and money market savings accounts Solution Let a A denote the set of people with checking accounts b B denote the set of people with regular savings accounts and c 0 denote the set of people with money market savings accounts We have that a jA UB U 0 214 b jAj 189 c ij 73 d 0 114 e jA Bj 69 and 0 B m Cl 0 We are required to calculate jA C From the principle of inclusion and exclusion we know that lAUBUCllAlHBHlClilA BlilB ClilA ClHA B Cl Since B Q Cj 0 it trivially follows that jA Q B Q Cj 0 and hence jA Cj 93 D 4 In how many distinct ways can six people be seated around a circular table Solution This is a circular permutation problem as opposed to a linear permutation problem Note that n people can be seated at a regular table in Pn n n distinct ways However the situation is somewhat different when the seating is around a circular table This is because circular shifts of a straight line permutation are indistinguishable from each other in a circular table Observe that corresponding to each circular permutation of n people there are precisely n straight line permutations since we can shift a permutation n times without altering its circular structure In other words the n linear shifts of a given linear permutation give rise to the same circular permutation It follows that the total number of distinct circular permutations of n people is n 7 1 l The answer to our speci c question is therefore 5 120 D 5 How many distinct undirected graphs can you draw on n vertices Solution Given n vertices there are precisely Cn 2 possibile locations for an edge in an undirected gprah To identify a particular graph we need to select which of the Cn 2 locations contains an edge By a simple application of the multiplication principle it is clear that the total number of distinct graphs is 20013 D 6 Show that for any n and T withO g T g n Cn2 CT2Cn77 27 niT Solution We provide a combinatorial proof for the above identity Note that the LHS represents the number of distinct ways of selecting 2 objects from n distinct objects We break up the set of n objects into two disjoint sets with one set containing T objects and the other set containing n 7 T objects Observe that 2 objects can be selected in one of the following distinct ways a Both objects from the set of T objects this can be done in CT7 2 ways 03 Both objects from the set of n 7 T objects this can be done in Cn 7 T7 2 ways c One object from the set of T objects and the other object from the set of n 7 T objects this can be done in T n 7 T ways Thus the total number of ways to select 2 objects out of n is CT7 2 Cn 7 T7 2 T n 7 T which proves the identity You are of course welcome to attempt a proof using induction or rst principles D 7 Prove that i ii n 271Z1iCni or i1 Solution As per the binomial theorem 1 1 ZCQLJ lnii 11 i0 Zn Cn7 Ii i0 Differentiating both sides we get nlz 1 ZCniiazi 1 i0 Cm 2211 1 H H i Put 1 l in Equation 1 ii Put 1 71 in Equation 1 D

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "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."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.