Front Matter

0Introduction and also Preliminaries

1Counting

2Sequences

3Symbolic Logic and Proofs

4Graph Theory

5Additional Topics

Backmatter


Authored in PreTeXt
*

Section1.3Combinations and Permutations

¶Investigate!8

You have a bunch that chips i beg your pardon come in five different colors: red, blue, green, purple and also yellow.

How numerous different two-chip stacks deserve to you make if the bottom chip have to be red or blue? describe your answer making use of both the additive and multiplicative principles.

You are watching: All possible combinations of 4 letters

How plenty of different three-chip stacks deserve to you make if the bottom chip should be red or blue and also the optimal chip must be green, purple or yellow? exactly how does this problem relate come the vault one?

How plenty of different three-chip stacks space there in i beg your pardon no shade is repeated? What about four-chip stacks?

Suppose you wanted to take it three various colored chips and put them in your pocket. How numerous different selections do friend have? What if you want four various colored chips? exactly how do these problems relate to the vault one?

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

eginequation*abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba.endequation*

We recognize that we have actually them all detailed above —there are 3 options for i beg your pardon letter we placed first, then 2 choices for which letter comes next, i m sorry leaves only 1 an option for the last letter. The multiplicative principle states we main point (3cdot 2 cdot 1 ext.)

Example1.3.1

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


Solution

We perform NOT want to shot to list every one of these out. However, if we did, us would must pick a letter to write down first. There are 6 options for that letter. Because that each selection of an initial letter, there are 5 choices for the 2nd letter (we can not repeat the first letter; we room rearranging letters and only have one the each), and also for every of those, there are 4 selections for the third, 3 choices for the fourth, 2 selections for the fifth and also finally only 1 selection for the critical letter. For this reason there room (6 cdot 5 cdot 4 cdot 3 cdot 2 cdot 1 = 720) permutations of the 6 letters.


A item of notation is valuable here: (n! ext,) review “(n) factorial”, is the product the all confident integers less than or equal to (n) (for reasons of convenience, we additionally define 0! to it is in 1). Therefore the number of permutation of 6 letters, as viewed in the previous instance is (6! = 6cdot 5 cdot 4 cdot 3 cdot 2 cdot 1 ext.) This generalizes:

Permutations the (n) elements

There are (n! = ncdot (n-1)cdot (n-2)cdot cdots cdot 2cdot 1) permutations the (n) (distinct) elements.

Example1.3.2Counting Bijective Functions

How countless functions (f:1,2,ldots,8 o 1,2,ldots, 8\) room bijective?


Solution

Remember what it means for a function to be bijective: each aspect in the codomain have to be the photo of precisely one aspect of the domain. Making use of two-line notation, we might write among these bijections as

eginequation*f = woline1 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 4endequation*

What we are really law is simply rearranging the facets of the codomain, so us are creating a permutation the 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 see the answer need to be (8! = 8 cdot 7 cdotcdotscdot 1 = 40320 ext.) You deserve to see this directly as well: for each element of the domain, we need to pick a distinct facet of the codomain to map to. There room 8 choices for whereby to send 1, then 7 choices for whereby to send 2, and so on. Us multiply making use of the multiplicative principle.


Sometimes we execute not want to permute all of the letters/numbers/elements we room given.

Example1.3.3

How countless 4 letter “words” deserve to you make from the letter a v f, v no repeated letters?


Solution

This is just like the difficulty of permuting 4 letters, only now we have much more choices because that each letter. Because that the an initial letter, there are 6 choices. Because that each the those, there space 5 selections for the second letter. Then there room 4 options for the 3rd letter, and also 3 selections for the critical letter. The total number of words is (6cdot 5cdot 4 cdot 3 = 360 ext.) This is no (6!) due to the fact that we never multiplied by 2 and also 1. We could start v (6!) and then release the 2 and 1, and also thus write (frac6!2! ext.)


In general, we have the right to ask how many permutations exist the (k) objects choosing those objects from a larger collection the (n) objects. (In the instance above, (k = 4 ext,) and (n = 6 ext.)) We create this number (P(n,k)) and also sometimes speak to it a (k)-permutation that (n) elements. Native the instance above, we see that to compute (P(n,k)) we must use the multiplicative rule to (k) numbers, beginning with (n) and also counting backwards. Because that example

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

Notice again that (P(10,4)) starts the end looking favor (10! ext,) but we protect against after 7. We can formally account for this “stopping” by dividing away the component of the factorial we carry out not want:

eginequation*P(10,4) = frac10cdot 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 no (4!) but rather ((10-4)! ext.)

(k)-permutations of (n) elements

