Circular Arrangements

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Four friends go out for dinner and sit at a round table. Four people, four seats, so four factorial: twenty four seatings, right? Hmm. Walk round that table and you will find only six really different seatings! So where did the other eighteen go? Today we find out. And look, circular arrangements come up often in JEE, okay? So, let's begin.

0:31At a round table, only neighbours matter

So, look at the screen. The three pictures are numbered one, two and three, in small Roman numerals. Picture one: the four friends A, B, C and D at a round table, going clockwise from the top. In picture two, everybody has moved one seat clockwise, and the arrow says: same. But why the same? Start at A in picture two and go clockwise. Who do you meet, in order? We meet B, then C, then D, in that order. Exactly the same order as in picture one, okay? Rotate everyone by a seat, and every person still has the same person on the left and the same person on the right. At a round table only the relative positions matter, so it is the same seating. Same order round the table, same seating. Clear? Now, in a row there is a first seat, a second seat, and so on. But at a round table, which seat is the first seat? Yes, exactly! None of them. So we make one. Fix one person anywhere, say A, at the top. Now every other seat has a meaning: next to A, two seats away from A, and so on. So the other n minus one people simply fill n minus one seats, just like a row, okay? So, n different objects in a circle: n minus one, in brackets, factorial. The exclamation mark is factorial, remember. And note the conditions: the objects are all different, and only rotations count as the same. Got it? Now our four friends from the start. Three factorial: six, not four factorial, twenty four. Here is why it is four times fewer: four factorial counted each seating four times, once for every rotation. Mystery solved! With me?

2:23Necklaces and garlands: a flip changes nothing

Now look at picture three, the mirror image of picture one. Here, A is still at the top. So tell me: going clockwise from A, who comes next in picture one? And who comes next in picture three? In picture one, B comes next, and in picture three, D comes next. The order has reversed, so at a table this is a new seating, just as the line under picture three says, okay? People at a table cannot be flipped over. But now make the four into beads on a necklace. Pick it up, turn it over, and picture one becomes picture three! The same necklace. Right? So for a necklace, a garland or beads, clockwise and anticlockwise are not distinguished. Each necklace was counted twice in n minus one factorial, once for each way round. So, divide by two: half of n minus one, in brackets, factorial. Okay? Two conditions here. First, this needs n greater than or equal to three: that is the sign you see, greater than or equal to. With just two beads, there is only one necklace anyway, but the formula would give one half. Second, and this is the trap: halve only when clockwise and anticlockwise are not distinguished, as for necklaces, garlands and beads. For people at a round table they are different, so do not halve. Some students halve there too, and get exactly half the right answer. Don't do that!

3:50Two more rules for circles

Now, two more rules. First, what if only r out of n different objects go round the circle? In a row, that is n P r: the capital P, with n at its top left and r at its bottom right. But each circle is counted r times in it, once for every rotation, just like our four friends. So divide by r: n P r over r. Clear? Next, gaps. Remember the gap method? In a row, m people make m plus one gaps: one between each pair of neighbours, and one at each end. Now seat the same m people at a round table. How many gaps now? Only m! There are no ends at a round table: the last person sits right next to the first. So m people make m gaps, not m plus one. This is a very common slip, so watch for it. Got it?

4:44Example 1: 8 people at a round table, necklace of 8 beads

Alright, example one. In how many ways can eight people sit at a round table? And how many necklaces can be made from eight different beads? Pause the video, and try it first. Done? Okay, let's check. Eight different people, so fix one of them and arrange the other seven: seven factorial. Five thousand and forty ways. Right? Now the necklace. Eight different beads, so seven factorial again? Oh no, careful! Look, a necklace can be turned over, and its mirror image is the same necklace. So each one was counted twice. Seven factorial over two: two thousand five hundred and twenty necklaces. Got it?

5:30Example 2: 5 men and 5 women alternate at a round table

Now a slightly harder one. In how many ways can five men and five women sit at a round table, so that men and women alternate? All ten are different people, okay? Pause and try. Hint: seat one group first. Done? Okay, let's check. Seat the five men first. Five different men round a table: five minus one, factorial, that is four factorial. Twenty four ways. With me? Now the women. They also sit round the circle, so four factorial again, right? No, no, wait! Once the men are seated, the circle is no longer free to turn. Every gap is now a fixed place, between two particular men. And five men at a round table make five gaps, not six. Alternate means exactly one woman in each gap, so five women go into five different places: five factorial, one hundred and twenty. Clear? So, the total is four factorial times five factorial. Twenty four times one hundred and twenty: two thousand eight hundred and eighty. Seat one group, then fill the gaps. See how fast that was?

6:44Quick revision: round table, necklaces and gaps

So, quick revision. Round table: n minus one, factorial. Fix one, arrange the rest. Necklace or garland: half of that, for n at least three. And at a round table, m people make m gaps, not m plus one. Now go and try the practice problems on this page. You will enjoy them, I promise. All the best!