Introduction

It has been estimated that the average adult makes 35,000 decisions per day (7). Some of these decisions are only two options, being ‘yes’ or ‘no’. Other decisions are more complicated and may involve breaking a situation down into smaller choices. When was the last time you were in a situation where you thought to yourself, “There are too many options, I can’t decide what I want!” or “What are the chances?” Nearly all situations can be quantified using methods or concepts in combinatorics, the branch of mathematics that includes selections and arrangements of objects with prescribed conditions and configurations. Events are the set of all possible outcomes resulting from a particular situation, experiment, or process. People use basic principles of combinatorics in many everyday situations. Counting allows us to enumerate all possible ways an event can occur, and from these counts we can make inferences that will inform our decision making.

The Fundamental Counting Principle is introduced in elementary and middle school and forms the foundation for enumerating quantities given varying choices. In high school, permutations and combinations are emphasized in Integrated Math II (or Algebra II) and the Math Analysis (precalculus) courses. The connections between these three topics is often not explained or emphasized, though the structures and formulas for computation are similar. This unit emphasizes the relationships between the three key content concepts and gives students the opportunity to understand the general formulas and properties through relatable examples. Furthermore the connection between the number of combinations and the coefficients of the binomial theorem will be demonstrated through examples.

Demographics

San Jose, California, is a city of over one million people. On the East Side of San Jose, there are approximately 100,000 people, with a majority Hispanic/Latino population followed by Asians, including Filipinos. William C. Overfelt High School is one of eleven high schools in the East Side Union High School District (ESUHSD), a high school only district serving approximately 24,500 students in the East Side of San Jose. There are seven elementary partner districts that feed directly to ESUHSD.

The East Side is its own unique, vibrant, and strong community, and is a different world from the rest of San Jose. Over 80% of students at Overfelt qualify for federal free or reduced lunch, and over 50% of students’ parents are not high school graduates. This is in stark contrast to even some of the other high schools in our school district, such as one school located just 3 miles away with an enrollment of approximately 2500 students but only 17% of students being socioeconomically disadvantaged.

Rationale

My high school promotes a college going culture. In an effort to increase college eligibility, my school offers the opportunity for all students in the junior class to take the SAT. Results indicate that a large proportion of our students struggle on the mathematics portion of the exam. Our students also often struggle with the probability and statistical reasoning section on standardized tests such as the PSAT and SAT. Though these concepts make up a small portion of questions on standardized tests, the gaps in knowledge are obvious and need to be addressed.

Counting and its associated topics are taken for granted in the high school mathematics curriculum my school and district uses. Four years ago, the ESUHSD transitioned from a traditional Algebra 1-Geometry-Algebra 2 course sequence to a three course Integrated Mathematics pathway. In this transition, topics related to counting have taken a back seat, or were dumped, in favor of more emphasis on algebra skills, graphing of functions, and geometric concepts. Our district includes probability computations as a major standard in the curriculum pathway, but designates permutation and combinations to a supporting role, which is often interpreted as meaning “optional content.” The combinatorial topics that remained in the Integrated Math II curriculum emphasize counting permutations and combinations using prescribed formulas. There is little emphasis and explanation on how to understand the formulas and why the formulas work.

In my previous years of teaching, I noticed that many students lacked basic understanding of the counting principles that forms the foundation for a variety of topics in higher level math courses. For example, I had students taking AP Calculus BC that were never shown the factorial operator, which is essential in calculus when working with Taylor polynomials and testing for convergence of infinite series. Limited success in higher level mathematics at my school site is due in part to students being unable to access concepts due to gaps in their foundational knowledge.

My students like to see answers that are single and double digits because most of the practice questions that they were exposed to in previous math classes produced those types of results. When counting the number of ways we arrange objects or ways events can occur, numbers grow quickly. I can sense a heightened level of number anxiety and uncertainty when solutions include numbers reaching even the hundreds and thousands place. However, in realistic situations, people deal with numbers of all sizes on a regular basis. Attending to these ideas also might introduce students to take AP Statistics, as topics involving counting, permutations, and combinations which are included in the course. 

Permutation or Combination

