Chapter 02 - Counting bài toán đếm Toán rời rạc

Toán rời rạc - bài toán đếm

1. Discrete Mathematics Counting Hà Minh Hoàng Faculty of Data Science and Artificial Intelligence College of Technology National Economics University

2. Counting elements Basics of counting Permutations and Combinations Pigeonhole Principle Discrete Probability Extended Permutations and Combinations Content

3. Combinatorics is an important part of discrete mathematics, focusing on the arrangement of objects. It involves listing and counting objects that satisfy specific properties. Counting problems frequently appear in both mathematics and computer science. For example, consider counting the number of different ways to set a password that meets the following conditions: The length must be at least 6 characters and at most 8 characters. Each character is selected from the set [‘0’..‘9’, ‘a’..‘z’]. Basics of counting (1)

4. Addition rule - Suppose there are two tasks: The first task can be done in n ₁ ways. The second task can be done in n ₂ ways. Then, there are n ₁ + n ₂ ways to do these two tasks. Example: We need to select a representative who meets one of the following criteria: A male student with an average grade of 8.0 or higher , or A female student with an average grade of 7.5 or higher . Given that: There are 20 male students who meet the requirement. There are 25 female students who meet the requirement. Thus, there are 20 + 25 = 45 ways to select a representative. This rule can be expressed in set notation as follows: If A₁, A₂, ..., Aₙ are disjoint sets, then the number of elements in their union is equal to the sum of the elements in each individual set: ∣A​ 1 ∪ A​ 2 ∪...∪A n ​∣ = ∣A 1 ​∣+∣A 2 ​∣+...+∣A n ​∣ Basics of counting (2)

5. Multiplication Rule - Suppose a task is divided into two steps: The first step can be done in n ₁ ways. The second step can be done in n ₂ ways. Then, there are n ₁ × n ₂ ways to complete the task. Example: We need to select two representatives: One male student with an average grade of 8.0 or higher . One female student with an average grade of 7.5 or higher . Given that: There are 20 male students who meet the requirement. There are 25 female students who meet the requirement. Thus, there are 20 × 25 = 500 ways to select the two representatives. This rule can be expressed in set notation as follows: Selecting an element from the Cartesian product A ₁ × A ₂ × ... × A ₙ is done by sequentially choosing: One element from A ₁ , one element from A ₂ , ..., one element from A ₙ ∣A​ 1 x A​ 2 x...x A n ​∣ = ∣A 1 ​∣ x ∣A 2 ​∣ x ... X ∣A n ​∣ Basics of counting (3)

6. Example 1 : Count the number of different ways to create a password that satisfies the following conditions: - The length must be at least 6 characters and at most 8 characters. - Each character is selected from the set [‘0’..‘9’, ‘a’..‘z’]. Example 2: Determine the value of variable k after executing each of the following code snippets. Basics of counting (4) k = 0; for (int i = 1; i <= 123; i++) k++; for (int i = 1; i <= 111; i++) k++; k = 0; for (int i = 1; i <= 123; i++) for (int i = 1; i <= 111; i++) k++;

7. Inclusion-Exclusion Principle The addition rule may lead to overcounting when some cases are counted twice. To determine the correct number of ways to perform a task, we add the number of ways to do each task individually and then subtract the cases that were counted twice. This is known as the Inclusion-Exclusion Principle. Example : How many students take Math or Physics , given that: 40 students take Math. 30 students take Physics. 15 students take both Math and Physics. Using the Inclusion-Exclusion Principle : 40 + 30 − 15 = 55 Set Theory Formulation : ∣A∪B∣ = ∣A∣+∣B∣−∣A∩B∣ Basics of counting (5)

8. Exercise : Count the number of binary strings of length 8 that either: start with bit 1, or end with two bits 00 Basics of counting (6)

9. At a university, there are 18 Mathematics students and 325 Data Science students . (a) How many ways can we select two representatives , one from the Mathematics students and the other from the Data Science students? (b) How many ways can we select one representative , either from the Mathematics students or the Data Science students? Basics of counting (7)

10. There are 6 airlines flying from New York to Denver and 7 airlines flying from Denver to San Francisco . How many different ways are there to travel from New York to San Francisco via Denver ? Basics of counting (8)

11. A multiple-choice test consists of 10 questions , and each question has 4 answer choices . (a) How many ways can the test be completed if every question must be answered? (b) How many ways can the test be completed if questions can be left unanswered? Basics of counting (9)

12. How many numbers from 1 to 1000 are divisible by 6 or 9? Basics of counting (10)

13. A permutation of a set of distinct objects is an ordered arrangement of these objects. An arrangement of r elements ( r ≤ n ) chosen from a set of n elements is called an r -permutation (or arrangement ) of n elements. A permutation is a special case where r = n. For example, given the set S = {1, 2, 3} : The arrangement (3, 1, 2) is a permutation of S . The arrangement (3, 1) is a 2-permutation (arrangement of 2 elements) from S . Permutations and Arrangements (1) (10)

