Should dictionary words be used in passwords?

It is commonly advised that dictionary words should not be used when forming passwords. We would like to make the case that dictionary words can be used as long as the words are randomly chosen. This post illustrates how this may be done.

We pick 5 words at random from the following dictionary.

The idea is to choose 5 pages at random. Then choose a word at random from each page. There are 1,317 pages. We calculate the Excel function =RANDBETWEEN(1, 1317) 5 times to generate the following random numbers, each of which is considered a page number in the dictionary.

562, 1292, 397, 857, 1171

Assuming that there are around 50 words in a page, calculate the Excel function =RANDBETWEEN(1, 50) and generate the following random numbers.

40, 8, 19, 13, 29

Thus the first random word is the 40th word in the 562nd page in the dictionary, the second word is the 8th word in the 1292nd page in the dictionary and so on. The 5 random words are:

Putting these 5 words in a string produces the following password, which is 41-character long.

How secure is this password? The 5 words are selected at random from a fairly large dictionary. It has 1317 pages. Assuming 50 words per page, the dictionary would have around 65,000 words. According to the multiplication principle, there would be $65000^5=1.16 \times 10^{24}$ many ways to choose 5 words from this dictionary. This is 1 followed by 24 zeros, which is 1 septillion. When 1 is followed by 12 zeros, the result is 1 trillion. So 1 followed by 24 zeros is the same as 1 trillion times 1 trillion.

So a brute force dictionary attack would have to cover the universe of these 1 septillion 5-word strings. To get a sense of how big 1 septillion is, try this scenario. For a computer than can check 1,000 5-word strings per second, it will take over 1 million years to exhaust all the 1 septillion 5-word strings. Such a brute force attack may be more suitable for a parallel computing project that involves a massive number of computers than for a cyber criminal who has only a limited number of computers. Examples of parallel computing projects include the ones for searching for the largest known prime number (one example is GIMPS – Great Internet Mersenne Prime Search).

The words have to be chosen at random for this approach to work. If the words are based on movie titles, sport team names, names of celebrities and other types of familiar proper nouns as well as idiomatic phrases, then the universe of the word strings would be much smaller, maybe 20,00 or 30,000. In relation 1 septillion, 30,000 is in effect zero. The word strings from this tiny universe would be vulnerable to brute force attack.

Of course, the security of the random 5-word strings can be further enhanced. Use more random words, for example. Another possibility is to make them case sensitive. The above 41-character string can become the following:

