CU-BCA-SEM-I-Mathematics

301 CU IDOL SELF LEARNING MATERIAL (SLM)

302 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: Solution: 303 CU IDOL SELF LEARNING MATERIAL (SLM)

304 CU IDOL SELF LEARNING MATERIAL (SLM)

305 CU IDOL SELF LEARNING MATERIAL (SLM)

306 CU IDOL SELF LEARNING MATERIAL (SLM)

10.4 SUMMARY ● A feasible solution to a linear program is a solution that satisfies all constraints. ● An optimal solution to a linear program is the feasible solution with the largest objective function value (for a maximization problem) ● A linear program is infeasible if there exists no solution that satisfies all of the constraints -- in other words, if no feasible solution can be constructed ● A solution region of a system of linear inequalities is bounded if it can be enclosed within a circle. If it cannot be enclosed within a circle, it is unbounded. 307 CU IDOL SELF LEARNING MATERIAL (SLM)

10.5 KEYWORD • Corner (or Extreme) Point. A point that lies on one of the corners of the feasible region. This means that it falls at the intersection of two constraint lines. • Corner Point Method. The method of finding the optimal solution to an LP problem by testing the profit or cost level at each corner point of the feasible region. The theory of LP states that the optimal solution must lie at one of the corner points. • Decision Variables. The unknown quantities in the problem for which optimal solution values are to be found • Infeasibility. A condition that arises when there is no solution to an LP problem that satisfies all of the constraints. 10.6 LEARNING ACTIVITY 1. Consider a chocolate manufacturing company that produces only two types of chocolate – A and B. Both the chocolates require Milk and Choco only. To manufacture each unit of A and B, the following quantities are required: Each unit of A requires 1 unit of Milk and 3 units of Choco Each unit of B requires 1 unit of Milk and 2 units of Choco The company kitchen has a total of 5 units of Milk and 12 units of Choco. On each sale, the company makes a profit of Rs 6 per unit A sold 308 CU IDOL SELF LEARNING MATERIAL (SLM)

Rs 5 per unit B sold. Now, the company wishes to maximize its profit. How many units of A and B should it produce respectively? ___________________________________________________________________________ ___________________________________________________________________________ 2.A toy Company manufactures two types of doll, a basic version –doll A and a deluxe version-doll B. Each doll of type B takes twice as long to produce as one of type A, and the company have time to make a maximum of 2000 per day. The supply of plastic is sufficient to produce 1500 dolls per day (both A and B combined). The deluxe version requires a fancy dress of which there are only 600 per day available. If the company makes a profit of Rs.3.00 and Rs.5.00 per doll, respectively on doll A and B, then how many of each doll should be produced per day in order to maximize the total profit. Formulate this problem and discuss the components of decision problem. ___________________________________________________________________________ _____________________________________________________________________ 10.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is bounded and unbounded solution in LPP? 2. How can you say the LPP has an unbounded solution? 309 CU IDOL SELF LEARNING MATERIAL (SLM)

3. What is a optimal solution? 4. What is basic feasible solution in simplex method? 5. What is degenerate basic feasible solution? Long Questions 1. A bolt manufacturing organization manufactures two types of toys A and B. Both the bolts are sold at Rs.25 and Rs.20 respectively. There are 2000 resource units available every day from which the bolt A requires 20 units while bolt B requires 12 units. Both of these toys require a production time of 5 minutes. Total working hours are 9 hours a day. What should be the manufacturing quantity for each of the pipes to maximize the profits? 2. Solve to maximize the profit function Z = 40x + 15y, subject to constraints, (a) x+2y ≤ 100 x+2y ≤ 70 x, y ≥ 0 3. Examine the Linear programming problem. Maximize Z = 3x1 + 5x2 Subject to x1 + x2 ≤ 8, x1 + 3x2 ≤12 x1 , x2 ≥ 0. 310 CU IDOL SELF LEARNING MATERIAL (SLM)

4. Solve the following LPP by graphical Method. Maximize Z = 3x1 + 2x2 Subject to -2x1 + x2 ≤ 1, x1 ≤2 x1 + x2 ≤ 3, x1 , x2 ≥ 0. 5. A company manufactures two types of products P1, P2.Each product uses lathe and Milling machine. The processing time per unit of P1 on the lathe is 5 hours and on the milling machine is 4 hours. The processing time per unit of P2 on the lathe is 10 hours and on the milling machine, 4 hours. The maximum number of hours available per week on the lathe and the milling machine are 60 hours and 40 hours, respectively. Also the profit per unit of selling P1 and P2 are Rs.6.00 and Rs.8.00, respectively. Create a linear programming model to determine the production volume of each of the products such that the total profit is maximized. and also solve. B. Multiple Choice Questions 1. Which technique is used in finding a solution for optimizing a given objective, such as profit maximization or cost reduction under certain constraints? a. Quailing Theory b. Waiting Line 311 CU IDOL SELF LEARNING MATERIAL (SLM)