The textbook used in Math Analysis gives students the product formulas for permutations and combinations and expects students to use them. In previous years, I noticed students would rely heavily on the formulas for computations without thinking about the problem. Given a word problem, they would scan and identify any two numbers in the problem. The larger of the two numbers was assigned n, and the smaller of the two numbers had to be r since it needed to be smaller. However, they had a very difficult time determining whether a problem was asking for a total number of permutations or combinations. Another point of difficulty for my students is the ability to visualize the large number of permutations and combinations. When we have a set with only a few elements, it does not take much effort to write our all permutations or combinations. However, even with 4 elements, students grumble at the thought of writing our 24 permutations. Once we reach 5 elements, writing all 120 permutations is a tedious and time consuming task. Even a seemingly simple problem, such as finding the number of seating arrangements in a classroom with 32 students results in an answer of 263,130,836,933,693,530,167,218,012,160,000,000, or slightly over 263 decillion outcomes, which can be written as approximately 2.63 × 10³⁵. For comparison, there are only roughly 100 billion trillion, or 10 × 10²³ number of stars in the whole universe (1).

Unit Goals

The mathematical topics emphasized in this unit include the Fundamental Counting Principle, counting the number of permutations, and counting the number of combinations. These will be introduced using a variety of problems with different contexts. In order to find the number of outcomes, students are expected to understand the difference between permutation and combination, and identify when a situation is asking to determine the number of permutations or number of combinations. Furthermore, students will understand the connections between the formulas for the Fundamental Counting Principle, the number of permutations and the number of combinations. In addition to the mathematical content, this unit includes examples, problems, and questions where students must comprehend, evaluate, and compare the quantities they compute.

The culminating activity for this unit will give students the opportunity to use their understanding of counting techniques to evaluate the issue of cyber security, specifically password security. A common complaint by students is related to their district assigned email accounts. There are various conditions and restrictions regarding that composition of a password that must be met. Consequently, I have many students forgetting their passwords. I will have my students research relevant issues in cyber security, examine our district’s current password guidelines and make recommendations for changes or arguments for keeping the existing policies based on their computations.

Standards

In the Common Core State Standards for mathematics, kindergarten students should “understand the relationship between numbers and quantities; connect counting to cardinality (11).” Cardinality is the number of elements in a set or group. Connections between counting with addition and subtraction are developed during the first grade. Skip counting using equal sized groups form the foundation of multiplication and division in third grade. After third grade, elementary and middle school standards emphasize counting through measurements of distance, area, and volume. During seventh grade, students learn how to use tree diagrams and the Fundamental Counting Principle. At the high school level, standards for quantity (see appendix) emphasize the defining quantities with appropriate levels of accuracy to model a variety of real-life situations.

Counting

Counting allows us to enumerate all possible outcomes resulting from events. An event is a particular situation, experiment, or process with a finite set of potential outcomes. Familiar examples are the throw of one or more dice, or the flipping of a coin. There are various methods to assist one when enumerating all elements of an event: methods introduced throughout grade school include making lists, keeping a tally, drawing a tree diagram, or computations using formulas.

At the high school pre-calculus course level, students are expected to enumerate the total number of possibilities for a variety of events. In both Integrated Math II and Math Analysis, the content covered begins with what is called the Fundamental Counting Principle, defined below. The Fundamental Counting Principle is also known as the Multiplication Principle in Combinatorics (8). However, this unit begins with the Addition Principle, defined below, that is not emphasized in high school, but is subtly implied in most situations.

Addition Principle

The addition principle defines a way to break down one event into two, or more, smaller events. These smaller events can be described as subevents of a single event.

Addition Principle: Suppose there are n₁ outcomes (ways) for the event E₁ to occur and n₂ outcomes (ways) for the event E₂ to occur. If all these ways are distinct, then the number of ways for E₁ or E₂ to occur is n₁ + n₂.

Example #1: Addition Principle

A class consists of 16 sophomores and 14 juniors. You will pick a student in the class for a prize. How many ways are there?

Solution: Let E=number of ways to pick a student. To find the number of ways, we must count how many students are in the class. Since there are 16 sophomore and 14 juniors, then E = 16 + 14 = 30 ways you can pick a student to win the prize.

Problem contexts designed for schools often state how many ways an event can occur. However, the addition principle is a key step that my students do not take into account. To compute probabilities, often my students struggle with adding up the number of ways to achieve successes or failures. Emphasizing the Addition Principle will help prepare my students for

