Let’s Count
Dr Aamir Hashmi
-My office: Email: [Link]@[Link]
Cabin-3, F-102, B-Building
Office Hours:
Tuesday: 10:00 – 12:00
Thursday: 10:00 – 12:00
Friday: 10:00 – 12:00
or by appointment (email)
Alice’s Party
• Friends: Bob, Carl, Dian, Eve, Fred, George
• How many handshakes?
Alice’s Party
• Friends: Bob, Carl, Dian, Eve, Fred, George
• How many handshakes?
42 ???
• How about when 2 persons meet?
• Two handshakes? Or one?
• Double Counting?
• 42/2 = 21 handshakes …
Sets
• P = {Alice, Bob, Carl, Dian, Eve, Fred, George}
• P = {Alice and her guests}
• 𝐺 = 𝑥 ∈ 𝑃, 𝑥 is a girl = {Alice, Dian, Eve}
• 𝐷 = 𝑥 ∈ 𝑃, 𝑥 is over 21 years age = {Alice, Carl, Frank}
Sets
• We use many number sets
• Set of positive integers: 𝑥 ∈ ℤ: 𝑥 ≥ 0
• 𝜙 ⊆ ℕ ⊆ ℤ+ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ
Sets
• Set operations:
Union, 𝐴∪𝐵
Intersection, 𝐴 ∩ 𝐵
Difference, 𝐴 − 𝐵 or 𝐴 \ B, 𝐵 − 𝐴 or 𝐵 \ 𝐴
Symmetric difference 𝐴Δ𝐵 = A\B ∪ (𝐵\𝐴)
• DeMorgan’s Law
• 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪ 𝐴∩𝐶
• 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩ 𝐴∪𝐶
Sets: Venn diagram
• DeMorgan’s Law
• 𝐴∩ 𝐵∪𝐶 = 𝐴∩𝐵 ∪ 𝐴∩𝐶
• 𝐴∪ 𝐵∩𝐶 = 𝐴∪𝐵 ∩ 𝐴∪𝐶
Alice’s Party: Hand Shaking
• How many handshakes?
21, for 7 people.
• A general formula
• Let’s make a graph of it.
Alice’s Party: Hand Shaking
• How many handshakes?
21, for 7 people.
• A general formula
𝑵 𝑵−𝟏
𝟐
• Let’s make a graph of it.
• Complete graph: 𝑲𝑵
Alice’s Party: Seating Plan
• Possible seating arrangement?
• Change after every half hour? How log will this part go?
Alice’s Party: Seating Plan
• Possible seating arrangement?
• Change after every half hour? How log will this part go?
• With Alice place fixed?
720 (15 days :o .. Quite a party)
• With Alice place changed?
Alice’s Party: Pooling for Lottery Ticket
• Lottery rule: You have 5 numbers. If these match with the lottery ticket’s 5
numbers (out of total 90), you win the jack-pot
• Plan: Buy enough tickets, no matter what they draw, we will have a ticket
with the winning numbers !!!
• How many tickets to buy?
Alice’s Party: Pooling for Lottery Ticket
• Lottery rule: You have 5 numbers. If these match with the lottery ticket’s 5
numbers (out of total 90), you win the jack-pot
• Plan: Buy enough tickets, no matter what they draw, we will have a ticket
with the winning numbers !!!
• How many tickets to buy?
Alice’s Party: Pooling for Lottery Ticket
• Lottery rule: You have 5 numbers. If these match with the lottery ticket’s 5
numbers (out of total 90), you win the jack-pot
• Plan: Buy enough tickets, no matter what they draw, we will have a ticket
with the winning numbers !!!
• How many tickets to buy?
A huge number
Alice’s Party: Let’s play cards
• Bridge rule: Each of the 4 players get 13 cards
• A strange claim:
Alice’s Party: Let’s play cards
• Bridge rule: Each of the 4 players get 13 cards
• A strange claim: I have got exactly the same cards as before
• What are the chances for this to happen?
Alice’s Party: Let’s play cards
• Bridge rule: Each of the 4 players get 13 cards
• A strange claim: I have got exactly the same cards as before
• What are the chances for this to happen?
One out of these many:
highly unlikely !!!
Alice’s Party: Playing Chess
• Setting: Set up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
Alice’s Party: Playing Chess
• Setting: Alice sets up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
Alice’s Party: Playing Chess
• Setting: Set up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
Alice’s Party: Playing Chess
• Setting: Set up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
Alice’s Party: Playing Chess
• Setting: Set up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
Alice’s Party: Playing Chess
• Setting: Set up 3 boards of chess,
with 2 players playing against each other.
How many ways can the players be matched with each other?
An alternate way to count
• This ends the party at a happy note and we leave the party
Merci et Au Revoir !!!
Note:
Be ready for the quiz in next class from the given reading
Assignment will be available on portal on Thursday
Try this problem:
Do it by yourself:
• List all subsets of {0, 1, 3}. How many do you get?
• List all subsets of {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}, containing a but not containing b.
• Define a set of which both {1, 3, 4} and {0, 3, 5} are subsets. Find such a set
with the smallest possible number of elements.
Good Practices Bad Practices
• Be on time in class • Coming late in class (remember: quiz will be
in 1st 10 min of class)
• Start assignments on • Come to class without pen and
time notebooks
• Do not submit • Asking for leaves --- Teacher has no
authority to grant leaves. Manage your 6
assignment late (better absents as emergency leaves, or request
submit an incomplete assignment, HoD/Dean for extra leaves.
rather than to miss the assignment)
• Coming to class without reading the
• Visit during office hours required text/notes
to discuss your • Copying / plagiarism
problems/assignments
Bad Practices
• Excuses
• Coming late in class (remember: quiz will be in 1st 10 min of class)
• Come to class without pen and notebooks
• Asking for leaves --- Teacher has no authority to grant leaves. Manage your 6
absents as emergency leaves, or request HoD/Dean for extra leaves.
• Requesting to increase marks
• Coming to class without reading the required text/notes
• Copying / plagiarism
• Asking to extend the deadline
• Using mobile phones in class - Cross talk in class