c. Both A and B d. Linear Programming 2. What have been constructed from OR problems an methods for solving the models that are available in many cases? a. Scientific Models b. Algorithms c. Mathematical Models d. None of these 3. What is the objective function in linear programming problems? a. A constraint for available resource b. An objective for research and development of a company c. A linear function in an optimization problem d. A set of non-negativity conditions 4. Which statement characterizes standard form of a linear programming problem? a. Constraints are given by inequalities of any type b. Constraints are given by a set of linear equations c. Constraints are given only by inequalities of >= type d. Constraints are given only by inequalities of <= type 312 CU IDOL SELF LEARNING MATERIAL (SLM)

5. Feasible solution satisfies __________ a. Only constraints b. only non-negative restriction c. [a] and [b] both d. [a],[b] and Optimum solution Answers 1-d, 2-c, 3-c. 4-a, 5-c 10.8 REFERENCES References book ● Taha, H.A., “Operations Research: An Introduction”, 9th Edition, Pearson Education, Asia, New Delhi, 2016. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. ● Hennoy G.V. and Srivastava U.K., “Operation Research for Management”, Wiley Eastern,1994. 313 CU IDOL SELF LEARNING MATERIAL (SLM)

● Bazara M.J., Jarvis and Sherali H., “Linear Programming and Network Flows”, John Wiley,1990. ● Philip D.T. and Ravindran A., “Operations Research”, John Wiley, 1992. ● Hillier and Libeberman, “Operations Research”, Holden Day, 1986. 314 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 11: COMBINATIONS 1 STRUCTURE 11.0 Learning Objectives 11.1 Introduction 11.2 Basics of counting Principle 11.3 Permutations. 11.4 Summary 11.5 Keywords 11.6 Learning Activity 11.7 Unit End Questions 11.8 References 11.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Learn to Set up and compute factorials ● Apply and calculate permutations ● Learn to count using the fundamental counting principle ● Describe the notion of permutations. ● Explain to Count in accordance with the basic counting principle 315 CU IDOL SELF LEARNING MATERIAL (SLM)

11.1 INTRODUCTION A new startup sells tablet and smartphone cases that may be customised. Each case is available in a range of colours and may be personalised with photos or a monogram for an extra charge. Customers can opt to have no personalization or one, two, or three photos or a monogram. The order of the photos and letters in the monogram can be customised by the buyer. The company is collaborating with a marketing agency to create a campaign that highlights the vast array of possibilities available. It's difficult to keep track of all the choices! Every day, we come across a wide range of counting challenges. This type of counting problem is studied in an area of mathematics called combinatorics. Other applications of counting include secure passwords, horse racing outcomes, and college scheduling choices. We will examine this type of mathematics in this section. The Counting Principle: Consider option A, which has three alternatives (A1,A2,A3), and option B, which has two options (B1,B2). The total number of alternatives would be 32=6 if you had to choose an option from A and then an option from B. A1B1, A1B2, A2B1, A2B2, A3B1, A3B2 are the alternatives. Using the Fundamental Counting Principle and a decision tree, you can figure out where the 6 comes from. A decision tree is a graph that represents the many alternatives available at each stage of a study. To create a decision tree, first figure out how many decisions you'll be making. There are only two options available here: You will have two \"slots\" in your choice tree if you 1) choose an option from A and 2) choose an option from B. 316 CU IDOL SELF LEARNING MATERIAL (SLM)

Next, think about how many possibilities there are for the 1st choice (in this case there are 3), and how many possibilities there are for the 2nd choice (in this case there are 2). The Fundamental Counting Principle says that you can multiply those numbers together to get the total number of outcomes. The Multiplication Principle can be used to solve a variety of problem types. One type of problem involves placing objects in order. We arrange letters into words and digits into numbers, line up for photographs, decorate rooms, and more. An ordering of objects is called a permutation. For some permutation problems, it is inconvenient to use the Multiplication Principle because there are so many numbers to multiply. Fortunately, we can solve these problems using a formula. Before we learn the formula, let’s look at two common notations for permutations. If we have a set of n objects and we want to choose r objects from the set in order, we write P(n,r). Another way to write this is nPr, a notation commonly seen on computers and calculators. To calculate P(n, r), we begin by finding n!, the number of ways to line up all n objects. We then divide by (n−r)! to cancel out the (n−r) items that we do not wish to line up. Let’s see how this works with a simple example. Imagine a club of six people. They need to elect a president, a vice president, and a treasurer. Six people can be elected president, any one of the five remaining people can be elected vice president, and any of the remaining four people could be elected treasurer. The number of ways this may be done is 6×5×4=120. Using factorials, we get the same result. 317 CU IDOL SELF LEARNING MATERIAL (SLM)