(P(n,k)) is the number of (k)-permutations that (n) elements, the number of ways come arrange (k) objects liked from (n) distinct objects.

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

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

Example1.3.4Counting injective functions

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


Solution

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

We should pick an aspect from the codomain to it is in the picture of 1. There space 8 choices. Then we have to pick one of the continuing to be 7 aspects to it is in the picture of 2. Finally, among the remaining 6 elements must be the picture of 3. For this reason the total variety of functions is (8cdot 7 cdot 6 = P(8,3) ext.)

What this demonstrates in general is that the variety of injections (f:A o B ext,) wherein (cardA = k) and also (cardB = n ext,) is (P(n,k) ext.)


Here is another way to discover the variety of (k)-permutations the (n) elements: very first select i m sorry (k) aspects will it is in in the permutation, then counting how plenty of ways there are to arrange them. As soon as you have selected the (k) objects, we understand there space (k!) means to arrange (permute) them. But how execute you choose (k) objects indigenous the (n ext?) You have (n) objects, and also you should choose (k) that them. You can do the in (n choose k) ways. Then because that each choice of those (k) elements, we can permute them in (k!) ways. Making use of the multiplicative principle, us get one more formula for (P(n,k) ext:)

eginequation*P(n,k) = n choose kcdot k!.endequation*

Now since we have a closed formula for (P(n,k)) already, we can substitute that in:

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

If we division both political parties by (k!) we gain a close up door formula because that (n choose k ext.)

Closed formula for (n choose k)

eginequation*n choose k = fracn!(n-k)!k!endequation*

We to speak (P(n,k)) counts permutations, and also (n choose k) counts combinations. The formulas for each are very similar, over there is just an extra (k!) in the denominator that (n choose k ext.) the extra (k!) accounts because that the truth that (n choose k) does not distinguish in between the different orders the the (k) objects can appear in. We are just selecting (or choosing) the (k) objects, no arranging them. Perhaps “combination” is a misleading label. We don"t typical it choose a mix lock (where the stimulate would certainly matter). Probably a better metaphor is a mix of seasonings — you simply need to decide which spices to combine, no the bespeak in i beg your pardon to incorporate them.

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

Example1.3.5

You decision to have a dinner party. Also though you are exceptionally popular and also have 14 different friends, you only have sufficient chairs come invite 6 the them.

How many options do you have actually for which 6 friends come invite?

What if you have to decide not only which friends come invite but likewise where to seat them follow me your long table? exactly how many choices do you have then?


You should simply select 6 friends from a group of 14. This can be done in (14 choose 6) ways. Us can uncover this number one of two people by utilizing Pascal"s triangle or the closed formula: (frac14!8!cdot 6! = 3003 ext.)

Here you have to count every the methods you can permute 6 friends chosen from a group of 14. For this reason the prize is (P(14, 6) ext,) which deserve to be calculated as (frac14!8! = 2192190 ext.)