Multiplication Principle (Fundamental Counting Principle)

Multiplication Principle: Suppose that an event E can be split into two events E₁ and E₂ in ordered stages. If there are n₁ ways for  to occur, and if for each of these, there are exactly n₂ ways for  E₂ to occur, then the number of ways for the event E to occur is n₁ ∙ n₂. For each outcome of  E_1, there are n₂ possible outcomes for  E₂.

Example #2: Multiplication Principle

You are picking what to wear to school. You have 6 shirts and 4 pairs of pants. How many outfits can you make? To find the number of outfits, we can break the situation down to two events. E₁ represents the number of shirts and E₂ represents the number of pants. Then E₁ = 6 and E₂ = 4. To find the total number of outfits, we multiply the number of ways each event can occur, giving us the image: .

In this example, the events are independent, where the outcome of the first event does not affect the number of outcomes in the second event. Sometimes events are not independent, but still there are the same number of possibilities for E₂, for any outcome of E₁. The multiplication principle is a special case of the addition principle, when every outcome of E₁ leaves the same number of possible outcomes for E₂.

Generalized Multiplication Principle

The multiplication principle can be applied to situations where there are more than 2 events. This fact is buried in the margins of our textbook as a side remark regarding the generalization of the formula. During this unit, I will introduce my students to the Fundamental Counting Principle as it is stated above, and I will also formally generalize the principle to include more than 2 events.

Multiplication Principle (General): Suppose that an event E can be described as, a combination of events E₁, E₂, …, E_k that occur in successive stages. If there are n₁ ways for E₁ to occur, n₂ ways for E₂ to occur for any outcome of E₁, …, and n_k ways for E_k to occur for any outcomes of the earlier events, then the number of ways for the event E to occur is given by n₁ ∙ n₂… ∙ n_k.

Example #3: Multiplication Principle – More than 2 Events

In the state of California, each standard automobile license plate number consists of a one-digit number followed by three letters followed by a three more digits. Digits and letters can be repeated. How many distinct license plate numbers can be formed in California?

Solution: Break up 1 license plate into 7 independent sub events. Each event is either a digit from 0-9 or a letter from A-Z.

Thus there are (10)∙(26)∙(26)∙(26)∙(10∙10∙10)=175,760,000 possible license plate combinations in California.

When I taught this topic in previous years, some of my students would think that this number is very large and therefore incorrect. To build their number sense, I would have students compare the above result with the fact that at the end of 2017 the California DMV reported that there were 25,467,663 registered cars in the state (3). Also, approximately 2.1 million cars were sold and registered in California during 2016. Suppose that rate stays the same and license plates with the standard pattern described above are still issued. If the next license plate to be issued is 8FAA000, and the digits are increased by 1 such that the next plates issued are 8FAA001, 8FAA002, 8FAA003, and so on. This continues to 8FAA998, 8FAA999, 8FAB000, and 8FAB001. This pattern continues until the last license plate 9ZZZ999 is issued. About how long will it be before California issues all possible combinations? If there were 4 digits and 3 letters, but a letter could occupy any position, how would that change the number of possible license plates?

A related question involves the California driver’s license which consists of 1 letter followed by 7 digits. How many different licenses can be issued? When will California need to change the configuration for driver’s licenses?

Permutations

A permutation is a way in which a set or collection of things can be ordered or arranged. The number of permutations of n elements is n∙(n-1)∙3∙2∙1=n!, where the possibilities at each step depend on previous choice, however the number of items does not. I will emphasize how factorial, !, is a mathematical convention that follows directly from the Fundamental Counting Principle. I will present my students with situations where utilizing the factorial notation would allow for computations to be written concisely. I will also compare factorials as analogous to exponential notation for powers of a fixed number.

Example #4: Permutations

Place students into groups of varying sizes and have them determine how many ways they can rearrange themselves in a line. Record the different ways they can line up.

For my classes, I will assign students into groups of different sizes. When placed into groups of 1 student, 2 students, 3 students, and 4 students, I would have each group physically line themselves up into as many different permutations and then record each of the different permutations. 

Group of 1: Since n=1, and 1!=1 There is only 1 way that a student can line up.

Group of 2: Since n=2, and 2!=1∙2=2. There are 2 ways that students can line up.  