6!3!=6⋅5⋅4⋅3!3!=6⋅5⋅4=120 There are 120 ways to select 3 officers in order from a club with 6 members. We refer to this as a permutation of 6 taken 3 at a time. The general formula is as follows. P(n, r)=n!/(n−r)! 11.2 THE FUNDAMENTAL COUNTING PRINCIPLE Definition of n Factorial: (n !)n! = n(n-1)(n-2)(n-3)…1 For example, 5! = 5(4)(3)(2)(1) = 1200! = 1 by definition. Fundamental counting Principle: Recall that the theoretical probability of an event E is P(E)=number of outcomes in E / size of sample space. To compute such probabilities, we must be able to enumerate the number of possible possibilities. This isn't always easy. Assume you're dealt a five-card draw poker hand from a normal deck. What is the sample space's size, or the total number of possible hands? We’ll have three counting techniques. The simplest, and the foundation for many more sophisticated techniques, is the Fundamental Counting Principle, sometimes called the Multiplication Rule. It is very simple: if there are m ways to do a task, say, Task 1, and n ways to then do another task, Task 2, then there are m⋅n ways to do first Task 1 and then Task 2. Example 1: 318 CU IDOL SELF LEARNING MATERIAL (SLM)

John wants to give a novel and a cookbook to his friend. He has four different novels and three different cookbooks to choose from. How many different choices can he make? Solution: John has two assignments: choose a novel and a cookbook. He has four distinct novels from which to choose, so he has four options; he has three recipes from which to choose, so he has three options. As a result, he has 43=12 options for selecting a novel and subsequently a cookbook. Example 2: The Thursday special at Lisa’s Pizza is a large pizza with any combination of toppings (but no more than one of each). The available toppings are pepperoni, mushrooms, onions, sausage, peppers, olives, and pineapple. How many different Thursday specials can be ordered? Solution: Think of ordering a Thursday special as a sequence of seven different tasks: choose whether or not to have pepperoni, then choose whether or not to have mushrooms, and so on. There are two choices for each task, so there are 2⋅2⋅2⋅2⋅2⋅2⋅2=27=128 different ways to order. Example 3: You are going on a road trip with 4 friends in a car that fits 5 people. How many different ways can everyone sit if you have to drive the whole way? 319 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: The Fundamental Counting Principle is an excellent way to approach this issue. You must take the wheel of the vehicle. For the first passenger seat, there are four alternatives. There are three alternatives for the next passenger seat once that individual is seated. This goes on until there is one person left with 1 seat. 1⋅4⋅3⋅2⋅1=24 Example 4: How many different 4-digit ATM passwords are there? Assume you can repeat digits. Solution: It is true that order is important. There are ten digits, and you can repeat them as many times as you want. Each of the four alternatives may be solved using the Fundamental Counting Principle. 10⋅10⋅10⋅10=10,000 320 CU IDOL SELF LEARNING MATERIAL (SLM)

11.3 PERMUTATION Definitions: A permutation of some objects is an arrangement of those objects in a definite order. For any positive integer n, we define n factorial, denoted n!, to be the product of all the positive integers up to and including n itself. That is, n!=n(n−1)(n−2)⋯(2)(1) Number of Permutations: The number of permutations of r objects chosen from among n different objects is nPr=n!/(n−r)! Example 1: It is obvious that if you have two different pool balls, there are two ways to arrange them in a row: But what if there were three balls, or four, or twelve? Consider placing the balls as a sequence of two tasks: first choose the left ball, then choose the right ball to see how to find the answer for any number of balls. There are two options for the left ball, but only one for the right, so there are a total of 2 1=2 ways to arrange the balls. Similarly, if you have three balls, you can arrange them in any of the following ways: 321 CU IDOL SELF LEARNING MATERIAL (SLM)