Notice the we can think that this counting trouble as a question around counting functions: how plenty of injective functions are over there from your collection of 6 chairs come your set of 14 girlfriend (the functions are injective due to the fact that you can"t have actually a single chair go to 2 of your friends).

How room these number related? an alert that (P(14,6)) is much larger than (14 choose 6 ext.) This provides sense. (14 choose 6) choose 6 friends, but (P(14,6)) arranges the 6 friends as well as picks them. In fact, we deserve to say precisely how much bigger (P(14,6)) is. In both counting problems we pick 6 the end of 14 friends. Because that the first one, we stop there, in ~ 3003 ways. But for the second counting problem, every of those 3003 options of 6 friends deserve to be arranged in precisely (6!) ways. So currently we have (3003cdot 6!) choices and that is exactly (2192190 ext.)

Alternatively, look at the an initial problem another way. We desire to pick 6 the end of 14 friends, however we do not care about the order they are selected in. To choose 6 out of 14 friends, us might shot this:

eginequation*14 cdot 13 cdot 12 cdot 11 cdot 10 cdot 9.endequation*

This is a reasonable guess, because we have actually 14 options for the an initial guest, climate 13 because that the second, and also so on. But the guess is not correct (in fact, the product is precisely (2192190 = P(14,6))). That distinguishes between the various orders in which we might invite the guests. To correct because that this, we might divide by the number of different species of the 6 guest (so that all of these would certainly count as just one outcome). There are exactly (6!) ways to kinds 6 guests, for this reason the correct answer to the an initial question is

eginequation*frac14 cdot 13 cdot 12 cdot 11cdot 10 cdot 96!.endequation*

Note that another means to compose this is

eginequation*frac14!8!cdot 6!.endequation*

which is what we had originally.


SubsectionExercises

¶1

A pizza parlor provides 10 toppings.

How countless 3-topping pizzas could they placed on your menu? Assume dual toppings room not allowed.

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

The pizza parlor will list the 10 toppings in 2 equal-sized columns on your menu. How countless ways deserve to they kinds the toppings in the left column?


(10 choose 3 = 120) pizzas. Us must select (in no certain order) 3 out of the 10 toppings.(2^10 = 1024) pizzas. Speak yes or no to every topping.(P(10,5) = 30240) ways. Assign each of the 5 point out in the left tower to a unique pizza topping.
2

A combination lock consists of a dial through 40 numbers on it. To open up the lock, you turn the dial come the appropriate until you reach a an initial number, then to the left till you obtain to 2nd number, climate to the best again come the third number. The numbers have to be distinct. How many different combinations space possible?


Despite its name, we room not looking for a mix here. The stimulate in i beg your pardon the 3 numbers appears matters. There space (P(40,3) = 40cdot 39 cdot 38) various possibilities for the “combination”. This is suspect you cannot repeat any kind of of the number (if friend could, the answer would certainly be (40^3)).


3

Using the digits 2 with 8, discover the variety of different 5-digit numbers such that:

Digits can be used much more than once.

Digits can not be repeated, however can come in any order.

Digits cannot be repeated and also must be created in enhancing order.

Which the the above counting inquiries is a mix and which is a permutation? describe why this renders sense.

4

How numerous triangles are there through vertices from the points presented below? Note, we are not enabling degenerate triangle - ones v all three vertices top top the exact same line, however we do enable non-right triangles. Define why your answer is correct.


*

*

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

(7 choose 2) rectangles. Once you choose the 2 dots top top the top, the bottom two space determined.

This is tricky due to the fact that you have to worry around running the end of space. One means to count: rest into situations by the ar of the top left corner. You acquire (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

(7choose 27choose 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) ight> ext.) all of them, except the parallelograms.


78

How numerous anagrams are there of the word “assesses” that start with the letter “a”?


After the an initial letter (a), we should rearrange the staying 7 letters. There are just two letters (s and also e), for this reason this is really simply a bit-string inquiry (think that s together 1 and also e as 0). Therefore there (7 choose 2 = 21) anagrams beginning with “a”.


9

How many anagrams space there the “anagram”?

10

On a business retreat, your agency of 20 businessmen and businesswomen go golfing.

You should divide up right into foursomes (groups the 4 people): a an initial foursome, a 2nd foursome, and also so on. How countless ways have the right to you execute this?

After all your tough work, you realize that in fact, you desire each foursome to include one that the 5 Board members. How many ways can you execute this?


(20 choose 416 choose 412 choose 48 choose 44 choose 4) ways. Choose 4 the end of 20 civilization to it is in in the an initial foursome, then 4 that the staying 16 because that the second foursome, and so ~ above (use the multiplicative rule to combine).(5!15 choose 312 choose 39 choose 36 choose 33 choose 3) ways. Very first determine the tee time of the 5 board members, then choose 3 of the 15 non plank members to golf v the very first board member, then 3 of the staying 12 come golf through the second, and also so on.
11

How many different seating species are possible for King Arthur and his 9 knights around their round table?


(9!) (there space 10 human being seated about the table, but it go not matter where King Arthur sits, only who sits to his left, two seats come his left, and also so on).


12

Consider sets (A) and (B) with (|A| = 10) and (|B| = 17 ext.)

How numerous functions (f: A o B) are there?

How plenty of functions (f: A o B) room injective?


(17^10) functions. There are 17 choices for the image of each facet in the domain.(P(17, 10)) injective functions. There are 17 selections for picture of the an initial element of the domain, then only 16 options for the second, and also so on.
13

Consider features (f: 1,2,3,4 o 1,2,3,4,5,6\text.)

How plenty of functions space there total?

How many functions space injective?

How plenty of of the injective attributes are increasing? To be increasing means that if (a lt b) climate (f(a) lt f(b) ext,) or in various other words, the outputs gain larger together the inputs gain larger.

14

We have seen the the formula because that (P(n,k)) is (dfracn!(n-k)! ext.) her task here is to define why this is the appropriate formula.

Suppose you have 12 chips, each a different color. How numerous different stacks of 5 chips deserve to you make? describe your answer and why the is the same as using the formula because that (P(12,5) ext.)

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

See more: 1/4 C Fresh Parsley To Dried Recipes, Familytime'S Conversion Charts

Explain why it makes sense to divide (12!) through (7!) when computing (P(12,5)) (in regards to the chips).

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