Front Matter

0Introduction and also Preliminaries

1Counting

2Sequences

3Symbolic Logic and Proofs

4Graph Theory

5Additional Topics

Backmatter


Authored in PreTeXt
*

Section1.3Combinations and also Permutations

¶Investigate!8

You have actually a bunch of chips which come in five different colors: red, blue, green, purple and also yellow.

How numerous different two-chip stacks have the right to you make if the bottom chip need to be red or blue? explain your answer utilizing both the additive and also multiplicative principles.

You are watching: How many ways to arrange 6 letters

How many different three-chip stacks have the right to you make if the bottom chip need to be red or blue and the optimal chip should be green, violet or yellow? how does this problem relate come the previous one?

How plenty of different three-chip stacks are there in which no color is repeated? What around four-chip stacks?

Suppose you wanted to take three different colored chips and also put lock in her pocket. How many different options do you have? What if you wanted four different colored chips? how do these troubles relate come the vault one?

A permutation is a (possible) rearrangement of objects. For example, there room 6 permutations that the letter a, b, c:

\beginequation*abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba.\endequation*

We recognize that we have them all provided above —there room 3 selections for which letter we put first, then 2 choices for i m sorry letter comes next, i beg your pardon leaves only 1 selection for the critical letter. The multiplicative principle says we main point \(3\cdot 2 \cdot 1\text.\)

Example1.3.1

How plenty of permutations are there that the letter a, b, c, d, e, f?


Solution

We carry out NOT want to try to list all of these out. However, if we did, we would should pick a letter to create down first. There room 6 selections for the letter. Because that each selection of an initial letter, there space 5 selections for the second letter (we can not repeat the very first letter; we are rearranging letters and also only have actually one that each), and also for every of those, there space 4 choices for the third, 3 selections for the fourth, 2 selections for the fifth and finally just 1 choice for the last letter. For this reason there space \(6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\) permutations of the 6 letters.


A piece of notation is helpful here: \(n!\text,\) review “\(n\) factorial”, is the product of all positive integers less than or same to \(n\) (for reasons of convenience, we also define 0! to be 1). So the variety of permutation of 6 letters, as watched in the previous instance is \(6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text.\) This generalizes:

Permutations the \(n\) elements

There room \(n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1\) permutations that \(n\) (distinct) elements.

Example1.3.2Counting Bijective Functions

How numerous functions \(f:\1,2,\ldots,8\ \to \1,2,\ldots, 8\\) are bijective?


Solution

Remember what it method for a function to it is in bijective: each element in the codomain need to be the image of exactly one facet of the domain. Utilizing two-line notation, we could write one of these bijections as

\beginequation*f = \twoline1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8 3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4\endequation*

What we are really act is simply rearranging the elements of the codomain, so us are creating a permutation that 8 elements. In fact, “permutation” is another term offered to describe bijective features from a finite set to itself.

If you believe this, climate you view the answer should be \(8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text.\) You have the right to see this directly as well: for each aspect of the domain, we must pick a distinct element of the codomain come map to. There room 8 choices for where to send 1, climate 7 selections for wherein to send 2, and so on. We multiply using the multiplicative principle.


Sometimes we do not desire to permute every one of the letters/numbers/elements we are given.

Example1.3.3

How many 4 letter “words” have the right to you make from the letter a through f, with no repetitive letters?


Solution

This is just like the problem of permuting 4 letters, only currently we have much more choices for each letter. For the very first letter, there space 6 choices. For each the those, there room 5 options for the second letter. Climate there are 4 options for the 3rd letter, and also 3 selections for the last letter. The total variety of words is \(6\cdot 5\cdot 4 \cdot 3 = 360\text.\) This is no \(6!\) due to the fact that we never multiplied by 2 and also 1. We can start through \(6!\) and also then release the 2 and also 1, and also thus create \(\frac6!2!\text.\)