An arrangement of objects in a definite order is called a permutation of those objects. We’ve just seen that there are two possible permutations of two different objects and six possible permutations of three different objects. These examples make it clear that if we have n different objects, then there are n(n−1)(n−2)⋯(2)(1) possible permutations of those objects. Clearly there are n! possible permutations of n different objects. We need to push this just a little further. Suppose we have five pool balls and a box with only three slots. Assuming that the order of the balls in the box matters, in how many different ways could we choose three balls to put in the box? This is not much different from the earlier question: we have five choices for the first ball, then four for the second, and then three for the third, so there are 5⋅4⋅3=60 ways to choose the three balls. Notice that 5⋅4⋅3=5!/(5−3)!, which leads to the following formula: So, for example, 5P3=5!/(5−3)!=5⋅4⋅3=60. Note: Sometimes nPr is written P(n,r). You need to know both notations. The notation P(n,r) represents the number of permutations (arrangements) of n objects taken r at a time, where r is less than or equal to n. In a permutation, the order is important P(n,r) may also be written P(n,r) or nPr 322 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 2: In our example with the number of two letter words from {p, e, n}, the answer is P3,2, which represents the number of permutations of 3 objects taken 2 at a time.P3,2 = 6 How many different ways can the gold, silver, and bronze medals be awarded in an Olympic event with 12 athletes competing? Solution: Since the order does matter with the 3 medals, this is a permutation problem. You will start with 12 athletes and then choose and arrange 3 different winners. 12P3=12!(12−3)!=12!9!=12⋅11⋅10⋅9⋅…9⋅…=12⋅11⋅10=1,32012P3=12!(12−3)!=12!9!=12⋅11⋅ 10⋅9⋅…9⋅…=12⋅11⋅10=1,320 You may also use the Fundamental Counting Principle to figure out how many gold possibilities there are (12), how many silver possibilities there are (11, since one already 323 CU IDOL SELF LEARNING MATERIAL (SLM)

possesses gold), and how many bronze possibilities there are (10). Any permutation problem can be solved using the Fundamental Counting Principle. 12⋅11⋅10=1,320 Example 3: How many outcomes are possible when three dice are rolled, if no two of them may be the same? Solution: The first two dice together have 6 · 5 = 30 possible outcomes, from above. For each of these 30 outcomes, there are four possible outcomes for the third die, so the total number of outcomes is 30 · 4 = 6 · 5 · 4 = 120. (Note that we consider the dice to be distinguishable, that is, a roll of 6, 4, 1 is different than 4, 6, 1, because the first and second dice are different in the two rolls, even though the numbers as a set are the same.) Example 4: Suppose blocks numbered 1 through n are in a barrel; we pull out k of them, placing them in a line as we do. How many outcomes are possible? That is, how many different arrangements of k blocks might we see? Solution: 324 CU IDOL SELF LEARNING MATERIAL (SLM)

This is essentially the same as the previous example: there are k “spots” to be filled by blocks. Any of the n blocks might appear first in the line; then any of the remaining n − 1 might appear next, and so on. The number of outcomes is thus n(n−1)(n−2)· · ·(n−k+1), by the multiplication principle. In the previous example, the first “spot” was die number one, the second spot was die number two, the third spot die number three, and 6 · 5 · 4 = 6(6 − 1)(6 − 2); notice that 6 − 2 = 6 − 3 + 1. This is quite a general sort of problem: Example 5: The number of permutations of n things taken k at a time is P(n, k) = n(n − 1)(n − 2)· · ·(n − k + 1) = n! /(n − k)!. A permutation of some objects is a particular linear ordering of the objects; P(n, k) in effect counts two things simultaneously: the number of ways to choose and order k out of n objects. A useful special case is k = n, in which we are simply counting the number of ways to order all n objects. This is n(n − 1)· · ·(n − n + 1) = n!. Note that the second form of P(n, k) from the definition gives n! /(n − n)! = n!/ 0! . This is correct only if 0! = 1, so we adopt the standard convention that this is true, that is, we define 0! to be 1. Suppose we want to count only the number of ways to choose k items out of n, that is, we don’t care about order. 325 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 6: How many ways are there to line up six people so that a particular pair of people are not adjacent? Solution: Denote the people A and B. The total number of orders is 6!, but this counts those orders with A and B next to each other. How many of these are there? Think of these two people as a unit; how many ways are there to line up the AB unit with the other 4 people? We have 5 items, so the answer is 5!. Each of these orders corresponds to two different orders in which A and B are adjacent, depending on whether A or B is first. So the 6! count is too high by 2 · 5! and the count we seek is 6! − 2 · 5! = 4 · 5!. Example 7: Six people are to sit at a round table; how many seating arrangements are there? Solution: It is not clear exactly what we mean to count here. If there is a “special seat”, for example, it may matter who ends up in that seat. If this doesn’t matter, we only care about the relative position of each person. Then it may or may not matter whether a certain person is on the left or right of another. So this question can be interpreted in (at least) three ways. Let’s answer them all. First, if the actual chairs occupied by people matter, then this is exactly the same as lining six people up in a row: 6 choices for seat number one, 5 for seat two, and so on, for a total of 6!. If the chairs don’t matter, then 6! Counts the same arrangement too many times, once for each person who might be in seat one. So the total in this case is 6!/6 = 5!. 326 CU IDOL SELF LEARNING MATERIAL (SLM)

