We have a set of \(7\) letters: A, T, E, W, L, O and R. We are interested in the \(4\) letter “words” that you can build from these letters, using each one only once. How many such “words” are there? What if we only want to build “words” such that the letters used are in the alphabetical order, how many “words” can we make then?
All the example problems followed a similar theme. You had to find the number of ways you can choose some \(k\) out of \(n\) items, if the order of choosing does not matter. We by now know the procedure to do so: First, pretend the order matters and pick \(k\) items, one item after the other, in \(n, n-1, n-2, \dots, n-k+1\) ways. To obtain the total number of ways to do that, we need to multiply them: \(n \times (n-1) \times \dots \times (n-k+1)\). Then, ask ourselves in how many ways can we order the items that we have chosen? Well, in \(k!\) ways, the number of permutations. Since the order does not matter, we need to divide the number found before by \(k!\).
The total number of combinations (choosing \(k\) out of \(n\) objects) is \[n \times (n-1) \times \dots \times (n-k+1)\div k! = \frac{n!}{k! \times (n-k)!}\] It is an important formula, and is often denoted with a special symbol \(\binom{n}{k}\), read “n choose k”. When solving the problems below, you can use the formula, or if you do not want to, just work them out individually, just like the examples!
Six girls – Ashley, Betty, Cindy, Donna, Eve and Fiona are members of a school maths circle (in another school obviously). In how many ways can you pick 4 of them to participate in a baths battle against the RGS team?
John’s dad is setting the table for a family dinner. He has \(13\) plates, all in different sizes. He will pick \(5\) plates, and then the largest will be for himself, the second largest for his wife, the third largest for John’s sister Dorothy, the fourth largest for John and the smallest will be for John’s little brother Louie. In how many ways can John’s father set the table?
Rithika drew \(10\) points on the board in such a way that no \(3\) of them belong to one straight line. How many triangles can she draw with vertices in these points?
a) A florist has \(11\) different types of flowers in her shop. She was asked to make a bouquet with \(4\) different flowers. In how many ways can she do that?
b) What if she was asked to use exactly \(7\) types of flowers?
c) Knowing the answer to a), do you know how and why is the answer to b) related to it?
Tom’s dad built a 9 board-long fence, which Tom’s mother painted white. Tom, who has 3 different cans of paint – red, green and blue – would like to decorate the fence.
a) If he paints every second board (boards 2, 4, ...), in how many ways can he do it?
b) If he paints every second board, and if exactly one of the boards should be red, in how many ways can he do it?
c) If he paints every board, if exactly three boards should be red, and if the fence should be symmetrical, in how many ways can he do it?
There are \(19\) adventurers standing in a queue to see a dragon’s treasure. They can enter the cave in three groups, with \(15\) minute breaks between two consecutive groups. The order in which adventurers will enter the cave is fixed – they are in a queue after all. But they can still decide who will be in the first, second and third group. Each group has to consist of at least one adventurer. In how many ways can they do that?
Ten players were entered into a badminton tournament. The first round consisted of 5 matches, with each player in one match. In how many different ways could the 10 players be matched against each other?
There are again some adventurers standing in a queue to see a dragon’s treasure. This time, there are more of them – \(26\). The rules have changed slightly, they still enter exactly in the order they are queuing, but they now have to divide themselves into \(5\) groups, and some of the groups can be empty, do not consist of any adventurers at all. In how many ways can they do that now?
Problems often involve a protagonist, a quest and a story. In combinatorics, stories can help us prove identities and formulas, that would be difficult to prove otherwise. Here, you can write your own story, which will show that the following statement is always true:
The number of ways we can choose \(k\) out of \(n\) items is equal to the number of ways we can choose \(k\) out of \(n-1\) objects PLUS the number of ways in which we can choose \(k-1\) out of \(n-1\) objects.