Group of 3: Since n=3, and 3!=1∙2∙3=6. For 3 students, they can arrange themselves 6 ways.

Group of 4: Since n=4, and 4!=1∙2∙3∙4=24. With 4 students, they can arrange themselves 24 ways.

I would consider using a group of 5 students, but since that there are 5!=120 different ways students can line up. I would have the students write out all of the permutations, but would not expect them to arrange themselves into each of the ways.

Combinations of n Elements Taken r at a Time

When given a set of n elements, we can count the number of permutations when ordering all n elements. We can also find the number of permutations when ordering less than all of the elements. When choosing r elements from the total set of n, where r<n, the number of permutations for the r elements is given by the formula ^⧠_nP^⧠_r = n!/(n-r)!. The notation ^⧠_nP^⧠_r represents the number of permutations when taking a subset of r elements taken from a set of n elements. The formula and notation is used in the Integrated Math II and Math Analysis textbooks.

My students like to have a formula and will substitute the first numbers they see in a given problem. If I were to follow the lesson as prescribed, my students would only need to identify the values for n and r, substitute into the formula, and compute. I plan to show the connection between the Fundamental Counting Principle and the formula for ^⧠_nP_r through examples.

Example #5: Permutations, nPr

Suppose there are 8 runners in a race. How many ways can they finish 1^st, 2^nd and 3^rd?

Solution: Let E represent the total number of outcomes. The event can be broken down into three smaller components. Let E₁ be the number of ways anyone in the race can finish 1^st, E₂ be the number of ways anyone remaining in the race can finish 2^nd, and E₃ be the number of ways the remaining runners can finish 3^rd.

Then,

Since there are 8 runners, there are 8 different outcomes for 1^st place, thus E₁ = 8. For second place, there are only 7 runners remaining, giving E₂ = 7. Finally, there are only 6 runners left for third place, giving E₃ = 6. The total number of permutations is

Using the preceding approach shows that the problem can be solved using the Multiplication Principle. ^⧠_nP^⧠_r can be represented as a product of integers from n to (n-r-1). Thus, ^⧠_nP^⧠_r = n!/(n-r)! = n(n-1)(n-2)∙∙∙(n-r-1). This representation is not presented in the Integrated Math II and Math Analysis textbooks. I plan to discuss with my students how this generalized representation really is the Multiplication Principle when we have the number of outcomes is decreasing by one each time.

Solution using Formula: In this scenario n=8 and r=3. Substituting into the formula for ^⧠_nP_r,we have ^⧠_nP_r = 8!/(8-3)! = 8!/5! = (8∙7∙6∙5∙4∙3∙2∙1)/(5∙4∙3∙2∙1) = 8∙7∙6 = 336.

Understanding the problem in context can help better understand why we divide. The first observation would be (n-r) is the number of runners that do not finish first, second, or third. By taking (n-r)!, we are finding all the permutations for the remaining five runners to finish in 4^th, 5^th, 6^th, 7^th, and 8^th place. Since we are only interested in finding the number of ways for the top three finishers, we would divide the total number of race outcomes, 8!, by the number of ways in which the 4^th through 8^th place runners would finish, 5!. The result gives us the same value as using only the Multiplication Principle.

Deriving the Formula

I will show my students that the formula in the textbook can be derived from the product identified in the first solution. Starting with ^⧠_nP^⧠_r = n!/(n-r)! = n(n-1)(n-2)∙∙∙(n-r-1), I will continue the product one step at a time from (n-r) down to 1, and simultaneously dividing from (n-r) down to 1. I will show the following steps:

^⧠_nP^⧠_r = n(n-1)(n-2)∙∙∙(n-r-1) =

= n(n-1)(n-2)∙∙∙(n-r-1)(n-r)/(n-r) =

= n(n-1)(n-2)∙∙∙(n-r-1)(n-r)(n-(r-1))/(n-r)(n-(r-1)) =

...

= n(n-1)(n-2)∙∙∙(n-r-1)(n-r)(n-(r-1))∙∙∙2/(n-r)(n-(r-1))∙∙∙2 =

= n(n-1)(n-2)∙∙∙(n-r-1)(n-r)(n-(r-1))∙∙∙2∙1/(n-r)(n-(r-1))∙∙∙2∙1 =