In general, we deserve to ask how plenty of permutations exist that \(k\) objects picking those objects indigenous a larger collection of \(n\) objects. (In the example above, \(k = 4\text,\) and \(n = 6\text.\)) We compose this number \(P(n,k)\) and also sometimes contact it a \(k\)-permutation the \(n\) elements. Indigenous the instance above, we view that come compute \(P(n,k)\) we must apply the multiplicative rule to \(k\) numbers, starting with \(n\) and counting backwards. For example

\beginequation*P(10, 4) = 10\cdot 9 \cdot 8 \cdot 7.\endequation*

Notice again that \(P(10,4)\) starts out looking favor \(10!\text,\) but we stop after 7. We deserve to formally account because that this “stopping” by separating away the component of the factorial we do not want:

\beginequation*P(10,4) = \frac10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 16 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = \frac10!6!.\endequation*

Careful: The factorial in the denominator is not \(4!\) yet rather \((10-4)!\text.\)

\(k\)-permutations the \(n\) elements

\(P(n,k)\) is the variety of \(k\)-permutations that \(n\) elements, the number of ways come arrange \(k\) objects favored from \(n\) unique objects.

\beginequation*P(n,k) = \fracn!(n-k)!.\endequation*

Note that as soon as \(n = k\text,\) we have \(P(n,n) = \fracn!(n-n)! = n!\) (since we identified \(0!\) to be 1). This provides sense —we currently know \(n!\) offers the number of permutations of all \(n\) objects.

Example1.3.4Counting injective functions

How many functions \(f:\1,2,3\ \to \1,2,3,4,5,6,7,8\\) room injective?


Solution

Note the it doesn"t make sense to ask for the number of bijections here, together there space none (because the codomain is larger than the domain, there space no surjections). But for a duty to it is in injective, we simply can"t usage an facet of the codomain an ext than once.

We must pick an element from the codomain to be the image of 1. There room 8 choices. Climate we should pick one of the remaining 7 aspects to it is in the image of 2. Finally, one of the remaining 6 facets must it is in the picture of 3. Therefore the total number of functions is \(8\cdot 7 \cdot 6 = P(8,3)\text.\)

What this displayed in basic is that the number of injections \(f:A \to B\text,\) whereby \(\cardA = k\) and \(\cardB = n\text,\) is \(P(n,k)\text.\)


Here is another method to discover the variety of \(k\)-permutations the \(n\) elements: very first select which \(k\) aspects will be in the permutation, then count how many ways there space to arrange them. When you have selected the \(k\) objects, we recognize there room \(k!\) methods to species (permute) them. But how do you select \(k\) objects from the \(n\text?\) You have actually \(n\) objects, and you need to choose \(k\) of them. You have the right to do the in \(n \choose k\) ways. Then for each an option of those \(k\) elements, we can permute them in \(k!\) ways. Making use of the multiplicative principle, us get an additional formula because that \(P(n,k)\text:\)

\beginequation*P(n,k) = n \choose k\cdot k!.\endequation*

Now since we have actually a close up door formula for \(P(n,k)\) already, we deserve to substitute the in:

\beginequation*\fracn!(n-k)! = n \choose k \cdot k!.\endequation*

If we division both political parties by \(k!\) we gain a closeup of the door formula because that \(n \choose k\text.\)

Closed formula for \(n \choose k\)

\beginequation*n \choose k = \fracn!(n-k)!k!\endequation*

We speak \(P(n,k)\) counts permutations, and \(n \choose k\) counts combinations. The formulas because that each are an extremely similar, over there is just an extra \(k!\) in the denominator that \(n \choose k\text.\) the extra \(k!\) accounts for the reality that \(n \choose k\) does not distinguish between the different orders the the \(k\) objects can appear in. We are just selecting (or choosing) the \(k\) objects, not arranging them. Possibly “combination” is a misleading label. Us don"t mean it prefer a mix lock (where the bespeak would certainly matter). Perhaps a far better metaphor is a combination of spices — you simply need to decide which spices to combine, not the stimulate in i m sorry to integrate them.

To more illustrate the connection between combinations and also permutations, we close through an example.

Example1.3.5

You decision to have actually a dinner party. Even though girlfriend are extremely popular and have 14 different friends, you just have sufficient chairs to invite 6 the them.