Another possibility is to add numeric characters and special characters (, *, # etc). Of course, the password will be harder to remember if it is made case sensitive (especially if the upper cases letters are chosen at random). So a possible compromise is to make the first letter of a word upper case just to satisfy the case sensitivity requirement of many systems and websites along with throwing in some numbers and special characters. Simply add more random words for enhanced security. In general, the approach of using multi-word phrase should be taken with care. The 5-word string that is demonstrated above requires some effort to produce – randomly selecting pages in the dictionary and randomly selecting one word from each selected page. I actually use a function in Excel to generate the random numbers to locate the pages. Instead, I can randomly flip through the pages. For some, that may still be too much effort. The danger is that someone may get lazy and simply use familiar proper nouns like favorite movies and sport teams such as the following: PirateoftheCaribbeanLALakers Instead, the following is a better alternative. MfmiPotCaIaadhLALf The above string is taken from the first letters of the sentence “My favorite movie is Pirate of the Caribbean and I am a die hard LA Lakers fan”. It is an 18-character password that is taken from a memorable phrase. The resulting password is definitely much more secure than stringing the movie title and the basket team name together. See here for information on the approach of using a memorable phrase or several phrases. $\text{ }$ $\text{ }$ $\text{ }$ Dan Ma math Daniel Ma math Dan Ma mathematics Daniel Ma mathematics $\copyright$ 2017 – Dan Ma Strength in numbers It is commonplace for frequent users of the Internet to have multiple online accounts that require passwords. Advice and guidelines abound on the Internet on picking safe and strong passwords. They are usually common sense guidelines – e.g. it has to be long enough and it should not be easily guessed. Sometimes a long enough password may not be safe and secure. The word password is an 8-letter word but sits on top of just about every list of no-no passwords. On the other hand, the 8-character string such as kHgfDsAa is a reasonable choice. Recently it was reported in Cnet.com that security researcher Troy Hunt has released a searchable tool that taps the database of previously compromised passwords (here’s the Cnet.com article and here’s the tool). There are 306 millions of them. Supposedly the utility of the tool is that no one should use the passwords in this list. The thinking is that 306 million is a large number, and since it is such a large number, the search database would be a public service. A counting exercise is sometimes needed in order to get a proper perspective on password strength. How big is 306 million? Consider the total number of 8-character strings. It would be $26^8$ which is 208,827,064,576. This is 208 billion or 208,827 million, about 682 times of 306 million. The universe of 8-letter passwords is 682 times bigger than this searchable database tool. This universe of 208 billion 8-letter passwords is only for lower case passwords. If including case sensitive passwords, this would be even a much bigger universe. It can be even bigger by adding the possibility of numeric characters and special symbols. The following table gives the numbers of possible passwords from lengths of 8 to 12 (just letters, case insensitive). Number of case insensitive passwords Length Total Total 8-letter $26^8$ 208,827,064,576 9-letter $26^9$ 5,429,503,678,976 10-letter $26^{10}$ 141,167,095,653,376 11-letter $26^{11}$ 3,670,344,486,987,780 12-letter $26^{12}$ 95,428,956,661,682,200 It is a good idea to use the searchable tool. But bear in mind that any password that is reasonably long and reasonably strong is likely not to be in this list of 306 million. Note that the number of 12-letter case insensitive (letter only) passwords is 95,428 trillion! The passwords represented in this table alone would dwarf the 306 million in this searchable database. Here’s a peculiar way to find strong passwords. This scheme is to produce 26-letter passwords such that every letter is known and is fixed! In fact, the first letter of the password is the first letter in the English alphabets, the second letter of the password is the second letter of the English alphabets and so on. The length of the password is long but every letter is fixed. This scheme is discussed in this blog post. This universe of passwords is not as big as the ones in the above table. But it is a big enough collection of possibilities that it is all but impossible to hack without computer help. There are 67,108,864 many different possibilities (over 67 million). How does this scheme work? Why is it that every letter is known but the passwords can be strong? Curious? Think about it or go to this blog post. This particular scheme is a way to learn the concept of binomial distribution. Any one who understands this scheme understands binomial distribution. Having to come up with multiple passwords for multiple online accounts is a fact of life in the age of the Internet. Having a good way to generate secure passwords is critical. Keeping track of all the passwords is definitely a challenge. Often times, what is overlooked is that thinking about passwords is a good way to get close to the mathematics of counting. $\text{ }$ $\text{ }$ $\text{ }$ $\copyright$ 2017 – Dan Ma The probabilities of poker hands This post works with 5-card Poker hands drawn from a standard deck of 52 cards. The discussion is mostly mathematical, using the Poker hands to illustrate counting techniques and calculation of probabilities Working with poker hands is an excellent way to illustrate the counting techniques covered previously in this blog – multiplication principle, permutation and combination (also covered here). There are 2,598,960 many possible 5-card Poker hands. Thus the probability of obtaining any one specific hand is 1 in 2,598,960 (roughly 1 in 2.6 million). The probability of obtaining a given type of hands (e.g. three of a kind) is the number of possible hands for that type over 2,598,960. Thus this is primarily a counting exercise. ___________________________________________________________________________ Preliminary Calculation Usually the order in which the cards are dealt is not important (except in the case of stud poker). Thus the following three examples point to the same poker hand. The only difference is the order in which the cards are dealt. These are the same hand. Order is not important. The number of possible 5-card poker hands would then be the same as the number of 5-element subsets of 52 objects. The following is the total number of 5-card poker hands drawn from a standard deck of 52 cards. $\displaystyle \binom{52}{5}=\frac{52!}{5! \ 47!}=2,598,960$ The notation $\binom{n}{r}$ is called the binomial coefficient and is pronounced “n choose r”, which is identical to the number of $r$-element subsets of a set with $n$ objects. Other notations for $\binom{n}{r}$ are $_nC_r$, $C_{n,r}$ and $C(n,r)$. Many calculators have a function for $_nC_r$. Of course the calculation can also be done by definition by first calculating factorials. Thus the probability of obtaining a specific hand (say, 2, 6, 10, K, A, all diamond) would be 1 in 2,598,960. If 5 cards are randomly drawn, what is the probability of getting a 5-card hand consisting of all diamond cards? It is $\displaystyle P(\text{all diamond})=\frac{1287}{2598960}=0.000495198=0.0495198 \%$ This is definitely a very rare event (less than 0.05% chance of happening). The numerator 1,287 is the number of hands consisting of all diamond cards, which is obtained by the following calculation. $\displaystyle \binom{13}{5} \times \binom{39}{0}=\frac{13!}{5! \ 8!} \times 1=1,287$ The reasoning for the above calculation is that to draw a 5-card hand consisting of all diamond, we are drawing 5 cards from the 13 diamond cards and drawing zero cards from the other 39 cards. Since $\binom{39}{0}=1$ (there is only one way to draw nothing), $\binom{13}{5}=1287$ is the number of hands with all diamonds. If 5 cards are randomly drawn, what is the probability of getting a 5-card hand consisting of cards in one suit? The probability of getting all 5 cards in another suit (say heart) would also be 1287/2598960. So we have the following derivation. \displaystyle \begin{aligned} P(\text{one suit})&=P(\text{all diamond})+P(\text{all heart})+P(\text{all club})+P(\text{all spade}) \\&=\frac{1287}{2598960}+\frac{1287}{2598960}+\frac{1287}{2598960}+\frac{1287}{2598960} \\&=\frac{5148}{2598960} \\&=0.001980792 \\&=0.198 \% \end{aligned} Thus getting a hand with all cards in one suit is 4 times more likely than getting one with all diamond, but is still a rare event (with about a 0.2% chance of happening). Some of the higher ranked poker hands are in one suit but with additional strict requirements. They will be further discussed below. Another example. What is the probability of obtaining a hand that has 3 diamonds and 2 hearts? The answer is 22308/2598960 = 0.008583433. The number of “3 diamond, 2 heart” hands is calculated as follows: $\displaystyle \binom{13}{3} \times \binom{13}{2} \times \binom{26}{0}=\frac{13!}{3! \ 11!} \times \frac{13!}{2! \ 13!}=286 \times 78=22308$ One theme that emerges is that the multiplication principle is behind the numerator of a poker hand probability. For example, we can think of the process to get a 5-card hand with 3 diamonds and 2 hearts in three steps. The first is to draw 3 cards from the 13 diamond cards, the second is to draw 2 cards from the 13 heart cards, and the third is to draw zero from the remaining 26 cards. The third step can be omitted since the number of ways of choosing zero is 1. In any case, the number of possible ways to carry out that 2-step (or 3-step) process is to multiply all the possibilities together. ___________________________________________________________________________ The Poker Hands Here’s a ranking chart of the Poker hands. The chart lists the rankings with an example for each ranking. The examples are a good reminder of the definitions. The highest ranking of them all is the royal flush, which consists of 5 consecutive cards in one suit with the highest card being Ace. There is only one such hand in each suit. Thus the chance for getting a royal flush is 4 in 2,598,960. Royal flush is a specific example of a straight flush, which consists of 5 consecutive cards in one suit. There are 10 such hands in one suit. So there are 40 hands for straight flush in total. A flush is a hand with 5 cards in the same suit but not in consecutive order (or not in sequence). Thus the requirement for flush is considerably more relaxed than a straight flush. A straight is like a straight flush in that the 5 cards are in sequence but the 5 cards in a straight are not of the same suit. For a more in depth discussion on Poker hands, see the Wikipedia entry on Poker hands. The counting for some of these hands is done in the next section. The definition of the hands can be inferred from the above chart. For the sake of completeness, the following table lists out the definition. Definitions of Poker Hands Poker Hand Definition 1 Royal Flush A, K, Q, J, 10, all in the same suit 2 Straight Flush Five consecutive cards, all in the same suit 3 Four of a Kind Four cards of the same rank, one card of another rank 4 Full House Three of a kind with a pair 5 Flush Five cards of the same suit, not in consecutive order 6 Straight Five consecutive cards, not of the same suit 7 Three of a Kind Three cards of the same rank, 2 cards of two other ranks 8 Two Pair Two cards of the same rank, two cards of another rank, one card of a third rank 9 One Pair Three cards of the same rank, 3 cards of three other ranks 10 High Card If no one has any of the above hands, the player with the highest card wins ___________________________________________________________________________ Counting Poker Hands Straight Flush Counting from A-K-Q-J-10, K-Q-J-10-9, Q-J-10-9-8, …, 6-5-4-3-2 to 5-4-3-2-A, there are 10 hands that are in sequence in a given suit. So there are 40 straight flush hands all together. Four of a Kind There is only one way to have a four of a kind for a given rank. The fifth card can be any one of the remaining 48 cards. Thus there are 48 possibilities of a four of a kind in one rank. Thus there are 13 x 48 = 624 many four of a kind in total. Full House Let’s fix two ranks, say 2 and 8. How many ways can we have three of 2 and two of 8? We are choosing 3 cards out of the four 2’s and choosing 2 cards out of the four 8’s. That would be $\binom{4}{3} \times \binom{4}{2}$ = 4 x 6 = 24. But the two ranks can be other ranks too. How many ways can we pick two ranks out of 13? That would be 13 x 12 = 156. So the total number of possibilities for Full House is $\displaystyle 13 \times 12 \times \binom{4}{3} \times \binom{4}{2}= 13 \times 12 \times 4 \times 6 =3744$ Note that the multiplication principle is at work here. When we pick two ranks, the number of ways is 13 x 12 = 156. Why did we not use $\binom{13}{2}$ = 78? Flush There are $\binom{13}{5}$ = 1,287 possible hands with all cards in the same suit. Recall that there are only 10 straight flush on a given suit. Thus of all the 5-card hands with all cards in a given suit, there are 1,287-10 = 1,277 hands that are not straight flush. Thus the total number of flush hands is 4 x 1277 = 5,108. Straight There are 10 five-consecutive sequences in 13 cards (as shown in the explanation for straight flush in this section). In each such sequence, there are 4 choices for each card (one for each suit). Thus the number of 5-card hands with 5 cards in sequence is $10 \times 4^5= 10240$. Then we need to subtract the number of straight flushes (40) from this number. Thus the number of straight is 10240 – 10 = 10,200. Three of a Kind There are 13 ranks (from A, K, …, to 2). We choose one of them to have 3 cards in that rank and two other ranks to have one card in each of those ranks. The following derivation reflects all the choosing in this process. $\displaystyle \binom{13}{1} \times \binom{4}{3} \times \binom{12}{2} \times \binom{4}{1} \times \binom{4}{1}=13 \times 4 \times 66 \times 4 \times 4 = 54912$ Two Pair and One Pair These two are left as exercises. High Card The count is the complement that makes up 2,598,960. The following table gives the counts of all the poker hands. The probability is the fraction of the 2,598,960 hands that meet the requirement of the type of hands in question. Note that royal flush is not listed. This is because it is included in the count for straight flush. Royal flush is omitted so that he counts add up to 2,598,960. Probabilities of Poker Hands Poker Hand Count Probability 2 Straight Flush 40 0.0000154 3 Four of a Kind 624 0.0002401 4 Full House 3,744 0.0014406 5 Flush 5,108 0.0019654 6 Straight 10,200 0.0039246 7 Three of a Kind 54,912 0.0211285 8 Two Pair 123,552 0.0475390 9 One Pair 1,098,240 0.4225690 10 High Card 1,302,540 0.5011774 Total 2,598,960 1.0000000 ___________________________________________________________________________ $\copyright$ 2017 – Dan Ma Binomial coefficients This is the third post in a series of posts on combinatorial analysis. The post is opened with the following problem. Figure 1 Path Problem Point Q is 7 blocks east and 6 blocks north of Point P (see Figure 1). A person wants to walk from Point P to Point Q by walking 13 blocks. Assume that all the paths from any point to any point in the above diagram are available for walking. In how many ways can the person go from Point P to Point Q? One way to solve this problem is to count the number of paths in a “brute force” approach by tracing all possible paths in the diagram. The total number of paths is 1,716. So counting directly is not a practical approach. It turns out that the path problem and other similar problems will become routine once the concept of binomial coefficients is clearly understood. ___________________________________________________________________________ Review First we highlight the important concepts introduced in the previous post on permutations and combinations. The number $n!$, read $n$ factorial, is defined by the product $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$. It is the number of ordered arrangements of $n$ objects. For convenience we define 0! = 1. An ordered arrangement of a set of objects is called a permutation. How many permutations are there of 7 objects? For example, how many ways can the following 7 people be arranged in a row for a group photo: Abby, Beth, Charlie, David, Edward, Frank, and George? An equivalent question: how many permutations are there of the letters A, B, C, D, E, F and G? The answer is 7! = 5040. The reasoning is based on the multiplication principle (see here). There are 7 people to choose for the first position, and there are 6 people to choose from for the second position after the first position is fixed, and so on. Thus there are 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040. The number of permutations of $k$ objects chosen from $n$ objects is defined by $\displaystyle P(n,k)=\frac{n!}{(n-k)!}$. Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes of1000, $500 and$100? An equivalent question: how many permutations are there of 3 letters chosen from the 7 letters A, B, C, D, E, F and G? The answer can also be obtained by the multiplication principle. There are 7 x 6 x 5 = 210 permutations, which is identical to $P(7,3)=\frac{7!}{(7-3)!}=\frac{7!}{4!}=7 \times 6 \times 5$.

The number of different groups of size $k$ that can be chosen from a set of $n$ distinct objects is $\displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!}$ where $n$ is a positive integer and $k=0,1,2,\cdots,n$. This number is called the number of possible combinations of $n$ objects chosen $k$ at a time. The values $\displaystyle \binom{n}{k}$ are often referred to as binomial coefficients because of their connection with the binomial theorem.

Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes, each of which is 1000? An equivalent question: how many three-letter sets can be chosen from the 7 letters A, B, C, D, E, F and G? Here, the order does not matter. The answer 210 obtained previously is too large because it contains many repeats. For example, the letters A, B and C has 3! = 6 permutations. In the answer 210, each 3-letter combination occurs 6 times. So the answer is 210 / 6 = 35, which is identical to $\binom{7}{3}=35$. Other notations for the binomial coefficient $\binom{n}{k}$ are $_nC_k$, $C(n,k)$ and $C_{n,k}$. Permutation and combination can all be computed directly in terms of factorials. The calculation can also be done using calculator or software. Most calculators have functions for combination (binomial coefficient) and permutation. In Excel, the binomial coefficient is computed by the formula =COMBIN(n, k), which will give the result as $\binom{n}{k}$. The Excel formula for permutation is =PERMUT(n,k). ___________________________________________________________________________ The Path Problem Recall that the problem is to walk 7 blocks East and 6 blocks North starting at point P. Let use E to mean walking one block East and N to mean walking one block North. The following is one specific path that the person might take. Figure 2 The path in Figure 2 can be described by the string E-E-N-N-N-E-N-E-E-E-N-N-E. Of course there are many other possible paths that can be taken. Observe that each possible path correspond to a string of 7 E’s and 6 N’s. On the other hand, each possible 13-character string with 7 E’s and 6 N’s correspond to a path in the problem. So the problem is about finding the number of possible 13-character string with 7 E’s and 6 N’s. In other words, we are in interested in all the ways we can write 7 E’s and 6 N’s in the following 13 positions. $\LARGE \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box$ Writing 7 E’s and 6 N’s in 13 boxes is the same as choosing 7 boxes out of 13 boxes to fill with 7 E’s. The number of ways to choose 7 objects out of 13 objects is simply $\binom{13}{7}=1716$. ___________________________________________________________________________ Several Interpretations of the Binomial Coefficients The path problem makes it clear that there are several ways of looking at the binomial coefficient $\displaystyle \binom{n}{k}$. Each of the following is a count that is computed by $\displaystyle \binom{n}{k}$. 1. The number of different groups of size $k$ that can be chosen from a set of $n$ objects. 2. The number of ways a set of $n$ objects can be labeled by 0 or 1. 3. The number of different $n$-character strings that can be formed by using $k$ of one symbol and $n-k$ of another symbol. 4. The number of permutations of $n$ items, of which $k$ are alike and $n-k$ are alike. 5. A random experiment consists of $n$ trials, each of which results in one of two outcomes (outcome 1 and outcome 2). The number of ways the experiment can be performed such that $k$ of the trials result in outcome 1 and $n-k$ of the trials result in outcome 2. 6. An urn contains a large number of balls, each of which is labeled 0 or 1. Randomly select a ball $n$ times from the urn with replacement. The number of ways the balls can be selected in such a way that $k$ of the balls are labeled 1 and $n-k$ of the balls are labeled 0. The same theme runs through the above 6 ideas. The first one is the standard definition of binomial coefficient. The number $\binom{n}{k}$, according to idea 1, would be the number of all possible subsets of size $k$ that can be chosen from a set of $n$ objects. We can also think of choosing a subset as a random experiment of $n$ trials where each trial has two distinct outcomes. Out of the $n$ objects, we only want $k$ of them with $k \le n$. Then for each object, there is a decision – choose it or not choose it (two distinct outcomes). So there are $n$ trials and each trial has two outcomes (idea 5). We can also think of a random sampling process too. Perform each trial that ends in two outcomes will be like a random sampling from a population consisting of 0’s and 1’s (idea 6). Going back to the $n$ objects in idea 1, deciding whether to choose each object is also like labeling that object with 0 or 1 (idea 2). Since each object generates two outcomes (choose or not choose), the $n$ decisions successively is like a string of $n$ characters, each of which is one of two distinct symbols (ideas 3 and 4). Though the interpretation may be nuanced, the calculation of the binomial coefficient is straightforward. Thinking of the binomial coefficient as the number of ways to making a series of two-outcome decisions is crucial to the understanding of binomial distribution. In the remainder of the post, we discuss other properties of the binomial coefficients. ___________________________________________________________________________ The Binomial Theorem The sum of two symbols, say $x+y$, is called a binomial. The binomial theorem is a formula for deriving the power of a binomial, i.e. for deriving $(x+y)^n$ for $n=1,2,3,\cdots$. We explain the idea behind the formula. The ideas 3 and 4 discussed above are particularly useful ways of looking at the binomial theorem. Consider the first several expansions. \displaystyle \begin{aligned} (x+y)^1&=x+y \end{aligned} \displaystyle \begin{aligned} (x+y)^2&=(x+y) (x+y)\\&=xx+xy+yx+yy \\&=x^2+2xy+y^2 \end{aligned} \displaystyle \begin{aligned} (x+y)^3&=(x+y) (x+y) (x+y)\\&=xxx+xxy+xyx+yxx+xyy+yxy+yyx+yyy \\&=x^3+3x^2y^1+3xy^2+y^3 \end{aligned} \displaystyle \begin{aligned} (x+y)^4&=(x+y) (x+y) (x+y) (x+y)\\&=xxxx+xxxy+xxyx+xyxx+yxxx\\& \ \ +xxyy+ xyxy+xyyx+yxxy+yxyx+yyxx\\&\ \ +xyyy+yxyy+yyxy+yyyx+yyyy \ \ \ \ \ \ \ \ \ \text{(16 terms)} \\&=x^4+4x^3y^1+6x^2y^2+4xy^3+y^4 \end{aligned} \displaystyle \begin{aligned} (x+y)^5&=(x+y) (x+y) (x+y) (x+y) (x+y)\\&=xxxxx+xxxxy+xxxyx+xxyxx+xyxxx+yxxxx \cdots \\& \ \ +xxxyy+xxyxy+xyxxy+yxxxy+xxyyx \\& \ \ + xyxyx+yxxyx+xyyxx+yxyxx+yyxxx \ \ + \cdots (\text{32 terms}) \\&=x^5+5x^4y^1+10x^3y^2+10x^2y^3+5xy^4+y^5 \end{aligned} The above derivations are deliberately detailed to make a point. For example, the result of $(x+y)^5$ is product of 5 identical factors of $x+y$. Multiplying out these five factors of $x+y$ results in $2^5=32$ terms. Each of these 32 items is a string of x’s and y’s. Let’s look at the strings with 3 x’s and 2 y’s. they are: $xxxyy+xxyxy+xyxxy+yxxxy+xxyyx$ $xyxyx+yxxyx+xyyxx+yxyxx+yyxxx$ To find out how many such strings are possible, we need to find out the number of 5-letter strings of which 3 letters are the same and the other 2 letters are the same. That would be $\binom{5}{3}=\binom{5}{2}=10$. In general, $(x+y)^n$ is obtained by multiplying $n$ factors of $x+y$. In the expansion, a typical term is $x^{n-j} y^j$, which can be viewed as a $n$-letter string of $n-j$ of the letters are $x$ and $j$ of the letters are $y$. We can also look at the situation as choosing $j$ of the $n$ positions to write the letter y. There are $\binom{n}{j}$ many ways of writing $j$ instances of y in $n$ positions. Thus $\binom{n}{j} x^{n-j} y^j$ would be one of the terms in the final result of the expansion. This is the reason why $\binom{n}{j}$ is referred to as binomial coefficients. The binomial theorem shows how to derive the power of a binomial. The formula is: $\displaystyle (x+y)^n=\binom{n}{0} x^n+\binom{n}{1} x^{n-1}y^1+\binom{n}{2} x^{n-2}y^2+\cdots+\binom{n}{j} x^{n-j}y^j+\cdots+\binom{n}{n-1} x^{1}y^{n-1}+\binom{n}{n} y^n$. A more compact way of stating the binomial theorem is: $\displaystyle (x+y)^n=\sum \limits_{j=1}^n \binom{n}{j} x^{n-j}y^j$. ___________________________________________________________________________ A Recursive Formula The combination $\displaystyle \binom{n}{k}$ can be evaluated using calculator or software. We may not need the following formula for the purpose of calculation. However, it does provide a great deal of insight. $\displaystyle \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ The formula can be derived by the following thought process. A $k$-subset of a set of $n$ objects is a subset consisting of exactly $k$ elements. The quantity $\displaystyle \binom{n}{k}$ is the number of $k$-subsets of a set of $n$ objects. For our purpose here, the $n$ objects are the numbers $1,2,3,\cdots,n$. Let fix one of the objects, say 1. There are two types of $k$-subsets – the ones containing 1 and the ones not containing 1. The number of $k$-subsets of the first type is $\displaystyle \binom{n-1}{k-1}$. The point 1 is known to be in each $k$-subset of the first type and the other $k-1$ points must be chosen from $n-1$ objects. The number of $k$-subsets of the second type is $\displaystyle \binom{n-1}{k}$. The point 1 is not in each $k$-subset of the second type. So all $k$ are chosen from the other $n-1$ objects. Thus $\displaystyle \binom{n}{k}$ is the sum of these two numbers. ___________________________________________________________________________ Pascal’s Triangle No discussion of the binomial coefficients is complete without mentioning the Pascal’s triangle. The triangle is usually represented as an isosceles triangle (or an equilateral triangle). We use a right angle representation. $\begin{array}{rrrrrrrrr} 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 2 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 3 & 3 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 4 & 6 & 4 & 1 & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 5 & 10 & 10 & 5 & 1 & \text{ } & \text{ } & \text{ } \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & \text{ } & \text{ } \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & \text{ } \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \end{array}$ Each row in the triangle gives the binomial coefficients in the expansion $(x+y)^n$, starting at $n=0$. Thus the second row gives the coefficients for the expansion of $(x+y)^1$, the third row gives the coefficients for $(x+y)^2$ and so on. The most interesting part about the triangle is that it is recursive. Each row is derived from the previous row. Each cell in a row is the sum of the two cells in the row above it – the cell directly above and the cell to the left of that. For example, the last row in the above triangle shows the coefficients for $(x+y)^8$. The third number from the left is 28, which is the sum of 21 and 7. The fourth element 56 is the sum of 35 (the cell directly above it) and 21 (the cell to the left of 35). As a result, any row can be derived from the previous row. The next row will be for $(x+y)^9$ have the following coefficients: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 The Pascal’s triangle is really the recursive formula discussed above. A typical cell in the triangle is the binomial coefficient $\binom{n}{k}$. The cell directly above it is $\binom{n-1}{k}$. The cell to the left of that one is $\binom{n-1}{k-1}$. ___________________________________________________________________________ How Many Subsets Are There of a Given Set? Given $n$ objects, we now know that there are $\binom{n}{k}$ many sets of $k$ elements from these $n$ objects. There are $\binom{7}{3}=35$ many sets of 3 letters from the letters C, K, M, L, T, P and O. There are several ways to come up with the answer. One way is to use the binomial theorem. Let $x=y=1$ and $n=7$. Write out the binomial theorem. The following is the result. $\displaystyle 128=2^7=(1+1)^7=\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}+\binom{7}{5}+\binom{7}{6}+\binom{7}{7}$ There are 128 different subsets of the 7 letters (or any other set of 7 objects). The reason is given in the right side of the above equation, which is the sum of the number of subsets with zero elements, plus the number of subsets with exactly one element, plus the number of subsets with exactly two elements, …, plus the number of subsets with seven elements. When buying a hamburger at a fast food restaurant, customers can always add toppings. A basic hamburger comes with a beef patty inside a bun. A customer can choose to add toppings from this list: Cheese, Ketchup, Mustard, Lettuce, Tomato, Pickles and Onion (compare the first letters with the 7 letters indicated earlier). How many different hamburgers can be created? Basically the problem is to find out the number of different subsets of the 7 letters C, K, M, L, T, P and O. The answer is of course $2^7=128$. Interestingly the answer of 128 includes one choice that is the plain burger with no toppings – just the beef and the bun. So the total number of different hamburgers with at least one topping would be 127. In general, the total number of subsets of a set with $n$ elements is $2^n$. This is confirmed by the plugging $x=1$ and $y=1$ into the binomial theorem: $\displaystyle 2^n=(1+1)^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\cdots+\binom{n}{n-1}+\binom{n}{n}$ ___________________________________________________________________________ Exercises Exercise 1 Starting at Point P, a student walks 6 blocks to a diner for breakfast (represented by the red dot in the following diagram). After breakfast, the students 7 blocks to school that is located at Point Q. In how many ways can the student walk from Point P to Point Q? Assume that all the paths from any point to any point in the above diagram are available for walking. Figure 2 Exercise 2 In ordering a pizza, a customer can choose from a list of 10 toppings: mushroom, onion, olive, bell pepper, pineapple, spinach, extra cheese, sausage, ham, and pepperoni. • How many different pizza can the customer create if any topping in the list is desirable to the customer and if the customer chooses at least one topping? • Suppose that the customer is a meat lover. He will always choose the three meat toppings: sausage, ham and pepperoni. He will also choose up to 3 vegetable toppings. How many different pizza can the customer create? Exercise 3 A committee of 8 people is to be chosen from a class consisting of 8 men and 9 women. If the committee must consist of at least 3 men and at least 4 women, how many different committees are possible? Exercise 4 • In how many ways can a father divide 8 gifts among his two children if the eldest is to receive 5 gifts and the other child 3 gifts? • In how many ways can a father divide 8 gifts among his two children if one child is to receive 5 gifts and the other child 3 gifts? $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ Answers Exercise 1 315 Exercise 2 • 1023 • 792 Exercise 3 15876 Exercise 4 • 56 • 112 ___________________________________________________________________________ $\copyright \ 2017 \text{ by Dan Ma}$ Permutations and combinations This is the second post in a series of posts on combinatorial analysis. The first post is on the multiplication principle. This post introduces permutations and combinations. The starting point of the discussion on counting is the idea that if one event can occur in $M$ ways and another event can occur, independent of the first event, in $N$ ways, then the two events together can occur in $M \times N$ ways. This idea is often called the multiplication principle and is introduced in this previous post. ___________________________________________________________________________ Factorial Consider the eight letters A, B, C, D, E, F, G and H. How many ways can we order the 8 letters? The following shows two ordered arrangements. A-B-C-D-E-F-G-H C-B-F-A-D-G-H-E The multiplication principle can help us determine the number of all arrangements of 8 letters. We are trying to fill 8 objects into 8 positions. There are 8 choices for the first position. After the first letter is fixed, there are 7 letters for the second position. Continue with this approach, there will be only one letter left for the eighth position. In total, there are 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 ordered arrangements of 8 letters. A convenient notation for the answer is 8!, read 8 factorial. It is simply the product of the integers from 8 down to 1. In general, if $n$ is a positive integer, $n!$, read $n$ factorial, is the product of all the integers from $n$ down to 1. $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$ For the above definition of $n!$ to make sense, $n$ is a positive integer. We define 0! = 1 to make certain formulas easy to calculate. According to the above example, there are 8! many different ordered arrangements of 8 distinct objects (objects that are distinguishable from one another). Any ordered arrangement such as C-B-F-A-D-G-H-E is called a permutation of the 8 letters. In general, a permutation is an ordered arrangement of a set of objects that are distinguishable from one another. From the above example of 8 letters, we have the following observation. The total number of permutations of $n$ distinct objects is $n!$. The G8 summit is an annual meeting between leaders from eight of the most powerful countries in the world. There would be 8! = 40,320 different ways to line up the 8 leaders for a group photo. A permutation can be viewed as ranking. In a soccer league of 8 teams, there would be 8! = 40,320 different possible rankings. The factorial grows very rapidly. In ordering 9 objects, there are 9! = 362,880 permutations. 10! = 3,628,800 11! = 39,916,800 12! = 479,001,600 15! = 1,307,674,368,000 17! = 355,687,428,096,000 20! = 2,432,902,008,176,640,000 Thus the number of possible rankings of 12 job applicants is over 479 millions. The number of possible rankings of 20 job applicants would be a staggering number, over 2.4 quintillions! A quintillion is 10 raised to 18. In contrast, a trillion is 10 raised to 12. Example 1 Suppose that you have 12 books with 4 of them being novels, 4 of them being math books, 3 of them being science books and one being a history book. You want to place the books on the same level in a bookshelf. If the books are put in any order, then there would be 12! = 479,001,600 different placements of books. In how many ways can the books be placed in the bookshelf if all books of the same subject are to be together? The last question makes use of the multiplication principle in a subtle way. Consider the books arranged by subjects in this order: novel-math-science-history. By the multiplication principle, there are 4! x 4! x 3! x 1! = 24 x 24 x 6 x 1 = 3,456 many ordered arrangements. This is just for one specific way of the order of the 4 subjects – novel-math-science-history. There are 4! = 24 ways of order 4 subjects. Then the answer to the last question is 24 x 3,456 = 82,944. $\square$ ___________________________________________________________________________ Permutation Sometimes we do not order the entire set of $n$ objects. We only order a subset of the $n$ objects. Using the above example of 8 letters A, B, C, D, E, F, G and H, in how many ways can we arrange three letters from these 8 letters? The multiplication principle is at work here. We are attempting to fill 3 positions using 8 letters at our disposal. The first position has 8 choices. The second position has 7 choices and the third position has 6 choices. There are a total of 8 x 7 x 6 = 336 ordered arrangements. Three examples are A-B-C, G-A-H and E-B-F. Any one of these 336 ordered arranged is called 3-permutation of 8 letters. We can also call it a permutation of 8 letters taken 3 at a time. Example 2 To put the 8 letters in a context, suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose 3 students to fill three positions of President, Vice President and Treasurer of the math club? Based on the preceding discussion, the answer is 8 x 7 x 6 = 336. The following is a presentation of the calculation that gives the hint for a formula. $\displaystyle 8 \times 7 \times 6=\frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1}=\frac{8!}{5!}=\frac{8!}{(8-3)!}$ In general, any ordered arrangement of $k$ objects from a set of $n$ objects is called a $k$-permutation of $n$ objects. We can also call any such ordered arrangement a permutation of $n$ objects taken $k$ at a time. Here, we attempt to fill $k$ positions with objects selected from $n$ objects with $k \le n$. How many permutations of $n$ objects taken $k$ at a time? There are $n \times (n-1) \times (n-2) \times \cdots \times (n-(k-1))$ many different permutations of $n$ objects taken $k$ at a time. Some common notations for this number are $P(n,k)$ or $P_{n,k}$. According to the hint in Example 2, the following is a formula for $P(n,k)$. $\displaystyle P(n,k)=\frac{n!}{(n-k)!}$ is the number of permutations of $n$ objects taken $k$ at a time. Note that $P(n,n)$ is simply $n!$. Example 3 In evaluating 20 job applicants, there are 20! many possible rankings, which is over 2 quintillions as discussed above. A more sensible goal is to narrow the list to the top 5 candidates. The number of permutations of 20 candidates taken 5 at a time is $\displaystyle P(20,5)=\frac{20!}{15!}=20 \times 19 \times 18 \times 17 \times 16=\text{1,860,480}$ Example 4 Suppose that the psychology club at a university has 12 members in the lower division (consisting of freshmen and sophomores), 10 members in the upper division (consisting of juniors and seniors). Four awards (achievements in terms of overall grade, leadership potential, volunteerism, and public speaking) are given to each group. What is the total number of different outcomes if • a student can receive more than one award, • a student can receive only one award. If a student can be awarded more than once, then there are $12^4$ ways of giving out awards in the lower division and $10^4$ ways in the upper division, leading to the following answer. $\displaystyle 12^4 \times 10^4 = \text{207,360,000}$ If a student can only be awarded once, then the following is the answer. $\displaystyle P(12,4) \times P(10,4) =(12 \times 11 \times 10 \times 9) \times (10 \times 9 \times 8 \times 7)= \text{59,875,200}$ ___________________________________________________________________________ When Some Objects are Indistinguishable In calculating the number of permutations, the objects are assumed to be distinct. We now look at the situation where objects are separated into groups of indistinguishable objects. The goal is still finding the number of ordered arrangements. The number of permutations as calculated above would be an over count. The answer is obtained by dividing the inflated count by the amount of over counting. Example 5 How many different letter arrangements can be formed from the letters in the word BANANA? There are 6 letters in BANANA. Three of the letters are indistinguishable (A) and two of them are indistinguishable (N). If all the letters are distinguishable, then there are 6! permutations. But 6! = 720 over counts. By how many? Pretend all the letters are distinguishable. Take the arrangement $A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2$. Now permute the A’s and the N’s. Doing so should result in 3! x 2! = 12 permutations. $A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2$ $A_1 \ A_3 \ A_2 \ B \ N_1 \ N_2$ $A_2 \ A_1 \ A_3 \ B \ N_1 \ N_2$ $A_2 \ A_3 \ A_1 \ B \ N_1 \ N_2$ $A_3 \ A_1 \ A_2 \ B \ N_1 \ N_2$ $A_3 \ A_2 \ A_1 \ B \ N_1 \ N_2$ $A_1 \ A_2 \ A_3 \ B \ N_2 \ N_1$ $A_1 \ A_3 \ A_2 \ B \ N_2 \ N_1$ $A_2 \ A_1 \ A_3 \ B \ N_2 \ N_1$ $A_2 \ A_3 \ A_1 \ B \ N_2 \ N_1$ $A_3 \ A_1 \ A_2 \ B \ N_2 \ N_1$ $A_3 \ A_2 \ A_1 \ B \ N_2 \ N_1$ But in reality, all of the 12 permutations are the same: $A \ A \ A \ B \ N \ N$. So each unique permutation appears 12 times in the count 6!. Thus the correct count is $\displaystyle \frac{6!}{3! \ 2! \ 1!}=60$ In general, $\displaystyle \frac{n!}{m_1! \ m_2! \ \cdots \ m_k!}$ is the number of permutations of $n$ objects, of which $m_1$ are alike, $m_2$ are alike, …, $m_k$ are alike, where $m_1+\cdots+m_k=n$. ___________________________________________________________________________ Combination In all the above instances of counting, the focus is to find all ordered arrangements (or permutations) of a set of objects. We now focus on the different subsets of $k$ elements that can be chosen from a set of $n$ objects. In this setting, the goal is not to count ordered arrangements. The goal is to count the number of subsets of a certain size. For example, let’s say you want to buy a 2-scoop ice cream cone of different flavors chosen from 3 flavors – Chocolate (C), Strawberry (S) and Vanilla (V). Suppose you do not care which flavor is on top and which one is at the bottom. The different subsets of size 2 would be: CS, CV, and SV. Here, CS is not an ordered arrangement. It just means that the two chosen flavors are chocolate and strawberry. If order matters, then there would be six outcomes – CS, SC, CV, VC, SV, and VS. So the approach is to find the number of permutations (an over count) and then divide the amount of over count. Example 6 Suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose three students to form a committee of three? The number of permutations of three students is 8 x 7 x 6 = 336. This count is inflated since there are many repeats reflected in this count. For example, if the chosen students are Abby, Beth and Chloe, then there are 3! = 6 ways to order these three students – ABC, ACB, BAC, BCA, CAB and CBA. So each set of three students is reflected 6 times in the inflated count of 336. So the answer is 336 / 6 = 56. Thus there are 56 possible groups of three students when three students are chosen from 8 students. The following calculation makes the formula clear. $\displaystyle \frac{8 \times 7 \times 6}{3!}=\frac{8 \times 7 \times 6 \times 5!}{3! \ 5!}=\frac{8!}{3! \ 5!}$ In general, $\displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!}$ is the number of different groups of size $k$ that could be chosen from a set of $n$ distinct objects where $k=0,1,2,\cdots,n$. The number $\binom{n}{k}$ is called a binomial coefficient and is pronounced “$n$ choose $k$.” Other notations for $\binom{n}{k}$ are $_nC_k$, $C_{n,k}$ and $C(n,k)$. Example 7 A committee of five is to be chosen from a group of 11 people consisting of 5 men and 6 women. • How many different committees of five people can be formed? • How many different committees consisting of 2 men and 3 women can be formed? • How many different committees of five consisting of either 2 men or 2 women? The number of possible committees of five would be $\binom{11}{5}=462$. For the second problem, note that there are $\binom{5}{2}=10$ possible groups of 2 men and there are $\binom{6}{3}=20$ groups of 3 women. By the multiplication principle, there are 10 x 20 = 200 different groups of 5 people consisting of 2 men and 3 women. For the third problem, there are two cases: a committee of 2 men and 3 women or a committee of 2 women and 3 men. The answer is the sum of these two cases. Thus the answer is $\displaystyle \binom{5}{2} \times \binom{6}{3}+\binom{5}{3} \times \binom{6}{2}=10 \times 20+10 \times 15=350$ ___________________________________________________________________________ More Examples We present a few more examples to demonstrate the ideas discussed here. Exercises are given at the end. Example 8 A child plays with a set of 12 blocks, 4 of which are red, 4 of which are black, 3 of which are white and one of which is yellow. In how many ways can these blocks be arranged in a row? In how many ways can these blocks be arranged in a row in such a way that all blocks of the same color are together? Note the similarity with Example 1. Both problems concern with a collection of 12 objects that can be separated into 4 sub groups. In Example 1, the objects in each sub group are distinguishable while the objects in this example are indistinguishable in each sub group. As a result, the formula discussed in the section “When Some Objects are Indistinguishable” would apply. Here’s the number of different ways to order the blocks. $\displaystyle \frac{12!}{4! \ 4! \ 3! \ 1!}=\text{138,600}$ For the second question, the answer would be 4! = 24. Unlike Example 1, we do not need to order the blocks within the same color since they are indistinguishable. $\square$ Example 9 The tennis team in School A has 12 players and the tennis team in School B has 14 players. If 5 players are selected from each team and then paired off for a tennis game, how many results are possible? There are $\binom{12}{5}=792$ ways of choosing 5 players from Team A. There are $\binom{14}{5}=2002$ ways of choosing 5 players from Team B. There are 5! = 120 ways in pairing off the two teams of 5 players. Thus there are 792 x 2002 x 120 = 190,270,080 ways of choosing two teams and then pairing them off for a tennis game. $\square$ Example 10 A company is made up of 3 departments with the one department consisting of 8 employees, the second department consisting of 10 employees and the third department consisting of 5 employees. The owner of the company decides to promote two employees chosen from the 23 employees. Suppose that the two employees are selected at random. How many ways can the two employees be selected if • both promotions are from the same department? • both promotions are from different departments? The problem does not mention the positions for the promotion. Thus we assume that the two positions are identical. The first question has three cases based on the departments. The following is the sum of the three cases. $\displaystyle \binom{8}{2}+\binom{10}{2}+\binom{5}{2}=28+45+10=83$ For the second question, there are $\binom{3}{2}=3$ cases, based on pairs of departments. The following is the sum of the 3 cases. $\displaystyle \binom{8}{1} \times \binom{10}{1}+\binom{8}{1} \times \binom{5}{1}+\binom{10}{1} \times \binom{5}{1}=80+40+50=170$ Example 11 The problem is the same as Example 10 except that the two promotions are for President and Vice President. Now that the two promotions are different, order matters. Thus use permutations to perform the calculations. the answer to the first question is: $\displaystyle \frac{8!}{(8-2)!}+\frac{10!}{(1-2)!}+\frac{5!}{(5-2)!}=56+90+20=166$ In the second question, we still pick one person from each department, but it needs to be multiplied by two since the positions are different. $\displaystyle 2 \times 8 \times 10+2 \times 8 \times 5+2 \times 10 \times 5=160+80+100=340$ ___________________________________________________________________________ Exercises Exercise 1 How many different letter arrangements can be formed from the letters in the word MISSISSIPPI? Exercise 2 In how many ways can a manager assigns 3 different jobs at random to 11 available workers? Exercise 3 Suppose that the license plates for a certain state consist of three numbers and three letters. How many different license plates are possible if 1. the letters must come before the numbers? 2. all letters must appear together and all numbers must appear together? 3. only the letters must appear together? 4. there is no restriction on the positions of the letters and numbers? Exercise 4 In ordering a pizza, cheese and tomato sauce come with the pizza. The customer can also choose to add toppings from the following lists: Meat items: ham, sausage, pepperoni, salami, chicken. Vegetable items: pineapple, olive, mushroom, onion, bell peppers. 1. How many distinct pizzas are possible? 2. Suppose that a customer does not like salami and sausage in the meat list and onion and olive in the vegetable list and thus will not add these toppings. How many different pizzas are possible? 3. Suppose that a customer would like to add two meat items and three vegetable items as toppings. How many different pizzas are possible? 4. Suppose that a customer would like to add exactly 5 toppings. How many different pizzas are possible? 5. Suppose that a customer would like to add at most 5 toppings. How many different pizzas are possible? Exercise 5 1. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as assembly line workers. How many ways can the workers be assigned to the factories? 2. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as manager, assistant manager and assembly line worker. How many ways can the workers be assigned to the factories? $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ Answers Exercise 1 34,650 Exercise 2 990 Exercise 3 1. 17,576,000 2. 35,152,000 3. 70,304,000 4. 351,520,000 Exercise 4 1. 1024 2. 64 3. 100 4. 252 5. 638 Exercise 5 1. 369,600 2. 479,001,600 ___________________________________________________________________________ $\copyright \ 2017 \text{ by Dan Ma}$ The multiplication principle This is the first post in a series of posts on combinatorial analysis, which is a study on counting, e.g. finding effective methods for counting the number of ways to arrange objects and for counting the number of ways events can occur. Many problems in mathematics, e.g. in probability theory, require the counting of the number of ways an event can occur. Permutations and combinations are basic ideas in counting. Both ideas are based on an idea called the multiplication principle. This post focuses on the multiplication principle. The next post is on permutations and combinations. ___________________________________________________________________________ The Multiplication Principle Let’s start with some examples. Example 1 Jack is buying ice cream – two scoops of ice cream of the same flavor on either a cone or a cup. The available flavors are vanilla, strawberry, chocolate, butter pecan, mint chocolate chips and rocky road. How many possible arrangements of ice cream are available for Jack? The answer is 2 x 6 = 12 arrangements. The following lists out all the possibilities. Cone-Vanilla Cone-Strawberry Cone-Chocolate Cone-Butter Pecan Cone-Mint Chocolate Chips Cone-Rocky Road Cup-Vanilla Cup-Strawberry Cup-Chocolate Cup-Butter Pecan Cup-Mint Chocolate Chips Cup-Rocky Road With the cone option, there are 6 choices for flavors. With the cup option, there are also 6 choices for flavors. So the total number of possible choices would be 6 + 6 = 2 x 6 = 12. Of course, if Jack only limits his purchase to his most favorite ice cream (say mint chocolate chips), then there would be only two choices, cone or cup. But if he is indifferent to the flavors, there would be 12 arrangements as listed above. $\square$ The listing in Example 1 suggests a general principle. The Multiplication Principle If one event can occur in $M$ ways and another event can occur independent of the first event in $N$ ways, then the two events successively can occur in $M \times N$ ways. Of course, the principle just described has an obvious generalization. Instead of just considering two events, we can count how many ways a series of events can occur. As long as the events are independent, the total number of ways all events occurring in a row is obtained by simply multiplying the numbers of possible occurrences of the individual events. Example 2 The following is a menu for a banquet. Assuming that each guest can only pick one item for each course, how many different possible dinner decisions are possible? This problem is mentioned in previous post. Using the multiplication principle, the answer is 4 x 2 x 3 x 2 = 48 choices. $\square$ Remark. For the multiplication principle to apply, the events must be independent. This means that the number of occurrences of the one event is not restricted by the previous event. If a guest in the banquet is indifferent to all items in the menu (if taken individually) but does not like to mix certain items (e.g. he does not like to have French onion soup to go with goat cheese salad), then he or she might not have 48 choices. The following example illustrates that for a certain kind of dependency between events, the multiplication principle can still apply. Example 3 A PIN code for a bank ATM machine is a 4-digit number. Determine the following: • How many PIN codes are possible? • How many PIN codes are possible if no repetition of digits is allowed? • How many PIN codes are possible if the first two digits form a number less than or equal to 33 and the last two digits form a number that is at least 3 times the first two digits? There are $10 \times 10 \times 10 \times 10= 10^4=10,000$ many possible codes. If no digits can repeat, then there are $10 \times 9 \times 8 \times 7=5040$ different codes. For the no repetition case, there are 10 choices for the first digit. Once the first digit is fixed, there are only 9 choices for the second digit. Once the first two digits are fixed, there are 8 choices for the third digit. Then the fourth digit has 7 choices once the first three digits are fixed. Though the number of choices for each digit is limited by the previous digit, it is the same regardless the value of the previous digits. Thus the principle still applies. The third problem illustrates a dependency that makes the multiplication principle not applicable. For example, if the first two digits are 01, the last two digits would be 03, 04, 05, 06, …, 99 for a total of 97 possibilities. If the first two digits are 02, then there are 94 possibilities for the last two digits (06, 07, …, 99). As the number for the first two digits increases to 33, the number of choices for the last two digits would decrease. The largest possibility for the first two digits would be 33 and there is only one choice for the last two digits (99). Thus the multiplication principle would not work here. The answer is not obtained by multiplication. It is obtained by adding up all the possibilities as the first two digits go from 01 to 33. We perform the calculation in Excel and the answer is 1617. Of course, the third problem is not a realistic way to obtain pass codes. It is just an illustration of a case where the multiplication principle does not apply. $\square$ We look at more examples. Example 4 In how many ways can 9 students (4 males and 5 females) stand in a row for a group photo • if there is no restriction on the standing positions? • if the females must stand together and the males must stand together? • if the females must stand together? If the students can stand anywhere they want, there are 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880 ways of arranging these 9 students in a row. For the first spot, there are 9 students to choose from and there are 8 students to choose from for the second spot and so on. A convenient notation for the answer is 9! (read 9 factorial). It simply means that it is the product of all the integers from 9 down to 1. By the same reasoning, there are 5! = 120 ways of arranging 5 persons in a row. There are 4! = 24 ways of arranging 4 people standing in a row. If the females stand on the left and the males stand on the right, then there are 120 x 24 = 2,880 arrangements in a row for the 9 students. The answer is 2 x 120 x 24 = 5,760 since there is also the case of males standing on the left and females on the right. The third problem requires that only the females must stand together. The use of the multiplication principle is subtle. If the females must stand together, think of all the females as one unit. There are 5 units – 4 males and one combined unit of females. There are 5! ways of arranging the 5 units. Within the combined unit of females, there are 5! ways of arranging the 5 females. Thus the answer is 5! x 5! = 120 x 120 = 14,400. $\square$ The next example shows that the multiplication principle is invaluable in calculating large numbers. Example 5 In general, longer passwords are stronger passwords. The principle of counting discussed here can be used to quantify the strength. Consider an 8-character password consisting of letters from English. To start, let’s say the letters in the password are all upper case or all lower case, i.e. the password is case insensitive. Then the number of possible passwords would be $\displaystyle 26 \times 26 \times 26 \times 26 \times 26 \times 26 \times 26 \times 26=26^8=\text{208,827,064,576}$ That’s over 208.8 billions possibilities. What if the password is case sensitive? If each character in the password can be in upper case or in lower case, then each character has 52 choices (26 upper case letters and 26 lower case letters). Then the number of possible passwords would be $\displaystyle 52 \times 52 \times 52 \times 52 \times 52 \times 52 \times 52 \times 52=52^8=\text{53,459,728,531,456}$ That’s over 53 trillions possible passwords! Of course, the length of the password by itself may not mean strength. For example, people may use familiar words to form the password. One of the famous examples would have to be “Password”. In addition to being long enough, the characters in the passwords should be randomly chosen if possible. To make the 8-character password even stronger, we can include numbers in addition to letters. Then the total number of possibilities is $\displaystyle 62^8=\text{218,340,105,584,896}$ which is over 218 trillions. $\square$ ___________________________________________________________________________ Factorial The factorial concept introduced in Example 4 is a useful tool in counting. If $n$ is a positive integer, the number $n!$ is defined to be the product of all the positive integers less than or equal to $n$. $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$ For convenience, we define 0! = 1. In Example 4, 9! is the number of ways of ordering 9 people in a row. In general, $n!$ is the number of ordered arrangements of $n$ distinct objects. There will be more discussion about this interpretation of $n$ factorial in the next post. ___________________________________________________________________________ Exercises Exercise 1 Example 3 and Example 5 concern with finding the number of possible ordered arrangements of objects for use in setting passwords or pass codes. Here’s is an example involving license plates. When a motor vehicle authority (or some relevant governmental body) designs license plates for automobiles, one important goal is to have a sufficiently large number of possibilities to accommodate all the vehicles in that jurisdiction. Suppose that the license plate has 7 characters. The first character is a number and the next three characters are letters. The last three characters are numbers. 1. What is the total number of possibilities in this license plate design? 2. If the motor vehicle authority is beginning to issue license plates with the first digit being 3, how many license plates will the authority have to issue before switching to using 4 as the first digit? Exercise 2 1. Twelve tasks are to be assigned to twelve workers. What is the total different number of job assignments? 2. In how many ways can four students be randomly selected to receive four cash prizes (10, $20,$30, \$40)?

Exercise 3

1. In how many ways can 4 boys and 4 girls stand together in a row for a group photo?
2. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if people of the same gender must be together?
3. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if only the girls must be together?
4. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if no people of the same gender can stand together?

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

Exercise 1

• 175,760,000
• 17,576,000

Exercise 2

• 479,001,600
• 11,880

Exercise 3

• 40,320
• 1,152
• 2,880
• 1,152

___________________________________________________________________________
$\copyright \ 2017 \text{ by Dan Ma}$

A banquet menu can be a lesson in counting

The above is a menu found in the Internet. Though we do not know how the dishes taste, the menu seems enticing. Whatever the eventual quality of the food, it is a well crafted menu. There are choices for each course. Assuming you can only pick one choice for each course, how many possible choices does a guest have for a complete meal in this banquet?

The above question is a counting problem, which in this case is easy to answer. The answer is derived by multiplying a few numbers. However, the significance of the problem is broader than the procedure to get the answer. The fundamental ideas behind this and other “easy” examples form a foundation of the mathematical subject called combinatorics. In order to help build a firm foundation, we devote several posts introducing the subject of counting, starting from the fundamental notions.

___________________________________________________________________________
$\copyright \ 2017 \text{ by Dan Ma}$