= n!/(n-r)!.

The result from the Fundamental Counting Principle now coincides with the factorial notation formula found in the textbook. With my classes, I will compare the amount of work it takes to use the textbook formula to perform the computations to arrive at the same answer that can be found through a few multiplications. I often hear my students ask for a formula because many like the fact that you can plug in numbers and compute a result. I want my students to recognize a formula may appear compact and easier, but alternative approaches may be more efficient for actually doing computations.

Combinations

A combination is a subset of a larger set in which the order of elements is not important. The equation for combinations is given and students are tasked with computing the number of combinations by identifying the total number of elements, n, and the number of elements being selected, r.

^⧠_nC^⧠_r = n!/(r!∙(n-r)!) = ^⧠_nP^⧠_r/r!

Why do we divide the number of permutations ^⧠_nP^⧠_r by r! when finding the number of combinations? Just as for the formulas for permutation, the text gives no explanation regarding what is happening with this equation. We will provide an explanation below, after discussing some examples.

Example #7: Lottery

To play the California Fantasy Five lottery game, a person picks five numbers from 1 to 39.  They need to match all five of the numbers. Find the total number of all 5-number combinations.

I would introduce this problem prior to giving the ^⧠_nC^⧠_r. To come up with the solution, I would show how to begin solving the problem by thinking of it as another permutation problem.

Solution: Let E represent the number of ways to select five numbers. To find the number of permutations for the number of ways to select five numbers, the event can be broken down into five smaller events.

For the first pick, E₁=39, since there are 39 choices. Since no numbers can be repeated, E₂=38. Since each pick leaves one less option, E₃=37, E₄=36 and E₅=35. This gives the total number of permutations as E=(39)(38)(37)(36)(35)=69,090,840 permutations.

There are just over 69 million ways to select a sequence of 5 numbers from the set of numbers 1 to 39, but we want combinations. This means that we don’t care about the ordering of the 5 numbers, only about the set we get. Notice that we could have picked the same numbers in a different order. For example, the formula above treats the sequence of 5 numbers, 9, 11, 18, 25, and 31, as different from the sequence of 5 numbers 11, 25, 9, 31, 18, despite the fact that they both give the same collection of numbers. From this observation, I would say to my students: Didn’t we find a way to account for distinguishable permutations, that is, different orderings, already? I would also ask, “How many repeats of each number set are within the 69,090,840 permutations?”

I want my students to see the connection between, r, the number of elements being chosen, and the number of repetitions for each set of r numbers. Taking 5!=120, gives the number of times each distinct set of 5 is counted in the 69,090,840 permutations. Thus, for each combination, there are 120 different permutations that are accounted for in the 69,090,840 permutations. Thus, to find the number of distinct combinations, we would divide by 5!

This is one of multiple examples I would show students before generalizing the formula for combinations. I will take the time to show how to break down the problems into smaller pieces that utilize prior concepts rather than just giving the formula. By understanding the problem, students would be better equipped to identify whether a question was seeking permutations or combinations. Knowing what type of problem would enable them to select the correct formula to solve the problem.

Combinations and the Binomial Theorem

Textbooks often point out the fact that the binomial coefficients found in Pascal’s Triangle also tell us the number of combinations when choosing r objects from n items. Often, students are told to count to the nth row of the triangle and then find the rth entry. To convince my students of this fact, I would have students group for 0≤r≤n when n=1, 2, 3, 4 and 5.  The definition would be given to students. I would have to introduce the concept of the empty set, ϕ, counting as 1 set. I expect this to be a difficult concept for students to comprehend, even at the precalculus level.

To explain this concept, I would ask my students, “How many ways can we take 0 items from a group of n?” It seems odd that the result is 1, but if we were to select 0 items, we would have 0 items afterwards, thus there is 1 way to have 0.

By having students list out and count the number of sets will make the connection between the number on Pascal’s Triangle and ^⧠_nC^⧠_r more apparent, because they will be writing out the actual set combinations for each situation.

For, n=1, {A}.

For, n=2, {A, B}.

For, n=3, {A, B, C}.

I will have my students construct similar tables for the cases where n=4 and n=5. Writing out the combinations and counting the ways for selecting r elements from a group of n for 0≤r≤n gives a more concrete way to connect the binomial theorem coefficients with ^⧠_nC^⧠_r. This exercise emphasizes the connection between the number of subsets with the coefficients of the binomial theorem.

