(Also available in WeScheme)
Students explore the concept of combinations as a restricted set of permutations in which order does not matter. They compute the possible number of outcomes when choosing n items from m possibilities in a variety of real-world situations.
Students will be able to…
Student-facing Lesson Goals
the number of possible arrangements in a collection of items where the order of the selection does NOT matter. (ABC and CBA would be considered the same combination.)
the number of possible arrangements in a collection of items where the order of the selection matters (ABC and CBA would be considered different permutations)
Students are introduced to the concept of combinations. They learn the definition and compute a number of combinations by hand using tree diagrams, then learn the formula for computing combinations.
🖼Show image With his new set of rules, Luigi’s Family Restaurant is more popular than ever! But with a full house every night, the cooks are busy and the kitchen gets backed up. Customers start complaining about slow service, and Luigi is once again in trouble.
The cooks point out that it’s easy to add twice as much ravioli to the same pot - but it’s hard to make two separate pots of ravioli. If people could choose their four courses in advance, the chefs could just make a few huge batches of each item and divide them up on people’s plates!
Luigi decides to change the rules again, to help his kitchen staff. There are still six items on the menu, customers can still choose any four they want, and they still can’t choose the same item twice…but order no longer matters. Instead of a four-course meal, diners get a "combination platter" with all four items on the plate.
How is this situation similar to the permutation questions?
How is it different?
When order doesn’t matter, all the possible options are called combinations (think of Luigi’s "combination platter!").
Since there’s no replacement, let’s start by using our formula for permutation-without-replacement to compute all the possible permutations. We have six items to choose from and are selecting four of them:
permute\mbox-no\mbox-replace(6, 4) = 6!/( (6 - 4)! ) = 6!/2! = 360
In this situation, the order doesn’t matter, so some of these platters are going to be the same combination: Lasagna, Soup, Ziti and Chicken is a different permutation from Lasagna, Soup, Chicken, Ziti, but it’s the same combination! If we knew that every combination would have a duplicate, we’d divide the number of platters by two. If we knew each one would have a triplicate, we’d divide by three.
How do we compute the number of duplicates in a four-course platter?
We already know how to do this! This is the same question as "How many permutations are there for the same four courses?"
Using our formula for permutation without replacement we get: permute\mbox-no\mbox-replace(4, 4) = 4!/( 4-4! ) = 4! = 24 duplicates!
Now, we need to divide 'the number of permutations (without replacement) for choosing 4 courses out of six items" by "the number of duplicate permutations in any four-course platter".
combinations(6, 4) = 6!/( (6 - 4)! ) ÷ 4! = 360 ÷ 24 = 15
We can rewrite this using our functions from earlier:
combinations(items, choose) = ( permute\mbox-/no\mbox-replace(items, choose) )( permute\mbox-no\mbox-replace(choose, choose) )
In this situation, we have 6 possible choices and we get to choose 4 times:
combinations(6, 4) = ( permute\mbox-/no\mbox-replace(6, 4) )( permute\mbox-no\mbox-replace(4, 4) )
What is the difference between combination and permutation?
What are some real-world examples of combinations?
Permutations and Combinations Starter File provides students with a chance to view all the permutations and combinations for Luigi’s menu.
These materials were developed partly through support of the National Science Foundation, (awards 1042210, 1535276, 1648684, and 1738598). Bootstrap by the Bootstrap Community is licensed under a Creative Commons 4.0 Unported License. This license does not grant permission to run training or professional development. Offering training or professional development with materials substantially derived from Bootstrap must be approved in writing by a Bootstrap Director. Permissions beyond the scope of this license, such as to run training, may be available by contacting contact@BootstrapWorld.org.