A lesson on enumerations and combinatorics.

Permutations and Combinations: Lesson

So far, you have learned many techniques to enumerate members of a set. Well done! In a real-world problem, however, arranging or selecting from a set of items may not be so straightforward. A single enumeration problem may require you to consider many different possible situations. It is because of this, some enumeration problems are solved by breaking the problem down into subcases, enumerating those using techniques from previous exercises, and then combining the results by using the addition principle, the multiplication principle, or any combination of the two.

Consider this example: vehicles registered in the state of New York are issued license plates that consist of three letters followed by a four-digit number. How many different license plates can be issued to cars registered in New York? To solve this problem, we can break it down into two subproblems. Namely, we want the number of ways to pick three letters AND the number of ways to pick a four-digit number. We can pick any three letters in 26 3 ways to get 17,576 possible arrangements of letters. Then we can pick any four-digit number in 104 ways to get 10,000 possible arrangements of four-digit numbers. We then multiply the two numbers to get 175,760,000 possible license plates.

Breaking a Problem Down Into Subcases

An ice cream parlor offers 27 different flavors of ice cream! Customers are allowed to fill their ice cream cone with three flavors of their choosing. How many different ice cream treats can be constructed? For the first scoop, a customer can pick one out of 27 flavors. For the second scoop, they can also pick one out of the 27, and the same goes for the third. 

This means that there are 27 options for the first scoop "and" 27 options for the second scoop "and" 27 options for the third scoop. 

The total number of ways to construct an ice cream cone is:

```tex
Number \ of \ ways = 27 \times 27 \times 27 = 27^3 = 19,683
```

In general, when you have to pick *r* items out of *n* possible choices with repetition allowed, the number of ways to do this is:

```tex 
n \times n \times n \ldots \times n = n^r
```

Enumerations With Repetition

Until now, we have considered enumerations where the order of arrangement or selection matters. In the last exercise, one flight itinerary chosen could be New York, Virginia, Florida, Louisiana, Texas, Nevada, California.

Or it could be New York, Florida, Virginia, California, Texas, Louisiana, Nevada,

The first itinerary is a logical and efficient way of traveling as it requires a minimal change in direction. The second itinerary is an inefficient way to travel as the seemingly random selection of states requires many directional changes.

In this scenario, the order in which the states are visited is important as it will affect the efficiency of the trip. To plan the most efficient trip possible, we can hire a company that will plan the trip for us. All we have to do is provide any list of seven states and the company will offer the best route possible. The order of the list of states we provide is now irrelevant. How many ways can we compose a list of seven US states?

Initially, we had *P(50, 7)* different lists. This number is now reduced as any selection of seven states, ordered in any fashion, will produce the same outcome. Any list of seven states generated can be ordered in *7!* different ways, all of which will return the same single list from the travel company. This scales *P(50, 7)* by *7!*, which is:

```tex
\frac{P(50,7)}{7!} = \frac{50!}{7!(50-7)!} = 99,884,400
```

An enumeration of distinct objects where the order does not matter is called a *combination*; it is the permutation of *k* items out *n* possible choices scaled by *k!*. The formula for this is:

```tex
C(n, k) = \frac{n!}{k!(n-k)!}
```

This operation is also called "choose" because we say "out of *n* items, choose *k*". We also denote it like this:
``` tex
C(n, k) = \binom{n}{k} =\frac{n!}{k!(n-k)!}
```

Note the following identities: 

```tex
C(n,n) = 1
```
```tex
C(n,1) = n
```


Combination

In this exercise, we will explore how to enumerate elements of a *multiset* (a set that contains elements that are not necessarily distinct). Consider the problem of having to determine the number of permutations of the letters in the word CODE. From previous exercises, we know the number of permutations is *4!*. What about the word CODEC? Claiming the answer is *5!*, as you did for the word CODE, would be incorrect. This is because the letter C appears more than once. If we write the word like this C1ODEC2, the following permutation of the word exists: C2ODEC1 which is the same as the original word. Since both C’s are identical, it is irrelevant which one is in which position. Therefore we must scale the number of permutations down. To do this, we consider that the order of the two C's, in whichever spot they appear, does not matter. Sounds familiar? That's right, we scale down by *2!*. So the number of permutations of the word CODEC is:

```tex
\frac{5!}{2!} = 60
```

If we were permuting a word with more than one repeated character, we would further scale down the permutations by the count of the other repeated letters. Generally speaking, the number of permutations of a multiset is:

```tex 
P(n; r_1, r_2, \ldots, r_k) = \frac{n!}{r_1! r_2! \ldots r_k!}
```

Where *n* is the total size of the multiset and each of *rk's* represents the count of each element.