An additional exercise I would introduce to students is to demonstrate how to produce subsequent rows of Pascal’s Triangle using the recursion formula . For example, .

I will have my students compute more examples to show the recursion formula works numerically. For more advanced students, I would challenge my students use mathematical induction to confirm the recursion for Pascal’s Triangle by showing using the formula for .

Distinguishable Permutations

A common textbook question asks students to find the number of permutations for the letters in the word ‘BANANA’. Since there are 6 letters in the word BANANA, n=6. The total number of permutations is given by 6!, thus there are 720 arrangements for the letters. However, some of the permutations look the same. For example, BANANA and BANANA look the same, but the first and second ‘N’ swapped places, so they count as two permutations. How do we account for these duplications? How many distinguishable permutations, permutations that are look different from others, are there?

One way to compute the number of distinguishable permutations for the letters in ‘BANANA’ is to begin by counting the how many times each letter appears in the word. ‘B’ appears 1 time, ‘N’ appears 2 times, and ‘A’ appears 3 times. To find how many ways to arrange these letters, begin by selecting a letter. Suppose we started with placing ‘B’ into any of the six spaces. Next, we could find how many pairs of places to put the two ‘N’ letters. This is a combination problem that can be computed by taking ^⧠₅C^⧠₂ =10.  Finally there is only 1 way left to place all three ‘A’ letters to fill in the remaining slots. Multiplying the ways to arrange ‘B’, two ‘N’, and three ‘A’ letters gives the total number of 6∙10∙1=60 distinguishable permutations. This is not the way our textbooks introduce and explain how to compute distinguishable permutations when there is repetition of items since this topic is introduced prior to combinations.

The textbook way of approaching the BANANA problem also begins by counting the number of letter repetitions. Since we know how many times a letter repeats, n_i, we need to take n_i! to find the number of ways we can permute that specific letter with its other identical letters. With the example, we have 3 ‘A’, 1 ‘B’, and 2 ‘N’ giving n₁=3, n₂=1, and n₃=2. Taking n₁!=3!=6 tells us that there are 6 copies of each distinct permutation that look identical only because the three ‘A’ letters are interchanged with one another. Likewise, n₃!=2!=2 tells us that there are 2 copies of each distinct permutation that look identical due to the two ‘N’ letters interchanging. Since there is only 1 ‘B’, giving n₂!=1, this does not increase the number of indistinguishable permutations. We multiply n₁! ∙ n₂! ∙ n₃! together by using the Fundamental Counting Principle to find the total number of copies of each distinguishable permutation. Thus there are n₁! ∙ n₂! ∙ n₃!  = (6)(1)(2)=12 copies of each distinguishable permutation. Dividing by the total number of permutations, we find a total of 720/12=60 distinct permutations for the letters in ‘BANANA’.

The textbook method uses the formal definition which states: Suppose a set of n elements has n₁ of one kind of elements, n₂ of a second kind, n₃of a third kind, and so on, with n = n₁ + n₂ + n₃ + ⋯ + n_k. Then the number of distinguishable permutations of the n objects is n! / (n₁ + n₂ + n₃ + ⋯ + n_k). This is sometimes also called a multinomial coefficient. In the textbook, no explanation as to why we divide by n_i! for 1≤i≤k is provided. The textbook just expects us to follow along. Why do we need to divide by the product of each element’s number of repetitions? I plan to show my students the first solution approach to the BANANA problem and have them compare the 60 to the 60!/(3!∙1!∙2!) computed using the general rule.

Problem Sets

In addition to the abstract content of permutations, combinations, binomial and multinomial coefficients, a goal of this unit is to have my students quantify situations that they encounter on a frequent basis. Classic textbook problems involving permutations and combinations utilize sets of objects such as a standard 52-deck of playing cards, 6-sided die, 2-sided coins, and telephone numbers. Though these objects may seem mundane to most, I had students struggle significantly with the topics in this unit because they were unfamiliar with a deck of cards. Throughout this unit, I will make sure to include more traditional problems, because they do appear on standardized tests, but first I will give my students a chance to practice the concepts and skills within familiar contexts that are part of their daily life.

Menu Options

