از بین بردن تکرار

Eliminating Repetition

Eliminating Repetition. In this video, we will make something explicit that we were doing in calculations in the previous video. When a method of counting yields repetitions, that is the same thing is counted in more than one way, we have to divide by the total number of possibilities.

But, but to divide the total number of possibilities by the time each item was counted. So if each out, if each particular arrangement was counted three times, we have to divided by 3. For example, suppose there’s a room of 20 people and each one will shake hands with each other person, how many handshakes occur?

One way to approach this is to realize each one of the 20 people shakes hands with 19 other people. One might think the number would be 20 times 19, but that would be too big. It would count every handshake twice. So for example, person A shakes hands with 19 other people. Person B shakes hands with 19 other people.

One of A’s persons, one of the handshakes of A, A shakes handshakes shakes hands with B. One of the, and person B. One of the people they shake hands with is A. So the handshake of A and B gets counted twice. Once as one of A’s handshakes and once as one of B’s handshakes.

So, if everything is counted twice, we’d have to divided by 2. And of course, what we get, 20 divided by 2 is 10, 10 times 19 is 190. So 190 handshakes would happen. Here’s a practice problem. Pause the video and then we’ll talk about this. We made reference to this back in the geometry section, now we can actually, we have the tools now where we can count diagonals.

So the diagonal of a polygon is a segment from any vertex to any other non-adjacent vertex. For example, a diagonal from K could go to any letter from A to I, but could not go to J or L, so that’s just the definition of a diagonal. How many diagonals does a regular 12-sided figure or regular dodecagon on half? Let’s think about this.

We could start at any vertex. That’s our starting vertex. From that vertex, then we could go to any non-adjacent vertex. So, a non-adjacent would be not the same vertex and not either one right next to it, so those three are eliminated. So there are nine other vertices that are non-adjacent.

And so for any one vertex, there are nine non-adjacent vertex, vertices. That’s 12 times 9, but each diagonal is counted twice doing that. One’s from the starting point and one’s from the ending point. And so we have to divide that by 2. So, instead of 12 times 9, it’s 6 times 9, which is 54. And that is actually the number of diagonals in a regular dodecagon.

This is precisely what we were doing in the previous video on repeated elements. For example, as we learned in that video. If three elements are identical, then we divided by 3 factorial, which equals 6 to eliminate repetitions. Here’s another practice problem. Pause the video and then we’ll talk about this.

Okay. From a set of ten different items, Lisa is going to select three as a gift for someone. How many different sets of three items can she pick? Using the methods we have learned so far, we might think 10 times 9 times 8.

The trouble is by counting choice by choice like this would count different arrangements of the three items as different. In other words, if one of the items is a watch, one is a ring and one is a necklace. It doesn’t actually matter, she’s gonna pick three and just put them in a group. It doesn’t matter whether we pick necklace first, then ring or ring first, then necklace.

The order of selection does not matter. And when we’re doing it in stages, we’re explicitly including the order of selection as if it did matter. So 10 times 9 times 8, that overcount. So, it’s three times, three factorial or six times too large, because we could rearrange the three gifts in any order and it would still be the same arrangement.

So, it’s gonna be 10 times 9 times 8 divided by 6. Little cancellation. Divide the 9 by 3, the 8 by 2 and then we get 3 times 4 is 12 times 10, which is 120. And that is the number of possible sets of three that she could pick. In that problem, we wanted a collection of three items and we didn’t care about the order of the items.

In this video, we saw that we could calculate this using the fundamental counting principle and then eliminating repetitions. In the coming video, we will learn that such a collection is called a combination and we will learn other ways to calculate. In summary, when we count, we must eliminate repetitions. We do this by dividing by the total number of times each arrangement is repeated in our calculation.