Part C: Concept Checks

Transcript

0:00Introduction

Hello everyone! Okay, a quick challenge before we start. You have n different balls and k different boxes, and any box can take any number of balls. In how many ways can the balls go in? n to the power k, or k to the power n? Looks like a coin toss, right? Today is Part C of our problem bank: ten statements that sound correct, and one question each time. Is it exactly right? Statements like these come up often in JEE, in true or false form. So, let's begin.

0:35Round tables and necklaces

So, the first statement. n different people sit round a table. The exclamation mark on screen is factorial, remember. Is the number of ways n factorial?

0:46Round tables and necklaces

No! Look at the figure. The three pictures are numbered with small Roman numerals. In picture two, everyone has moved one seat round, but keeps the same neighbours, and the arrow says same. At a round table, a rotation is the same seating. So n people give n minus one, in brackets, factorial, okay? Now make them different beads on a necklace. Picture three is the mirror image of picture one: a new seating at a table, but turn a necklace over and it is the same necklace, right? So each necklace was counted twice: one half of n minus one, in brackets, factorial. Now tell me: does this work for every n? Not quite! Only for n greater than or equal to three; that is the sign you see. With one or two beads, the formula gives one half, and half a necklace makes no sense. There is just one necklace. Clear?

1:41No two together, or not all together?

Next statement. Boys and girls in a row, all different people. Is no two girls together the same as the girls not all together? No, they are different! Not all together means the total, minus the arrangements with all the girls in one block. So, with three or more girls, two of them may still stand side by side. Only with exactly two girls do the two conditions mean the same thing. Okay?

2:07No two together, or not all together?

No two together is much stricter; it needs the gap method in the figure. Say six boys and four girls. B one to B six are the boys: six factorial ways. They make seven gaps, including both ends: the small circles. The four girls go into different gaps: seven P four ways, with the small seven at the top left. So, six factorial times seven P four; the cross means times. That is six hundred and four thousand eight hundred. Stricter condition, smaller count. Got it?

2:38Two groups, and a fixed order

Alright, now groups. Two n different people are split into two groups of n each. Is the count two n, in brackets, factorial, over n factorial times n factorial? Only if the groups are named, like team one and team two. If the groups have no names, swapping the two groups gives the same split. So every split was counted twice: divide by two factorial. With me? Next, n different objects in a row, but k of them must keep a fixed order among themselves. Is the count n factorial over k? Oh no, careful! Those k objects can be ordered in k factorial ways, and only one of those orders is allowed. So divide by k factorial, not by k. Clear?

3:26Balls, boxes and selections

Now, our question from the start. n different balls go into k different boxes. Is it n to the power k? How many choices does each ball have? k choices, yes, exactly! n balls, each with k choices: k times k times k, n times over. So it is k to the power n, not n to the power k. Mystery solved! Right? Next, the equation x one plus x two, and so on up to x k, equals n. The small numbers below x are subscripts, just labels, and each x i is a whole number, greater than or equal to zero. Is the number of solutions n C k minus one, with the small n at the top left? No! Write each solution as a row of n stars and k minus one bars. Choose the places of the bars among n plus k minus one places. So the count is n plus k minus one, C, k minus one. Okay? Now fruit. From p identical apples and q identical oranges, is the number of selections two to the power p plus q? No! The apples are identical, so only how many you take matters: zero, one, and so on up to p. That is p plus one choices. Same for the oranges: q plus one. So, p plus one, times q plus one, and this includes the empty selection. Got it?

4:47Onto functions and diagonals

Two more. Onto functions, from a set with m elements to a set with n elements. Onto means every element of the second set gets used. Is the number of onto functions m P n? No! It comes from inclusion and exclusion. The big Greek letter sigma means add over i: minus one to the power i, times n C i, times n minus i, to the power m. And when m equals n, it is simply n factorial. With me? Last one. The number of diagonals of a polygon with n sides: is it n C two? Careful! n C two joins every pair of vertices, and that counts the n sides too. Take away the n sides, and you get n times n minus three, over two. Clear?

5:34Example 1: TRIANGLE with vowels in alphabetical order

Okay, Example one, an easy one, from Part A of this chapter. In how many arrangements of the word TRIANGLE are the vowels in alphabetical order? Pause the video, and try it first. Done? Okay, let's check. TRIANGLE has eight letters, all different. The vowels are A, E and I, and alphabetical order means A first, then E, then I, okay? Three vowels in a fixed order, so the answer is eight factorial over three, right? No, no, careful! That is our trap from before. The three vowels can be ordered in three factorial, that is six ways, and only one of those orders, A, E, I, is allowed. So divide eight factorial by three factorial. Eight factorial is forty thousand three hundred and twenty; over six, that is six thousand seven hundred and twenty. Really simple, once you see it!

6:32Example 2: 8 at a round table, two pairs not neighbours

Now Example two, a little harder, also from Part A of this chapter. Eight people sit at a round table. In how many ways, if A and B are not neighbours, and C and D are not neighbours? Pause the video, and try it. Done? Let's check. Eight different people at a round table: eight minus one, factorial, so seven factorial. That is five thousand and forty, okay? Now the bad cases. First, A and B together: glue them into one block. Now seven units sit round the table, six factorial ways, and inside the block they can swap, so times two. The dot means times. That is one thousand four hundred and forty, and the same number for C and D together. Got it? So the answer is five thousand and forty, minus two thousand eight hundred and eighty, right? Oh no, careful! Seatings with both pairs together were subtracted twice, once with each pair. Glue both pairs: six units, five factorial ways, and each block can swap: two times two times five factorial, four hundred and eighty. So add them back once. Five thousand and forty, minus two thousand eight hundred and eighty, plus four hundred and eighty: two thousand six hundred and forty. That's it!

7:53Quick revision: the right formulas and when to divide

So, quick revision. Round table, n minus one, in brackets, factorial; necklace, half of that, for n at least three. n different balls into k different boxes, k to the power n; and for non-negative solutions, stars and bars: n plus k minus one, C, k minus one. For a fixed order, divide by k factorial; for unnamed groups, divide by two factorial. And always ask: is the statement exactly right? Now try the fourteen practice problems on this page. All the best!