Another approach to this: since the actual seats don’t matter, just put one of the six people in a chair. Then we need to arrange the remaining 5 people in a row, which can be done in 5! ways. Finally, suppose all we care about is who is next to whom, ignoring right and left. Then the previous answer counts each arrangement twice, once for the counterclockwise order and once for clockwise. So the total is 5!/2 = P(5, 3). We have twice seen a general principle at work: if we can over count the desired set in such a way that every item gets counted the same number of times, we can get the desired count just by dividing by the common over count factor. This will continue to be a useful idea. A variation on this theme is to over count and then subtracts the amount of over count. 11.4 SUMMARY • Fundamental principle of counting :If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrence of the events in the given order is m × n. ®The number of permutations of n different things taken r at a time, where repetition is not allowed, is denoted by nPr and is given by nPr = , where 0 ≤ r ≤ n. • n! = 1 × 2 × 3 × ...×n .n! = n × (n – 1) ! The number of permutations of n different things, taken r at a time, where repetition is allowed, is n r . • The number of permutations of n objects taken all at a time, where p1 objects. According to the Fundamental Counting Principle, if one event has m possible 327 CU IDOL SELF LEARNING MATERIAL (SLM)

outcomes and a second event has n possible outcomes, the two occurrences together have mn total possible possibilities. • A permutation is the number of possible combinations for selecting and arranging k things from a set of n objects. nPk=k!(n, k)=k!⋅(n!/k!(n−k)!)=n!/(n−k)! 11.5 KEYWORD ● Permutation: a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order. ● Combination: A combination is a mathematical technique that determines the number of possible arrangements in a collection of items where the order of the selection does not matter. ● Factorial: the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n:. ● Fundamental principle of counting: The fundamental counting principle is a rule used to count the total number of possible outcomes in a situation ● Pigeon hole principle: Suppose that n+1 (or more) objects are put into n boxes. Then some box contains at least two objects. 11.6 LEARNING ACTIVITY 1. How many ways can all nine swimmers line up for a photo? 328 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ _____________________________________________________________________ 2. Explain how 0!=1 ? ___________________________________________________________________________ _____________________________________________________________________ 11.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Simplify each of the following expressions so that they do not have a factorial symbol 7!3! 110!105!5! 2. Simplify each of the following expressions so that they do not have a factorial symbol 52!49! 3. In how many ways can you choose 3 objects from a set of 9 objects? 4. In how many ways can you choose and arrange 4 objects from a set of 15 objects? 5. First state whether each problem is a permutation/decision tree problem or a combination problem. Long Questions 329 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Suppose you need to choose a new combination for your combination lock. You have to choose 3 numbers, each different and between 0 and 40. How many permutations are there? 2. You just won a contest where you can choose 2 friends to go with you to a concert. You have 5 friends who are available and want to go. In how many ways can you choose the friends? 3. You want to construct a 3-digit number from the digits 4, 6, 8, 9. How many possible numbers are there? 4. There are 12 workshops at a conference, and Sam has to choose 3 to attend. In how many ways can he choose the 3 to attend? 5. A contest has 9 girls and 5 boys as finalists. In how many ways can 1st-, 2nd-, and 3rd-place winners be chosen? B. Multiple Choice Questions 1. In how many ways can 4 books be chosen from a group of nine? a. 126 b. 127 c. 125 d. 124 2. A restaurant offers butter, cheese, chives, and sour cream as toppings for a baked potato. How many different ways are there to order a potato? 330 CU IDOL SELF LEARNING MATERIAL (SLM)

a. 15 b. 16 c. 14 d. 13 3. A person going to a party was asked to bring 3 different bags of chips. Going to the store, she finds 12 varieties. a. 220 b. 215 c. 210 d. 225 4. How many ways can you select your side dishes? a. 15 b. 10 c. 20 d. 25 5. How many ways can you select 3 side dishes? a. 10 b. 15 331 CU IDOL SELF LEARNING MATERIAL (SLM)

c. 20 d. 25 6. Find the number of distinguishable permutations of the given letters \"AABCCDDD\". a. 1690 b. 1780 c. 1680 d. 1790 Answers 1-a, 2-b, 3-a. 4-b, 5-a, 6- c 11.8 REFERENCES References book ● Kenneth H. Rosen, ”Discrete Mathematics and its Applications”, 7th Edition, Tata McGraw – Hill Pub. Co. Ltd, New Delhi, 2011. ● Vittal, P.R, “Allied Mathematics”, Reprint,Margham Publications, Chennai. ● Venkata chalapathy, S.G, “Allied Mathematics”, Margham Publications, Chennai. Textbook references ● Singaravelu, A. “Allied Mathematics”, Meenakshi Agency, Chennai. 332 CU IDOL SELF LEARNING MATERIAL (SLM)