My students love food. The following are sample questions that are modeled from different restaurant menus from around our local neighborhood.  

Scenario #1

Ricky goes to Denny’s and wants to order a Grand Slam for breakfast. For the Grand Slam, he can select any four items from a list of 13 items. How many different breakfasts can Ricky order?

Extension: Ricky can upgrade his Grand Slam to a Super Grand Slam by adding a fifth item to his meal. How many different 5-item Super Grand Slams can Ricky order?

Scenario #2

Josephine is ordering a poke bowl. She wants a regular bowl and must choose a base of white or brown rice, one of six different choices of fish/protein, two of 8 different sauces, and 5 of 12 different toppings. How many different bowls are possible?

Extension: A large bowl allows two scoops of fish/protein and 7 different toppings. How many more large bowl combinations are possible compared to regular bowls?

Scenario #3

Vinh is ordering pizza for School Site Council. He can choose either a thin, hand-tossed or pan pizza crust, with one of five different sauces. Also, Vinh must specify if he wants a normal amount of sauce, extra sauce, or light sauce. A pizza can be topped off with a choice of 8 different meats and 16 different non-meat toppings. Since his coupon only allows for 3 toppings, how many different 3-topping pizzas are possible? Vinh must consider that some people at the meeting are vegetarians. How many 3-toppping, non-meat pizzas can he order? Vinh also decides to have some variety and wants to make some pizzas with 1 meat and 2 non-meat toppings. How many of these pizzas are possible? Are there the same number of possible pizzas with 2-meat toppings and 1 non-meat topping as there are pizzas with 1 meat and 2 non-meat toppings?

Scenario #4

At a Cracker Barrel restaurant, each of the 6 dinner entrees comes with the customer’s choice of three sides. There are 23 different sides available. How many dinner combinations are possible?

Extension: If you had one dinner per day at Cracker Barrel, could you eat a different meal every day for a year? For 2 years? For 3 years?

Scenario #5

Jason likes to drink way too much milk tea. His favorite milk tea spot offers 8 different types of tea. After selecting a tea, he must choose between a small or large size, 5 different sugar levels, 5 different levels of ice. How many different tea drinks are possible?

Extension Questions: Jason realizes that he forgot to add toppings. There 9 toppings available and he can choose to add up to two toppings to any drink. How many drinks are possible?

Fun and Games

This set of problems involves toys, board games, and card games.

Game #1

Consider a standard 3x3 Rubik’s cube. There are 6 center pieces that are fixed. There are 8 corner pieces and 12 edge pieces. Suppose that corner pieces can be interchanged with each other and the edge pieces interchanged with each other. Find the number of different patterns that can be produced assuming all permutations of corners and edges are possible.

Extension: How many permutations of face cubes are possible on 4x4 Rubik’s cube? Note that for the 4x4, there are no center cubes, and no fixed relation between a given face and a color. If you could display 1 permutation per second, how long would it take to cycle through all the permutations for a 3x3? A 4x4? If a computer can go through 350 billion permutations per second, how long would it take to cycle through all the permutations for a 3x3? A 4x4?

Game #2

A Boggle board has 16 slots. There are 16 6-sided dice with different letters of the alphabet printed on the sides. How many Boggle board permutations are there?

Game #3

In Mastermind, one player creates a 4 color code (a sequence of 4 colors) while the other player tries to guess the code. If there are 6 different colors and, colors can be repeated, how many different codes can be made?

Game #4

To play the card game 13, a standard deck of 52 cards is shuffled and 4 hands of 13 cards are dealt. How many different 13-card hands are possible?

Game #5

The badminton team has 7 girls singles athletes. The top three make it to varsity. How many different varsity lineups are possible?

Culminating Project - Password Combinations

With continual developments in technology, we interact and count with numbers of ever increasing size. There is a need to enumerate and comprehend numbers at increasing degrees of magnitude. A decade ago, the kilobyte and megabyte were the units to store our computer data. Today, we utilize gigabytes and terabytes, as standards for personal data storage.

Passwords are a context where it is easy to count and compare the total number of possible ways when the length is relatively small and as restrictions are introduced or relaxed. As the length increases, and the number of restrictions and conditions change, the number of potential passwords increases rapidly.

As a culminating project, students will evaluate the effectiveness of our district’s password policies. Based on their computations, they will make recommendations for or against policy changes.