Another way of computing this is to “choose” a spot for each element. Consider the word GOOGLE, how many permutations of this word can we have? We "choose" two spots for the G's, "and" we "choose" two of the remaining spots for the O's, "and" we "choose" one remaining spot each for the L and the E:


```tex 
P(6;2,2,1,1)= \binom{6}{2} \binom{6-2}{2} \binom{4-2}{1} \binom{1}{1} = 180
```



Formally:

```tex
P(n; r_1, r_2, r_3 \ldots, r_k)= \binom{n}{r_1} \binom{n-r_1}{r_2} \ldots \binom{n - r_1 - \ldots - r_{k-1}}{r_k}
```

Permutations With Identical Items

In this lesson, we will explore the concept of a permutation. A *permutation* is an arrangement or selection in which the order matters.

Consider this scenario: a college student has just purchased a new bookshelf for her dorm room and she has a total of *n* books that she wishes to arrange on the shelf. How many different ways can she arrange her books? 

For the first spot on the shelf, she has *n* different options for the placement of a book. Next, since one book has already been placed, she now has *n-1* books to place in the second spot. She will then have *n-2* books for the third spot, *n-3* books for the fourth spot, and so on. Suppose she has nine books in total, the arrangement of the bookshelf will look like this:

```tex
\underline{9} \ \underline{8} \ \underline{7} \ \underline{6}\ \ldots \ \underline{1}
```

So there are:
```tex 
9 \times 8 \times 7 \times \ldots \times 1 = 362,880
```
ways to arrange the books.

For a general arrangement of *n* items, we have:

```tex 
n(n-1)(n-2) \ldots 1 = n!
```
Here, the *!* is the factorial operator.

Arranging *n* items without repetition results in *n!* a number of permutations.

Note the following identities:
* 0! = 1
* The factorial operation is undefined for numbers less than zero.


Permutation

In this exercise, we will explore problems in which we have to choose *r* items from *n* different varieties. Consider this example: a taco restaurant offers three options of taco to choose from. You can pick a steak taco, a chicken taco, or a veggie taco. You wish to order a total of eight tacos. In this situation, the set of tacos is S = {chicken, steak, veggie} which has three distinct elements and you wish to order more than three. 

How many ways can you do this? If the sequence matters, the answer is 38. How many ways are there to do this if the sequence doesn’t matter? The brute force way to compute this calculation is to consider every possible combination of tacos and then sum them all up. While this calculation would work it is not efficient! We need a better way. 

Let’s say you present your order in the following manner: xx|xxxx|xx. This means you want two chicken tacos, four steak, and two veggie. This order xxx|xxx|xx means you want three chicken, three steak, and two veggie. This illustrates the technique we can use to determine how many different ways there are to order eight tacos. This means that we have ten available spaces for tacos (x) and two delimiters (|). So to answer the question, out of the ten available spots we choose eight of them for tacos and the remaining spots for delimiters. 

```tex
C(10, 8) = \binom{10}{8} \binom{2}{2} = 45
```
45 different combinations of tacos!

To put it formally, when selecting *r* items from a multiset of *n* distinct items we have:

```tex
C(r + n - 1, r) = \frac{(r + n - 1)!}{r!(n-1)!}
```
Different combinations. Note that we have *n-1* because the amount of delimiters we need is one less than we have items in our multiset.

Selecting Items From a Multiset

An *enumeration* is defined as the number of ways to select from, or arrange, a set of *n* objects. Before we can begin studying this process, we have to explore some fundamental concepts. 

Let's say you have two different sets of objects (here, by "set" we mean the mathematical definition of a set), and you want to figure out how many different ways you can pick one object from either set. Set A has ten objects in it and set B has five objects in it. You can either pick one object from set A or one object from set B. The total number of possible objects that you can have is simply the sum of the number of objects in set A and set B, so the answer is 15. This is known as the *addition principle*. 

Let’s say, however, you wish to pick an object from set A and set B. For every option from set A, you have an option from set B. This means the number of ways of selecting one object from set A and one object from set B is the product of the number of objects in two sets. In this case, the answer is *10(5) = 50*. This is known as the *multiplication principle*. 

As a general rule:
* If you find yourself saying "or," you have to add.
* If you find yourself saying "and" or "for every," you have to multiply.


Enumeration

If we want to find out the number of ways NOT to do something, we could break it down into the subcases that are allowed and then combine those. Sometimes this may be inefficient as there might be many more subcases that are allowed than there are ones that are not. We note that a subcase may either be allowed or not allowed leading to the following equation:

```tex
total \ number \ of \ ways = \sum{subcases \ allowed} + \sum{subcases \ not \ allowed}
```