● Thomas Koshy, “Elementary Number Theory with Applications”, Elsevier Publications, New Delhi, 2002. ● Tremblay J.P and Manohar R, “Discrete Mathematical Structures with Applications to Computer Science”, Tata McGraw–Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011. ● San Ling and Chaoping Xing, “Coding Theory – A first Course”, Cambridge Publications, Cambridge, 2004. 333 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 12: COMBINATIONS 2 STRUCTURE 12.0 Learning Objectives 12.1 Introduction 12.2 Combinations 12.3 Pigeonhole principle 12.4 Summary 12.5 Keywords 12.6 Learning Activity 12.7 Unit End Questions 12.8 References 12.0 LEARNING OBJECTIVES After studying this unit, you will be able to: ● Explain the likelihood of compound events and solving issues, correctly use permutations and combinations. ● Describe the likelihood of a compound event or solve a problem by calculating permutations and combinations ● Calculate and apply combinations 334 CU IDOL SELF LEARNING MATERIAL (SLM)

● Analyse permutations and combinations in applications. 12.1 INTRODUCTION We turn first to counting. While this sounds simple, perhaps too simple to study, it is not. When we speak of counting, it is shorthand for determining the size of a set, or more often, the sizes of many sets, all with something in common, but different sizes depending on one or more parameters. For example: how many outcomes are possible when a die is rolled? Two dice? n dice? As stated, this is ambiguous: what do we mean by “outcome”? Suppose we roll two dice, say a red die and a green die. Is “red two, green three” a different outcome than “red three, green two”? If yes, we are counting the number of possible “physical” outcomes, namely 36. If no, there are 21. We might even be interested simply in the possible totals, in which case there are 11 outcomes. Even the quite simple first interpretation relies on some degree of knowledge about counting; we first make two simple facts explicit. In terms of set sizes, suppose we know that set A has size m and set B has size n. What is the size of A and B together, that is, the size of A ∪ B? If we know that A and B have no elements in common, then the size A ∪ B is m + n; if they do have elements in common, we need more information. A simple but typical problem of this type: if we roll two dice, how many ways are there to get either 7 or 11? Since there are 6 ways to get 7 and two ways to get 11, the answer is 6 + 2 = 8. Though this principle is simple, it is easy to forget the requirement that the two sets be 12 Chapter 1 Fundamentals disjoint, and 335 CU IDOL SELF LEARNING MATERIAL (SLM)

hence to use it when the circumstances are otherwise. This principle is often called the addition principle. This principle can be generalized: if sets A1 through An are pairwise disjoint and have sizes m1, . . . mn, then the size of A1 ∪ · · · ∪An = ∑n i=1 mi . This can be proved by a simple induction argument. Why do we know, without listing them all, that there are 36 outcomes when two dice are rolled? We can view the outcomes as two separate outcomes, that is, the outcome of rolling die number one and the outcome of rolling die number two. For each of 6 outcomes for the first die the second die may have any of 6 outcomes, so the total is 6 + 6 + 6 + 6 + 6 + 6 = 36, or more compactly, 6 · 6 = 36. Note that we are really using the addition principle here: set A1 is all pairs (1, x), set A2 is all pairs (2, x), and so on. This is somewhat more subtle than is first apparent. In this simple example, the outcomes of die number two have nothing to do with the outcomes of die number one. Here’s a slightly more complicated example: how many ways are there to roll two dice so that the two dice don’t match? That is, we rule out 1-1, 2-2, and so on. Here for each possible value on die number one, there are five possible values for die number two, but they are a different five values for each value on die number one. Still, because all are the same, the result is 5 + 5 + 5 + 5 + 5 + 5 = 30, or 6 · 5 = 30. In general, then, if there are m possibilities for one event, and n for a second event, the number of possible outcomes for both events together is m · n. This is often called the multiplication principle. 336 CU IDOL SELF LEARNING MATERIAL (SLM)

In general, if n events have mi possible outcomes, for i = 1, . . . , n, where each mi is unaffected by the outcomes of other events, then the number of possible outcomes overall is ∏n i=1 mi . This too can be proved by induction. 12.2 COMBINATION Definitions: A combination of r objects chosen from among n different objects is a choice of the r objects without regard to order. The number of combinations of r objects chosen from among n different objects is nCr=n!/(n−r)!r! Other notations for nCr are C(n,r) and (rn). You need to know all these notations. Example 1: The order in which the balls ended up important in our previous cases. Order, on the other hand, isn't always important. Consider the following scenario: we have five pool balls and wish to chose four to toss in a bag. How many different ways could the four balls be chosen? Solution: Clearly, the only thing that matters is which balls are chosen, not which sequence they are chosen in. For example, if we choose Ball 2, Ball 3, Ball 1, and then Ball 4, we receive the same outcome as if we choose Ball 1, Ball 2, Ball 3, and then Ball 4. A combination is a choice like this where the order doesn't matter. Example 2: 337 CU IDOL SELF LEARNING MATERIAL (SLM)