How many choices do you have actually for i beg your pardon 6 friends to invite?

What if you need to decide not just which friends come invite but additionally where to seat them follow me your long table? just how many options do you have actually then?


You must simply pick 6 friends native a group of 14. This deserve to be done in \(14 \choose 6\) ways. We can discover this number either by making use of Pascal"s triangle or the close up door formula: \(\frac14!8!\cdot 6! = 3003\text.\)

Here you should count every the ways you have the right to permute 6 friends liked from a team of 14. Therefore the answer is \(P(14, 6)\text,\) which can be calculated as \(\frac14!8! = 2192190\text.\)

Notice the we deserve to think the this counting problem as a question about counting functions: how many injective functions are there from your set of 6 chairs to your set of 14 friends (the functions are injective because you can"t have a single chair go to two of your friends).

How room these numbers related? notification that \(P(14,6)\) is much larger than \(14 \choose 6\text.\) This makes sense. \(14 \choose 6\) choose 6 friends, yet \(P(14,6)\) arranges the 6 friends and picks them. In fact, we have the right to say exactly how much bigger \(P(14,6)\) is. In both counting troubles we pick 6 out of 14 friends. For the an initial one, we avoid there, in ~ 3003 ways. But for the second counting problem, every of those 3003 options of 6 friends have the right to be arranged in specifically \(6!\) ways. So now we have actually \(3003\cdot 6!\) choices and that is precisely \(2192190\text.\)

Alternatively, look in ~ the an initial problem another way. We desire to select 6 the end of 14 friends, however we execute not care around the bespeak they room selected in. To pick 6 the end of 14 friends, we might shot this:

\beginequation*14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9.\endequation*

This is a reasonable guess, since we have 14 choices for the very first guest, then 13 for the second, and also so on. But the guess is dorn (in fact, the product is specifically \(2192190 = P(14,6)\)). That distinguishes between the different orders in i m sorry we might invite the guests. To correct for this, we might divide through the variety of different kinds of the 6 guests (so that every one of these would certainly count as just one outcome). Over there are precisely \(6!\) means to arrange 6 guests, for this reason the exactly answer come the very first question is

\beginequation*\frac14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 96!.\endequation*

Note that another way to write this is

\beginequation*\frac14!8!\cdot 6!.\endequation*

which is what we had actually originally.


SubsectionExercises

¶1

A pizza parlor supplies 10 toppings.

How numerous 3-topping pizzas could they placed on their menu? Assume dual toppings are not allowed.

How many total pizzas space possible, with between zero and ten toppings (but not double toppings) allowed?

The pizza parlor will certainly list the 10 toppings in 2 equal-sized columns on their menu. How countless ways have the right to they arrange the toppings in the left column?


\(10 \choose 3 = 120\) pizzas. We must select (in no specific order) 3 the end of the 10 toppings.\(2^10 = 1024\) pizzas. To speak yes or no to each topping.\(P(10,5) = 30240\) ways. Assign every of the 5 spots in the left shaft to a distinctive pizza topping.
2

A mix lock consists of a dial through 40 numbers on it. To open the lock, you revolve the dial to the ideal until you with a first number, climate to the left until you get to 2nd number, climate to the ideal again come the 3rd number. The numbers have to be distinct. How numerous different combinations space possible?


Despite that is name, we space not searching for a mix here. The order in i beg your pardon the three numbers shows up matters. There space \(P(40,3) = 40\cdot 39 \cdot 38\) various possibilities because that the “combination”. This is suspect you cannot repeat any type of of the number (if girlfriend could, the answer would be \(40^3\)).


3

Using the digits 2 through 8, uncover the variety of different 5-digit numbers together that:

Digits deserve to be used an ext than once.

Digits cannot be repeated, yet can come in any kind of order.

Digits cannot be repeated and must be written in raising order.

Which of the above counting inquiries is a combination and which is a permutation? define why this provides sense.

4

How many triangles are there through vertices indigenous the points presented below? Note, we space not enabling degenerate triangle - ones v all 3 vertices ~ above the very same line, however we do enable non-right triangles. Describe why her answer is correct.


*

*

5 squares. You need to skip precisely one period on the top and also on the bottom to do the side lengths equal. Once you choose a dot on the top, the various other three dots are determined.

\(7 \choose 2\) rectangles. As soon as you select the two dots ~ above the top, the bottom two room determined.

This is tricky since you must worry about running out of space. One method to count: break into instances by the place of the optimal left corner. You obtain \(7 \choose 2 + (7 \choose 2-1) + (7 \choose 2 - 3) + (7 \choose 2 - 6) + (7 \choose 2 - 10) + (7 \choose 2 - 15) = 91\) parallelograms.

All that them

\(7\choose 27\choose 2 - \left< 7 \choose 2 + (7 \choose 2-1) + (7 \choose 2 - 3) + (7 \choose 2 - 6) + (7 \choose 2 - 10) + (7 \choose 2 - 15) \right>\text.\) all of them, except the parallelograms.


78

How plenty of anagrams room there of words “assesses” that start with the letter “a”?


After the first letter (a), we must rearrange the continuing to be 7 letters. There are just two letter (s and also e), for this reason this is really just a bit-string concern (think of s as 1 and also e as 0). Hence there \(7 \choose 2 = 21\) anagrams starting with “a”.


9

How countless anagrams space there that “anagram”?

10

On a business retreat, your firm of 20 businessmen and also businesswomen walk golfing.

You must divide up into foursomes (groups that 4 people): a first foursome, a second foursome, and so on. How numerous ways have the right to you execute this?

After all your difficult work, girlfriend realize the in fact, you want each foursome to include one of the five Board members. How numerous ways deserve to you perform this?


\(20 \choose 416 \choose 412 \choose 48 \choose 44 \choose 4\) ways. Pick 4 out of 20 civilization to it is in in the very first foursome, climate 4 that the staying 16 because that the second foursome, and so top top (use the multiplicative rule to combine).\(5!15 \choose 312 \choose 39 \choose 36 \choose 33 \choose 3\) ways. First determine the tee time the the 5 plank members, then choose 3 of the 15 non board members to golf v the very first board member, then 3 of the remaining 12 to golf v the second, and also so on.
11

How many different seating kinds are feasible for King Arthur and his 9 knights approximately their ring table?


\(9!\) (there room 10 people seated about the table, however it does not issue where King Arthur sits, only who sits to his left, two seats come his left, and so on).


12

Consider to adjust \(A\) and also \(B\) with \(|A| = 10\) and also \(|B| = 17\text.\)

How plenty of functions \(f: A \to B\) space there?

How many functions \(f: A \to B\) space injective?


\(17^10\) functions. There space 17 choices for the image of each facet in the domain.\(P(17, 10)\) injective functions. There are 17 options for photo of the very first element the the domain, then just 16 choices for the second, and also so on.
13

Consider attributes \(f: \1,2,3,4\ \to \1,2,3,4,5,6\\text.\)

How many functions room there total?

How many functions space injective?

How numerous of the injective features are increasing? To it is in increasing way that if \(a \lt b\) then \(f(a) \lt f(b)\text,\) or in other words, the outputs acquire larger as the inputs get larger.

14

We have seen the the formula because that \(P(n,k)\) is \(\dfracn!(n-k)!\text.\) your task below is to describe why this is the best formula.

Suppose you have actually 12 chips, each a different color. How plenty of different stacks of 5 chips can you make? explain your answer and why it is the exact same as using the formula for \(P(12,5)\text.\)

Using the script of the 12 chips again, what go \(12!\) count? What go \(7!\) count? Explain.

See more: How Much Are The Texas Rangers Worth ? Texas Rangers (Baseball)

Explain why it makes sense to division \(12!\) by \(7!\) when computer \(P(12,5)\) (in regards to the chips).

Does your explanation work for numbers other than 12 and also 5? explain the formula \(P(n,k) = \fracn!(n-k)!\) making use of the variables \(n\) and also \(k\text.\)