From this equation, we can see that if the number of cases not allowed is smaller than the number of cases allowed, we can calculate the number of cases allowed by rearranging the formula to get

```tex

\sum{subcases \ allowed} = total \ number \ of \ ways - \sum{subcases \ not \ allowed}
```

Let’s see how this works. How many ways can we rearrange the letters in the word YAHOO such that the two O’s are not together? We could consider every possible case in which the two letters are not together (YAOHO + OYAHO + etc…) which requires much more work than simply counting the number of ways the two letters are together and the total number of ways we can rearrange the word. The total number of permutations of the word YAHOO is:

```tex
\frac{5!}{2!}
```
Remember, we divide by *2!* because there are two O’s.

The number of ways we can rearrange the word with the two O’s next to either is done by combining the two O’s into one super letter and then computing the number of arrangements we can have of the letters *Y*, *A*, *H*, and *OO* so *4!*. So the total number of ways NOT allowing the two O’s together is

```tex
 \frac{5!}{2!} - 4! = 36
```

36 ways of rearranging the word YAHOO without the two O’s being together.


Set Exclusion

When enumerating a multiset, we are sometimes interested in the relative order of some members of the set. Take for example the problem of figuring out how many ways we can order the letters in the word APPLE such that the two P’s appear next to one another (ELPPA for example). The set of letters in this problem is  *S = {A, P, P, L, E}* which is a set of cardinality five. Since we want the two P’s together, we can treat them as a single element PP. The set now looks like this: *S = {A, PP, L, E}* of cardinality four. We would enumerate this using the same technique as we did in Exercise 2 to obtain an answer of:

```tex
4! = 24
```
There are 24 possible permutations of the word APPLE in which the two P’s are next to one another.


Element Composition

In the previous exercise, you learned how to compute the number of permutations of *n* items. What if you were only interested in the permutation of *r* out of those *n* items (permutation of four out of seven items for example)? Let's see how we can do this.

Consider this problem: a website with weak password requirements requires that its users produce a password of five distinct, lowercase, English letters. How many possible permutations of passwords exist? 

The English alphabet has 26 letters in it and your password only requires five distinct characters (which will produce weak passwords), therefore you have:

```tex
26 \times 25 \times 24 \times 23 \times 22 = 7,893,600
```

different possible passwords! A computer can easily brute force this password in a short amount of time.

The general formula for this is:

```tex
P = n(n-1)(n-2)(n-3)(n-4)
```

However, this is only valid for five options!

In the general case, if we have *n!* total permutations but we only want *r* options, we need to eliminate the remaining *n-r* possible options. We do this by dividing *n!* by *(n-r)!* leaving us with the *r* terms we want.

The formula for selecting (or arranging) *r* distinct objects from a set of *n* possible objects where their order matters and repetition is not allowed is:

```tex
P(n,r) = \frac{n!}{(n-r)!}
```

Note the identity:

```tex
P(n,n) = \frac{n!}{(n-n)!} =\frac{n!}{0!} = n!
```

Permutations of a Subset

Congratulations on getting this far! We’ve covered a lot of topics in the fundamentals of combinatorics and as of now, you should have a solid understanding of the topic! Let’s briefly recap the important concepts and formulas.

* Enumeration means arranging or selecting items from a set/multiset.
* The Addition and Multiplication Principle
    * “And” or “for every” means multiply
    * “Or” means add
*  The number of ways to enumerate *r* items from a set of *n* distinct elements:
    * Order matters; repetition allowed: 
```tex 
n \times n \times n \ldots \times n = n^r
```
    * Order matters; repetition not allowed (permutation):
```tex
P(n,r) = \frac{n!}{(n-r)!}
```
    * Order does not matter; repetition not allowed (combination):
```tex
C(n,k) = \frac{n!}{k!(n-k)!} = \binom{n}{k}
```
    * Order does not matter; repetition allowed:
```tex
C(r + n - 1, r) = \frac{(r + n - 1)!}{r!(n-1)!}
``` 
* Permutations of a multiset:
```tex 
P(n; r_1, r_2, \ldots, r_k) = \frac{n!}{r_1! r_2! \ldots r_k!}  = \binom{n}{r_1} \binom{n-r_1}{r_2} \ldots \binom{n - r_1 - \ldots - r_{k-1}}{r_k}
``` 
* Solving an enumeration problem sometimes requires breaking it down into subcases, solving those, and then combining those solutions.  

* If you have a case where there are more cases allowed than not allowed, it may be easier to deduct the disallowed cases from the total to determine the number of allowed cases.

```tex
\sum{subcases \ allowed} = total \ number \ of \ ways - \sum{subcases \ not \ allowed}
```
Excellent work!!