To start, students will compare passwords with a length of four.

Four digit pin numbers are often used for bank ATM cards and cell phone locks. How many possible 4-digit codes are there?

If you were to use four letters of the alphabet, how many 4-letter passwords are there?

Varying the numbers of letters and digits allowed also affects the number of passwords. If we only had one digit followed by three letters, we have:

Taking 2 digits and then 2 letters gives:

I would have students consider whether the placement of the 2 digits and 2 letters in a password changes the number of passwords. Also, I would have them look at 1 digit and 3 letters where the digit can change position in the password sequence.

If you could use an alphanumeric code, where the digits 0 to 9 and the letters A-Z are included, how many 4-character passwords are there?

For many students, the amount of over 1.6 million passwords seems very secure, but a computer can run through all possible combinations nearly instantaneously for only 4 characters. A standard computer can guess approximately 350 billion passwords a second. Using that knowledge, students are posed the following scenario: Our district requires students to create passwords that are at least 8 characters, where there is at least one upper case letter, at least one lower case letter, at least one digit, and at least one of six special characters. Are these requirements necessary or should they be changed? If you believe that the policy is sufficient, explain why. If you believe there should be changes, explain why. How many alphanumeric 8 letter codes are there? Assuming that a computer can check 350 billion passwords per second, how many seconds would it take for the computer to check all passwords?

Students would be permitted to work in groups of up to three and would submit their responses in a format of their choice, which may include but not limited to a written explanation, PowerPoint presentation, poster, or video. Their final project will also be examined by a non-math teacher, which requires the students to make sure their arguments are clear and understandable to a broader audience.

References

1. About How Many Stars Are in Space?" UCSB Science Line. Accessed July 18, 2018. https://scienceline.ucsb.edu/getkey.php?key=3775.
2. "Brute-force Attacks." English. Accessed June 25, 2018. https://www.password-depot.com/know-how/brute-force-attacks.htm
3. “CA DMV Statistics for Publication”. January 2017 through December 2017. https://www.dmv.ca.gov/portal/wcm/connect/5aa16cd3-39a5-402f-9453-0d353706cc9a/official.pdf?MOD=AJPERES.
4. "Calculate Passwords." Generate Random Prime Numbers. Accessed June 25, 2018. https://asecuritysite.com/encryption/passes
5. Cheswick, William. “Rethinking Passwords.” Communications of the ACM 56, no. 2 (2013)
6. Collider, Hadron. How Secure Is My Password? Accessed June 25, 2018. https://howsecureismypassword.net/
7. Hoomans, Joel. "Leading Edge Journal." 35,000 Decisions: The Great Choices of Strategic Leaders. Accessed August 03, 2018. https://go.roberts.edu/leadingedge/the-great-choices-of-strategic-leaders.
8. Koh, Khee-Meng, and Eng Guan Tay. Counting. River Edge, NJ: World Scientific, 2013.
9. Larson, Ron, and Laurie Boswell.Big Ideas Math: Integrated Mathematics II. Erie, PA: Big Ideas Learning, 2016.
10. Richards, Gary. "Roadshow: California's New "8" License Plates Will Hit the Road Soon." The Mercury News. July 26, 2017. Accessed June 20, 2018. https://www.mercurynews.com/2017/07/26/roadshow-californias-new-8-license-plates-will-be-on-the-road-soon/.
11. "Standards for Mathematical Practice." Common Core State Standards Initiative. Accessed June 01, 2018. http://www.corestandards.org/Math/Practice/.

Implementing District Standards

In many permutation and combination calculations, there may be a need to consider the computational limitations of a calculator. With such cases, students would need to define appropriate quantities and levels of accuracy for their numerical answers. These standards are addressed in the Common Core High School Number and Quantity standards HSN.Q.A.2 and HSN.Q.A.3. The East Side Union High School District (ESUHSD) standards are based off of the Common Core State Standards. ESUHSD math standard N-Q-A, reason quantitatively and use units to solve problems, is addressed throughout the scenario and context based problems as described in the examples and problem sets above. The culminating project incorporates standards F-BF-A, building a function that models a relationship between two quantities, and F-IF-B, interpreting functions that arise in applications in terms of the context, by having students examine real-world problems.