Subsets and Pairs of Subsets

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Take the numbers from one to ten. Pick as many as you like, even none, but never two neighbours, like four and five, okay? How many different selections are possible? Writing them all out would take an hour, right? By the end of this video, you will get it in under a minute, and the answer hides inside a famous number pattern. In JEE, counting subsets comes up often. So, let's begin.

0:33Subsets: every element says in or out

So, let's start simple. Take a set, capital S, with n elements. To build a subset, we go to each element and decide. How many choices does each element have? Two, yes! In, or out. The choices are independent, so we multiply: two times two, n times; the dots mean and so on. Two to the power n subsets, counting the empty set and S itself. Right? With exactly r elements? We just choose r of the n elements, and order does not matter: n C r ways. The small n sits at the top left of the capital C, okay? And exactly half of all subsets have an even number of elements: two to the power, n minus one. Why? Take any fixed element of S, and add it or remove it. The size changes by one, so the subsets pair up, one even and one odd. This needs S to be non empty, of course. Clear?

1:31Pairs with A inside B: three places per element

Now, pairs of subsets. The box marked U is our whole set S, and the circles are two subsets, A and B, okay? We want ordered pairs, A comma B, in round brackets, so swapping the two gives a different pair. And this rounded C with a line under it means is a subset of, or equal to. Right? Here is the topper's trick: forget the sets, and follow one element. The picture has four regions: A only, both, B only, and outside both. If A lies inside B, where can an element sit? Anywhere except the region A only! Correct. An element of A must also be in B, so this dark region stays empty. Clear? So, three places: neither, B only, or both, numbered one, two and three. Choose a place for every element, and the pair is fixed completely. Got it? Three choices for each of the n elements: three times three, n times, so three to the power n ordered pairs. No need to fix B first and count the subsets inside it. One line, done. Okay?

2:38Disjoint, or covering S: also three places

Now, two more conditions. First, A intersection B is the empty set. The upside down cup means intersection, and the circle with a slash is the empty set. So the dark middle region must stay empty. How many places are left? Three again, yes! Neither, A only, or B only. So, three to the power n once more. Right? Second: A union B equals the whole set, capital S, okay? The cup shape means union: in A, or in B, or in both. So now the dark outside region must stay empty. With me? The places: A only, B only, or both. Three to the power n, again. Three conditions, one answer, all from the same trick. Clear?

3:21Unordered pairs of disjoint subsets

Now, a twist: disjoint, but unordered. In curly brackets, swapping the two sets gives the same pair. Each unordered pair comes from two ordered ones, so just divide three to the power n by two, right? No, no, careful! Three to the power n is odd, so half of it is not a whole number. Halving fails when the two sets are equal, since swapping changes nothing. So, when can two disjoint sets be equal? Only when both are empty! Very good. If the two sets are equal, their intersection is the set itself, and that must be empty. So the pair empty set, empty set is counted once; every other pair, twice. Got it? So, remove that pair, halve the rest, and add it back: three to the power n minus one, over two, plus one. That is three to the power n plus one, over two. Order mattering or not changes the answer, so read carefully.

4:18No two consecutive numbers: Fibonacci

Okay? Last result, and it is our puzzle. Subsets of one, two, up to n, with no two consecutive numbers. The curly brackets hold the elements of the set. Right? The count is a Fibonacci number. Fibonacci goes one, one, two, three, five, eight, thirteen, each the sum of the two before. The small number at the bottom right of F is its position, so F one and F two are both one. Our count is F with subscript n plus two. Why? Example two will show you. With me?

4:48Example 1: 3-element subsets with 1, smallest element 5

Alright, example one, in two parts. First: how many three element subsets of one to twenty contain the number one? Second: how many subsets of one to twelve have smallest element five? Pause the video, and try it first. Done? Okay, let's check. Part one. The number one is fixed inside. We need two more elements, from the other nineteen numbers. Okay? So, nineteen C two: nineteen times eighteen, over two. One hundred and seventy one. That's it! Part two. The numbers five to twelve are allowed: eight numbers, each in or out. So, two to the power eight, two hundred and fifty six, right? Oh no, careful! The set with just six and seven has no five at all, so its smallest element is not five. So, five must be in, one to four must be out, and six to twelve are free. Clear? Six to twelve is seven numbers. Two to the power seven: one hundred and twenty eight. Very good!

5:53Example 2: subsets of 1 to 10 with no two consecutive

Now, remember our puzzle? Let's finish it. How many subsets of one to ten contain no two consecutive numbers? Pause and try. Hint: ask whether the subset contains ten. Done? Okay, let's check. Let s n, a small s with n at its bottom right, count such subsets of one to n. We want s ten. Right? Split on the largest number, n: is it in the subset, or not? Suppose n is in. Then what about n minus one? It must be out! Exactly. So the rest is a good subset of one to n minus two: s n minus two ways with n. And without n, the rest is a good subset of one to n minus one: s n minus one ways. Okay? Add them: s n equals s n minus one, plus s n minus two. That is the Fibonacci rule! To start, s one is two: empty, or just one. And s two is three: empty, one alone, or two alone. With me? Now keep adding. Two plus three, five. Three plus five, eight. Then thirteen, twenty one, thirty four, fifty five, eighty nine, and one hundred and forty four. Got it? So, s ten is one hundred and forty four, which is F twelve: position ten plus two. Exactly our formula, and our puzzle solved in under a minute. Perfect!

7:17Quick revision: subsets, subset pairs, no two consecutive

So, quick revision. Subsets: two to the power n in all, n C r of size r, and half of them, two to the power, n minus one, of even size. Ordered pairs with A inside B, or disjoint, or covering S: three to the power n, three places per element. Unordered disjoint pairs: three to the power n plus one, over two. No two consecutive numbers: F, n plus two. Now go and try the practice problems on this page. You are ready for them. All the best!