Jerrold possesses a total of five pool balls. How many different ways can he select four balls for a bag? Solution: 5C4=5!4!(5−4)!=5, so there are five ways in which he can choose. Example 3: When a customer orders an entrée, he has the option of selecting three different side dishes. How many different side dish combinations can a consumer make if there are twelve to pick from? Solution: Because the order in which side dishes are ordered does not matter, this is a combinations problem. So there are 12C3=12!/3!(12−3)! =12⋅11⋅10⋅9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1/(3⋅2⋅1)(9⋅8⋅7⋅6⋅5⋅4⋅3⋅2⋅1) =12⋅11⋅10/3⋅2⋅1=660 different choices. Example 4: You are deciding which awards you are going to display in your room. You have 8 awards, but you only have room to display 4 awards. Right now you are not worrying about how to arrange the awards, so the order does not matter. How many ways could you choose the 4 awards to display? 338 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Since order does not matter, this is a combination problem. You start with 8 awards and then choose 4. 8C4=(8, 4)=8!/4!(8−4)! =8⋅7⋅6⋅54⋅3⋅2⋅1=7⋅2⋅5=70 Note that if you try to use the Fundamental Counting Principle with this question, you will need to do an extra step of reasoning. There are 8 options you could choose 1st, then 7 left, then 6, and lastly 5. 8⋅7⋅6⋅5=1,680 Example 5: With three letters and four numerals, how many Oregon licence plates could be made? Solution: The Fundamental Counting Principle with 7 spaces can represent a licence plate with 3 letters and 4 numerals. Because order matters with licence plates, you can employ the Fundamental 339 CU IDOL SELF LEARNING MATERIAL (SLM)

Counting Principle. The first position is a number, the following three are letters, and the next three are numbers. Repetition is permitted while selecting a licence plate. 10⋅26⋅26⋅26⋅10⋅10⋅10=263⋅104=175,760,000 This number is only approximate because, in reality, certain letter and number combinations are not allowed, some license plates have extra symbols, and some commercial and government license plates have more numbers, fewer letters, or blank spaces. Example 6: A professional NHL team has 20 players, two of whom are goaltenders. What is the maximum number of sets of five skaters and one goalkeeper that can be on the ice at the same time? Solution: The question asks for how many on the ice, implying that order does not matter. This is combination problem with 2 combinations. You need to choose 1 goalie out of a possible of 2, and choose 5 skaters out of a possible 18. (21)(185)=2⋅18!/5!⋅13!=17,136 Example 7: How many different ways could you score a 70% on a 10-question test, where each question is weighted equally and is either right or wrong? Solution: The order of the questions you got right does not matter, so this is a combination problem. (107)=10!/7!3!=120 Difference between Permutations and Combinations 340 CU IDOL SELF LEARNING MATERIAL (SLM)

Both problems involved arrangements of the same set {p, e, n}, taken 2 elements at a time, without allowing repetition. However, in the first problem, the order of the arrangements mattered since pe and ep are two different “words”. In the second problem, the order did not matter since pe and ep represented the same two-man crew. We counted this only once.The first problem was concerned with counting the number of permutations of 3 objects taken 2 at a time. The second problem was concerned with the number of combinations of 3 objects taken 2 at a time. 12.3 THE PIGEONHOLE PRNCIPLE Pigeonhole Principle: Suppose that n+1n+1 (or more) objects are put into nn boxes. Then some box contains at least two objects. Proof: Suppose each box contains at most one object. Then the total number of objects is at most 1+1+⋯+1=n1+1+⋯+1=n, a contradiction. This seemingly simple fact can be used in surprising ways. The key typically is to put objects into boxes according to some rule, so that when two objects end up in the same box it is because they have some desired relationship. For example: Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle 341 CU IDOL SELF LEARNING MATERIAL (SLM)

called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it. Example 1: Among any 13 people, at least two share a birth month. Solution: Label 12 boxes with the names of the months. Put each person in the box labeled with his or her birth month. Some box will contain at least two people, who share a birth month. Example 2: Suppose 5 pairs of socks are in a drawer. Picking 6 socks guarantees that at least one pair is chosen. 342 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Label the boxes by \"the pairs'' (e.g., the red pair, the blue pair, the argyle pair, Put the 6 socks into the boxes according to description. Example 3: If (Kn+1) pigeons are kept in n pigeon holes where K is a positive integer, what is the average no. of pigeons per pigeon hole? Solution: Average number of pigeons per hole = (Kn+1)/n = K + 1/n Therefore there will be at least one pigeonhole which will contain at least (K+1) pigeons i.e., [K +1/n] and remaining will contain at most K i.e., floor[k+1/n] pigeons. i.e., the minimum number of pigeons required to ensure that at least one pigeon hole contains (K+1) pigeons is (Kn+1) Example 4: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color? Solution: Apply pigeonhole principle. No. of colors (pigeonholes) n = 3 343 CU IDOL SELF LEARNING MATERIAL (SLM)