14. Theorem: Number of r -Permutations of n Elements The number of r -permutations (arrangements of r elements from a set of n elements) is given by: P( n , r ) = n ( n −1)( n −2)…( n − r +1) For the special case where r = n : P( n , n )=n! Example: If 3 people (A, B, C) are arranged in 3 seats , the number of ways to arrange them is: 3!=63! = 63!=6 The possible arrangements are: ABC, ACB, BAC, BCA, CAB, CBA Permutations and Arrangements (2) (10)

15. The Traveling Salesman Problem (TSP) is a classic optimization problem in computer science and operations research. It is defined as follows: 📌 Problem Statement: A salesman needs to visit n cities exactly once and return to the starting city. The goal is to find the shortest possible route that visits all cities and returns to the starting point. Permutations and Arrangements (3) (

16. Illustration of Combinatorial Explosion in the TSP Problem 🚀 Combinatorial explosion occurs when the number of possible permutations in the Traveling Salesman Problem (TSP) increases exponentially as the number of cities increases. Example of Permutations ( n !) With 𝑛 cities, the number of possible routes is given by the permutation of 𝑛 cities, which is: (𝑛−1)! = (𝑛−1)×(𝑛−2)×...×2×1 𝑛=5 cities → 4!=24 routes 𝑛=10 cities → 9!=362,880 routes 𝑛=20 cities → 19!≈1.2×10 17 routes 🚀 𝑛=50 cities → 49!≈3.04×10 62 routes 😱 💡 Observation : As 𝑛 increases, the number of possible routes explodes exponentially, quickly exceeding the computational power of any computer! Permutations and Arrangements (4) (

17. Illustration of Combinatorial Explosion in the TSP Problem 🚀 Let’s analyze the time required to solve TSP on a modern computer (~1 billion operations/second): Permutations and Arrangements (5) ( Number of Cities (n) Number of Possible Routes ((𝑛−1)!) Time Required (assuming 1 billion operations/second) 10 362,880 0.00036 seconds 15 87,178,291,200 87 seconds 20 1.2×10 17 3,805 years 🤯 50 3.04×10 62 Longer than the age of the universe! 🌌

18. Exercise : How many ways are there to arrange 8 people around a circular table, considering two arrangements identical if one can be obtained from the other by rotating the table? Permutations and Arrangements (6) (

19. A combination of 𝑟 elements from a set is a way of selecting 𝑟 elements from the given set without considering order. Given 𝑆={1,2,3,4,5}, the subset {1,3,4} is a combination of 3 elements from 𝑆. Example 1: Randomly selecting 2 people from 3 individuals A, B, C . The possible selections are AB, AC, BC. Combination (1) (

20. Exercise : How many ways are there to draw 5 cards from a standard 52-card deck such that the hand contains exactly 3 Aces and 2 Tens? Combination (2) (

21. Exercise : A club has 25 members. How many ways can 4 members be selected for the standing committee? How many ways can a president, vice president, secretary, and treasurer be chosen? Combination (3) (

22. Theorem 1: If k +1 (or more) objects are placed into k boxes, then at least one box must contain at least two objects. Example: In a group of 367 people , at least two people must have the same birthday (since there are only 366 possible birthdays, including February 29). Theorem 2: If k objects are placed into b boxes, then at least one box must contain at least ⌈ k / b ⌉ objects . Example: Among 100 people , at least ⌈100/12⌉=9 people must have been born in the same month. Pigeonhole Principle (1) (

23. In a set of n +1 distinct positive integers, all of which do not exceed 2 n , there always exist two numbers that are relatively prime (i.e., their greatest common divisor is 1). Pigeonhole Principle (2) (

24. Test and event Definition of probability Relationships between events Probability of event combinations Discrete probability (

25. To observe random phenomena, these phenomena are repeated multiple times. Conducting an observation of a random phenomenon to determine whether it occurs is called a test . When performing a test, the outcome cannot be predicted in advance. However, all possible outcomes can be listed. The set of all possible outcomes of a trial is called the sample space of that trial, denoted as Ω . Each ω ∈ Ω is called an elementary event . Each subset A ∈ Ω is called an event . Test and event (1) (

26. Rolling a die is a test . The set of all faces of the die (each face represented by the number of dots) forms the sample space : Ω ={1,2,3,4,5,6} The elements ω 1 = 1, ω 2 = 2, … , ω 6 = 6 are elementary events . Subsets of Ω are events . In a test, an event that is certain to occur is called a certain event , denoted by Ω . An event that cannot occur is called an impossible (empty) event , denoted by Φ . Test and event (2) (

27. Assuming the equal likelihood of elementary events (i.e., all possible outcomes have the same probability), the probability of an event A is a non-negative number, denoted as P(A) which represents the likelihood of A occurring and is defined as follows: P(A)= m / n ​ where: m is the number of favorable outcomes for A. n is the total number of possible outcomes when the test is conducted. Elementary events that, when they occur, imply the occurrence of A are called favorable outcomes for A . Accordingly: P(Φ)=0 (the probability of the impossible event is zero). P(ω)=1 (the probability of the certain event is one). 0≤P(A)≤1. Definition of probability (classical form) (

28. Example 1 : A closed box contains 4 blue balls and 5 red balls. Calculate the probability of randomly drawing a blue ball from the box. Example 2: Randomly draw 8 cards from a standard deck of 52 playing cards . Find the probability that the drawn cards include: 3 Aces, 2 Tens, 1 Two, 1 King, and 1 Jack . 2 Hearts, 1 Diamond, 2 Spades, and 3 Clubs . 5 red cards and 3 black cards . Examples (

29. Example 3: There are 5 square cards, each labeled with a letter: A, I, H, O, N. These cards are randomly arranged in a horizontal row.Find the probability of forming the word HANOI. Examples (

30. Implication Relationship : Event A is said to imply event B, denoted as A⊂B, if and only if the occurrence of A implies the occurrence of B (i.e., A is a subset of B). Equivalence Relationship : Two events A and B are called equivalent, denoted as A = B, if and only if A⊂B and B⊂A. Union of Two Events : The union of two events A and B, denoted as A∪B, is the event that occurs if and only if either A occurs, or B occurs, or both occur. Intersection of Two Events : The intersection of two events A and B, denoted as AB or A∩B, is the event that occurs if and only if both A and B occur. Mutually Exclusive Events : A and B are said to be mutually exclusive events if AB=∅ (i.e., they cannot occur at the same time). Complementary Event : The complementary event (or the complement) of event A is denoted as A‾, where A‾ = Ω∖A. Relationship between events (

31. Relationship between events ( Example : Two people each shoot one bullet at a target. Let A i = {person  i  hits the target}, for i = 1, 2.

32. Probability of event combinations (

33. Probability of event combinations ( Example 1 : A 10-bit binary string is randomly generated. Find the probability that the string contains at least one 0. Example 2 : Find the probability that a randomly selected positive integer from the set of all positive integers not greater than 100 is divisible by 2 or by 5.

34. Relationship between events ( Example : Two people each shoot one bullet at a target. Let A i = {person  i  hits the target}, for i = 1, 2. P(A 1 ​)=0.9, P(A 2 )=0.8. calculate the following probabilities:

35. A shooter has 5 bullets and fires them one by one at a target, with a probability of hitting the target being 0.9. If the shooter stops after hitting 3 consecutive shots or running out of bullets, calculate the probability of firing exactly 3, 4, and 5 bullets. If the shooter stops after hitting 3 shots in total, calculate the probability of firing exactly 3, 4, and 5 bullets. Exercise (

36. (1) Calculate the probability that a randomly chosen card from a deck is an Ace. (2) Calculate the probability that a randomly selected integer from the first 100 positive integers is an odd number. (3) Calculate the probability of the event "the sum of the numbers on two dice rolled simultaneously is an even number." Exercises (

37. Permutations with Repetition (Repeated Arrangements) Problem: Find the probability of drawing 3 consecutive red balls from a closed urn containing 5 red balls and 7 blue balls , given that each drawn ball is returned to the urn after selection. Solution: Since sampling is with replacement , the probability is: 5 3 /12 3 Theorem: The number of r-permutations with repetition of n elements is given by: n r Extended Permutations and Combinations (1) (

38. Combinations with Repetition Example 1: Suppose a fruit tray contains apples, oranges, and pears , with at least 4 of each type available. How many ways can we select 4 fruits from the tray if: The order of selection does not matter . Fruits of the same type are indistinguishable . Extended Permutations and Combinations (2) (

39. Explanation of the Problem This is a combinations with repetition problem because: There are 3 types of fruits : apples, oranges, and pears. We need to select 4 fruits , where fruits of the same type are indistinguishable , and the order of selection does not matter . The problem is equivalent to distributing 4 identical fruits among 3 groups (apples, oranges, pears). This can be represented using the stars and bars method , where: 4 fruits are represented by 4 stars (****) . Dividing them into 3 categories is represented by 2 vertical bars (||) . For example, choosing (2 apples, 1 orange, 1 pear) can be represented as: ∗∗∣∗∣∗ where: The first two stars represent apples. The third star represents an orange. The last star represents a pear. Extended Permutations and Combinations (2) (

40. Theorem : The number of combinations with repetition of r elements chosen from n elements is given by: C( n + r −1, r ) Extended Permutations and Combinations (3) (

41. Combinations with Repetition Example 2: How many ways can 5 banknotes be selected from a cash register containing 1, 2, 5, 10, 20, 50, and 100-dollar bills , assuming: The order of selection does not matter . Banknotes of the same denomination are indistinguishable . Extended Permutations and Combinations (4) (

42. Combinations with Repetition Example 3: A biscuit shop offers 4 different types of biscuits. How many ways are there to choose 6 boxes of biscuits? Assume that we only care about the types of biscuits selected, not the specific boxes or the order in which they are chosen. Extended Permutations and Combinations (5) (

43. Combinations with Repetition Exercise 1: How many non-negative integer solutions does the equation 𝑥 1 +𝑥 2 +𝑥 3 =11 have? Extended Permutations and Combinations (6) (