×

### Let's log you in.

or

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

×

### Create a StudySoup account

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

or

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

Already have a StudySoup account? Login here

by: Shlomo Oved

15

0

4

# Discrete Mathematics Week 2 Lecture and Recitation Notes MA-UY 2314

Marketplace > New York University > Mathematics > MA-UY 2314 > Discrete Mathematics Week 2 Lecture and Recitation Notes
Shlomo Oved
NYU

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

×
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

Covers everything done in Recitation and Lecture
COURSE
Discrete Mathematics
PROF.
Dr Nasir Memon
TYPE
Class Notes
PAGES
4
WORDS
CONCEPTS
Counting, 6.1, 6.2
KARMA
25 ?

## Popular in Mathematics

This 4 page Class Notes was uploaded by Shlomo Oved on Wednesday September 14, 2016. The Class Notes belongs to MA-UY 2314 at New York University taught by Dr Nasir Memon in Fall 2016. Since its upload, it has received 15 views. For similar materials see Discrete Mathematics in Mathematics at New York University.

×

## Reviews for Discrete Mathematics Week 2 Lecture and Recitation Notes

×

×

### What is Karma?

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

Date Created: 09/14/16
Shlomi  Oved   Discrete  Mathematics   09/14/16   09/13/16  Recitation  (Week  2)   Problem:   Given  integers  of  the  form  abcabc  show  that  all  of  them  are  divisible  by  13.   Ex:  123123,  758758   ????????????????????????/???????????? = 1001????????????   1001/13   = 77   ???????????????????????? = 13 ∗ 17 ∗ ????????????     Homework  Problems   Section  2.1   6.  ???? = 2,4,6 ,???? = 2,6 ,???? = 4,6 ,???? = {4,6,8}   ???? ⊆ ????,???? ⊆ ????,???? ⊆ ????     11.   a.  ???? ∈ {????} → ????????????????   b.   ???? ⊆ ???? → ????????????????   c.     ????  ∈ ???? → ????????????????????   d.   ???? ∈ ???? → ????????????????   e.  ∅ ⊆ ???? → ????????????????   f.  ∅ ∈ ???? → ????????????????????     20.   a.   ∅ = 0   b.   {∅} = 1   c.   {∅,{∅}} = 2   d.   {∅, ∅ , ∅, ∅ } = 3     Section  2.2   25.  ???? = 0,2,4,6,8,10 ,???? = 0,1  ,2  3,4,5,6 ,???? = {4,5,6  ,7  8,9,10}   a.  ???? ∩ ???? ∩ ???? = {4,6}   b.  ???? ∪ ???? ∪ ???? = {0,1,2,3,4,5,6,7,8,9,10}   c.   ???? ∪ ???? ∩ ???? = 4,5,6  ,8,10   d.   ???? ∩ ???? ∪ ???? = {0,2  ,4,6,7,8,9,10}     Given  ???? ∪ ???? = ???? ∪ ????,????????:???? ≠ ????   ???? = 1,2   ???? = 3,4   ???? = 1,2     Given  ???? ∩ ???? = ???? ∩ ????,????????:???? ≠ ????   ???? = 1,2,3,4   ???? = 1,2,5,7   ???? = 1,2,6,9     Power  Sets     Shlomi  Oved   Discrete  Mathematics   09/14/16   ????????:???? = ????,???? ,???? ???? = ???? , ???? , ????,???? ,∅ , ????(????) = 4   ▯ ????????????  ????????????  ????????????ℎ  ????  ???????????????????????????????? = 2     09/14/16  Lecture  (Week  2)   Review-­‐  Counting  6.1  +6.2   • Product  Rule,  Sum  Rule,  Pigeon  Hole  Principle,  Generalized  pigeon  hole   principle,  Inclusion  Exclusion  principle.  Quiz  will  have  one  problem  on  each   subject     Chapter  6.2  +  6.3  Permutations  and  Combinations   • There  are  5  students.  How  many  different  way  can  I  seat  them  in  5  chairs?   • 5! → 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1   • How  many  different  ways  to  fit  10  students  in  5  chairs   ▯▯! • ▯! → 10 ∗ 9 ∗ 8 ∗ 7 ∗ 6     Permutations   • Definition-­‐  A  permutation  of  a  set  of  distinct  objects  is  an  ordered   arrangement  of  these  objects   • Definition-­‐  An  ordered  arrangement  of  r  elements  of  a  set  is  called  an  r-­‐ permutation.   • ???? ????,????    ????ℎ????????  ????ℎ????  ????????????????  ????????  ????ℎ????  ????????????  ????????  ????   • Theorem-­‐  If  n  is  a  positive  integer  with  1 ≤ ???? ≤ ????,  then  ???? ????,???? = ???? ∗ ???? − 1 ∗ ???? − 2 ∗ (???? − ???? + 1)   • Note-­‐  0! = 1   ▯! • ???? ????,???? = ▯▯▯ !     • Example:   • How  many  permutations  of  the  letters  ABCDEFGJ  contain  the  string  ABC?   • 6!     • Example:   • Find  all  the  subsets  of  size  3  of  the  following  set:  {1,  2,  3,  4}   • 1,2,3 , 2,3,4   , 1,2,4 ,{1,3,4}   • Definition-­‐  A  r-­‐combination  of  elements  from  a  set  from  n  elements  is  a   unordered ▯selection  of  r  elements  from  the  set.     • ???? ????,????     ▯   • Theorem:  The  number  of  r  combinations  of  a  set  with  n  elements  where  n  is  a   non-­‐negative  integer  and  r  is  an  integer  such  0 ≤ ???? ≤ ????  equals   ▯! • ???? ????,???? = ▯! ▯▯▯ !   • “Proof”:   ▯! • ???? ????,???? =   ▯▯▯ ! • Can  we  relate  permutations  and  combinations     Shlomi  Oved   Discrete  Mathematics   09/14/16   • ???? ????,???? = ???? ????,???? ∗ ????!   ▯ ▯,▯ • ???? ????,???? = ▯!   ▯! • ???? ????,???? = ▯▯▯ !▯!     • Example:  How  many  possible  poker  hands  can  one  have?   ▯▯ ▯▯! • ▯ = ▯▯!∗▯!     • Binomial  Coefficients   • ???? + ????   • ???? + ???? ∗ ???? + ???? ∗ (???? + ????)   • ???? + 3???? ???? + 3???????? + ????   ▯ • ▯                          ▯ ▯ ▯ ▯   • Binomial  Theorem   ▯ ▯ ▯ ▯ ▯▯▯ ▯ ▯▯▯ ▯ ▯ • ???? + ???? = ▯ ???? + ▯ ???? + ▯ ???? ???? + ⋯+ ▯ ????   • Proof:  By  similar  argument   ???? + ???? ∗ ???? + ???? …∗ (???? + ????)   • ???? + ???? ▯ = ▯▯▯ ▯ ???? ▯▯▯????   ▯   • Example:   ???? + ???? ▯▯   • (Quiz)-­‐   • What  is  the  coefficient  of  ???? ???? ?   ▯▯ • ▯▯     • Fact-­‐  given  a  set  of  size  n  the  cardinality  of  the  power  set  of  the  set  is  2 .   • 1,2,3,4,5,…????   • ????????????????????????  ????????  ???????????????????????????? = ▯ + ▯ + ▯ + ⋯ ▯   ▯ ▯ ▯ ▯ • ????????  ????????  ????????????????????????????  ????????  ????ℎ????  ????????????????????????????????  ????????????????????????????????????????.   • ????????????????  ????????????  ????  ????????????  ????  ????????  1   ▯ ▯ ▯ ▯ ▯ ▯ • 1 + 1 = 2 = ▯ + ▯ + ▯ + ⋯ ▯     ▯ ▯ ▯ ▯ • ▯▯▯ 2 ▯ = 3    ????????  ????????  ?????????????????         • 1.    If  I  eat  spicy  food  then  I  have  strange  dreams   • 2.  I  have  strange  dreams  if  there  is  thunder   • 3.  I  did  not  have  strange  dreams  last  night   • Therefore  there  I  didn’t  eat  spicy  food  and  there  was  no  thunder  last  night     • Every  CS  major  has  a  personal  computer   • Ralph  does  not  have  a  personal  computer     Shlomi  Oved   Discrete  Mathematics   09/14/16   • Ann  has  personal  computer.   • Ralph  is  not  a  CS  major.

×

×

×

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

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

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

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

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

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