10. Basic Rules of Counting

Counting is a very fundamental problem in discrete mathematics. The reason is that in discrete mathematics we are dealing with discrete objects and since the objects that we are dealing with are discrete we can count them. So very often we will encounter questions like how many; and our main aim is to come up with methodologies to address those questions.

Counting in discrete mathematics involves quantifying distinct objects. When we say discrete objects, we mean items that can be counted separately, like integers or individual items in a set. The aim is to develop methods to find answers to questions about how many objects there are in different scenarios, which is fundamental to many areas in mathematics and computer science.

Think about counting students in a classroom. Each student represents a discrete object. You can count them individually: there can be 10 students, 15 students, or fewer. Just as in counting students, we often face similar questions in mathematics about different sets or arrangements of items.

The first basic rule is the product rule. Suppose we have 2 employees, employee number 1 and employee number 2, and there are 3 office spaces available. This means we can allocate disjoint offices to these 2 employees. In total, we have 6 ways to do this.

The product rule states that if one task can be performed in 'm' ways and a second independent task can be performed in 'n' ways, then the total number of ways to perform both tasks is 'm * n'. In our example, assigning the first employee has 3 options (offices 1, 2, or 3), and for each assignment, the second employee has 2 remaining options. Therefore, the total combinations are 3 * 2 = 6.

Imagine you are choosing a sandwich and a drink for lunch. If you have 3 types of sandwiches (e.g., ham, turkey, vegetarian) and 2 types of drinks (e.g., soda, juice), the total combinations of meals you can have are 3 (sandwiches) * 2 (drinks) = 6 different lunch combinations.

If you have a larger task that can be divided into multiple subtasks, the product rule generalizes to say that if you can solve the first subtask in 'a' ways and the second in 'b' ways and so on, then the total number of ways to solve the entire task is 'a * b * ...'.

The generalized product rule expands the product rule to any number of tasks. If for each subtask, there are specific ways to accomplish it, you multiply all those individual ways together. This gives you a comprehensive count of all potential outcomes for the main task.

Consider planning a vacation where you have multiple decisions: the choice of destination, mode of transport, and type of accommodation. If there are 4 destinations, 3 transport options, and 2 types of accommodation, the total combinations for planning your vacation would be 4 * 3 * 2 = 24 different vacation plans.

Now let us see another counting rule which is the sum rule. Imagine you have a set of students and a set of faculty members, and our goal is to find out the number of ways in which we can form a committee of just 1 member.

The sum rule states that if you can do task A in 'm' ways and task B in 'n' ways, and A and B cannot happen at the same time (they are disjoint), then the total number of ways to do either A or B is 'm + n'. In this example, if there are 7 students and 5 faculty members, you can form a committee by choosing one member from either group resulting in 7 + 5 = 12 distinct committees.

Think about selecting a fruit for a snack. If you can choose from 3 apples and 4 bananas, the total number of fruit snack options you have is simply 3 (for apples) + 4 (for bananas) = 7 options. You can either pick an apple or a banana, so we use the sum rule.

We may encounter problems that require us to apply both the sum rule and the product rule.

In more complex scenarios, you may face situations where you need to use both counting rules simultaneously. For example, if you want to form valid passwords of varying lengths with restrictions, you might first use the product rule to count the possible characters for each position and then the sum rule to total the different lengths. This combination helps in addressing multifaceted counting questions systematically.

Imagine you're creating pin numbers. The pin can be either 4 digits or 6 digits. For each digit, you can use numbers 0-9. For each configuration length, you calculate options per rule and then sum them for the total. It’s like choosing whether to wear a hat or sunglasses based on the outfit you want to wear.

The pigeon-hole principle states if you have more pigeons than holes, at least one hole must contain more than one pigeon.

The pigeon-hole principle provides a straightforward insight into distribution: if you try to put more items than you have containers, some containers must end up holding multiple items. It can be illustrated through proofs by contradiction, emphasizing the basic concept of allocation and arrangement.

Consider a box of 13 chocolates divided among 12 friends. If each friend takes at least one chocolate, at least one friend will end up with two. This simple scenario highlights the principle that you cannot distribute more units than available spots without causing overlap.

--