No. of marbles (pigeons) K+1 = 4 Therefore the minimum no. of marbles required = Kn+1 By simplifying we get Kn+1 = 10. Verification: ceil[Average] is [Kn+1/n] = 4 [Kn+1/3] = 4 Kn+1 = 10 i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10 Example 5: In a computer science department, a student club can be formed with either 10 members from first year or 8 members from second year or 6 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed? Solution: Example 6: 344 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Here in this we cannot blindly apply pigeon principle. First, we will see what happens if we apply above formula directly. From the above formula we have get answer 47 because 6 + 8 + 10 + 12 + 15- 5 + 1 = 47 But it is not correct. In order to get the correct answer, we need to include only blue, yellow and white balls because red and green balls are less than 9. But we are picking randomly so we include after we apply pigeon principle. i.e., 9 blue + 9 yellow + 9 white – 3 + 1 = 25 Given we are picking randomly, now we can get all the red and green balls before the above 25 balls. Therefore, we add 6 red + 8 green + 25 = 39 We can conclude that in order to pick 9 balls of same color randomly, one has to pick 39 balls from a box. 12.4 SUMMARY ● The number of possibilities to choose k objects from a total of n objects is called a combination. nCk=(nk)=n!/k!(n−k)! 345 CU IDOL SELF LEARNING MATERIAL (SLM)

● If the average number of pigeons per hole is “A,” and A is not an integer, then There are ceil[A] (smallest integer greater than or equal to A) birds in at least one pigeon hole. There are at most floor[A] (biggest integer less than or equal to A) pigeons in the remaining pigeon holes. • Put n items into k boxes. Then There is a box with at least n/k items. There is a box with at most n/k items • The Pigeonhole Principle doesn’t say which pigeons will be in the same hole 12.5 KEYWORD ● Pigeonhole principle: If n+1 or more pigeons occupy n pigeonholes, then at least one pigeonhole is occupied by more than one pigeon. ● Combinations: is a mathematical approach for calculating the number of potential configurations in a group of objects. 12.6 LEARNING ACTIVITY 1. How many four-digit numbers can be formed from the digits 1, 2, 3, 4, 5, 6 (Repetition of digits not allowed)? ___________________________________________________________________________ _____________________________________________________________________ 346 CU IDOL SELF LEARNING MATERIAL (SLM)

2. A person has 6 friends to be invited for dinner through invitation cards, and he has 3 servants. In how many ways can he extend the invitation card? ___________________________________________________________________________ ____________________________________________________________________ 12.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. A restaurant's special allows you to select three dishes from a 10-item menu. How many different food combos could you come up with? 2. You go to 12 colleges and decide to apply to only four of them. How many different ways might you pick the four to apply to? 3. For the 12 colleges you visited, you want to select your top 5. How many different ways could you rank your top five? 4. How many different words can be formed with the letters of the word MISSISSIPPI? 5. What is pigeonhole principle? Long Questions 1. Explain why the following problem is not strictly a permutation or combination problem: The local ice cream shop has 12 flavours. You decide to buy 2 scoops in a 347 CU IDOL SELF LEARNING MATERIAL (SLM)

dish. In how many ways could you do this if you are allowed to get 2 of the same scoop? 2. How many 3 digit numbers between 400 and 1000 can be formed with the digits 0, 2, 3, 4, 5, 6 if no digit is repeated? 3. A team of 3 members need to be formed out of 5 men and 2 women. In how many ways team can be formed so as to include at least 1 woman? 4. In how many ways a committee of 5 members can be selected from 6 men and 5 women, consisting of 3 men and 2 women? 5. In a computer science department, a student club can be formed with either 15 members from first year or 9 members from second year or 5 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed? B. Multiple Choice Questions 1. If nPr = 3024 and nCr = 126 then find n and r. a.9, 4 b.10, 3 c. 12, 4 d.11, 4 348 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Find the number of rectangles and squares in an 8 by 8 chess board respectively. a.296, 204 b.1092, 204 c.204, 1092 d.204, 1296 3. There are 20 points in a plane, how many triangles can be formed by these points if 5 are colinear? a.1130 b.550 c.1129 d.1140 4. In how many ways can we select 6 people out of 10, of which a particular person is not included? a. 10C3 b. 9C5 c. 9C6 d. 9C4 349 CU IDOL SELF LEARNING MATERIAL (SLM)

5. In a colony, there are 55 members. Every member posts a greeting card to all the members. How many greeting cards were posted by them? a. 990 b. 890 c. 2970 d.1980 6. Find the number of ways of arranging the letters of the words DANGER, so that no vowel occupies odd place. a.36 b.48 c.144 d.96 7. Find the sum of all four-digit numbers that can be formed by the digits 1, 3, 5, 7, 9 without repetition. a.666700 b. 666600 c. 678860 d. 665500 Answers 350 CU IDOL SELF LEARNING MATERIAL (SLM)