Why Are There So Many Arangements of Here I Go Again

\(\def\d{\displaystyle} \def\class{Math 228} \newcommand{\f}[1]{\mathfrak #ane} \newcommand{\southward}[1]{\mathscr #i} \def\N{\mathbb Northward} \def\B{\mathbf{B}} \def\circleA{(-.5,0) circle (i)} \def\Z{\mathbb Z} \def\circleAlabel{(-1.5,.six) node[to a higher place]{$A$}} \def\Q{\mathbb Q} \def\circleB{(.5,0) circle (i)} \def\R{\mathbb R} \def\circleBlabel{(1.5,.6) node[in a higher place]{$B$}} \def\C{\mathbb C} \def\circleC{(0,-one) circle (1)} \def\F{\mathbb F} \def\circleClabel{(.5,-2) node[right]{$C$}} \def\A{\mathbb A} \def\twosetbox{(-two,-1.5) rectangle (ii,1.v)} \def\X{\mathbb Ten} \def\threesetbox{(-2,-2.five) rectangle (two,1.five)} \def\E{\mathbb Due east} \def\O{\mathbb O} \def\U{\mathcal U} \def\pow{\mathcal P} \def\inv{^{-1}} \def\nrml{\triangleleft} \def\st{:} \def\~{\widetilde} \def\rem{\mathcal R} \def\sigalg{$\sigma$-algebra } \def\Gal{\mbox{Gal}} \def\iff{\leftrightarrow} \def\Iff{\Leftrightarrow} \def\land{\wedge} \def\And{\bigwedge} \def\entry{\entry} \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge} \def\Vee{\bigvee} \def\VVee{\d\Vee\mkern-18mu\Vee} \def\imp{\rightarrow} \def\Imp{\Rightarrow} \def\Fi{\Leftarrow} \def\var{\mbox{var}} \def\Th{\mbox{Thursday}} \def\entry{\entry} \def\sat{\mbox{Sat}} \def\con{\mbox{Con}} \def\iffmodels{\bmodels\models} \def\dbland{\bigwedge \!\!\bigwedge} \def\dom{\mbox{dom}} \def\rng{\mbox{range}} \def\isom{\cong} \DeclareMathOperator{\wgt}{wgt} \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#i:#ii]{}} \newcommand{\va}[1]{\vtx{in a higher place}{#1}} \newcommand{\vb}[1]{\vtx{below}{#1}} \newcommand{\vr}[1]{\vtx{right}{#1}} \newcommand{\vl}[1]{\vtx{left}{#ane}} \renewcommand{\v}{\vtx{above}{}} \def\circleA{(-.5,0) circumvolve (1)} \def\circleAlabel{(-one.5,.6) node[above]{$A$}} \def\circleB{(.5,0) circle (1)} \def\circleBlabel{(1.5,.6) node[above]{$B$}} \def\circleC{(0,-i) circle (1)} \def\circleClabel{(.five,-2) node[right]{$C$}} \def\twosetbox{(-2,-one.4) rectangle (two,1.four)} \def\threesetbox{(-2.5,-two.4) rectangle (2.5,1.4)} \def\ansfilename{practice-answers} \def\shadowprops{{fill up=blackness!l,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge ten percent}}} \newcommand{\hexbox}[3]{ \def\x{-cos{thirty}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#one-sin{30}*\r*#one} \draw (\10,\y) +(ninety:\r) -- +(xxx:\r) -- +(-xxx:\r) -- +(-ninety:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \describe (\x,\y) node{#3}; } \renewcommand{\bar}{\overline} \newcommand{\card}[ane]{\left| #one \correct|} \newcommand{\twoline}[2]{\brainstorm{pmatrix}#1 \\ #two \end{pmatrix}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

¶

Investigate! 8

Y'all have a bunch of chips which come in v different colors: cerise, bluish, green, purple and xanthous.

1. How many different two-chip stacks can you brand if the bottom chip must be cherry-red or blue? Explicate your reply using both the condiment and multiplicative principles.

2. How many dissimilar three-fleck stacks can you brand if the lesser chip must exist ruby or blue and the acme chip must exist green, royal or yellow? How does this problem relate to the previous 1?

3. How many unlike iii-chip stacks are there in which no color is repeated? What almost iv-bit stacks?

4. Suppose you wanted to take three different colored fries and put them in your pocket. How many different choices do you have? What if yous wanted 4 different colored chips? How do these bug relate to the previous one?

A permutation is a (possible) rearrangement of objects. For instance, there are 6 permutations of the letters a, b, c:

\begin{equation*} abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba. \stop{equation*}

Nosotros know that we have them all listed to a higher place —there are 3 choices for which alphabetic character we put first, and so 2 choices for which letter of the alphabet comes next, which leaves only 1 choice for the final letter. The multiplicative principle says nosotros multiply \(3\cdot 2 \cdot 1\text{.}\)

Example 1.3.one

How many permutations are there of the letters a, b, c, d, e, f?

Solution

Nosotros do NOT want to effort to list all of these out. However, if we did, we would need to pick a alphabetic character to write down beginning. There are half-dozen choices for that letter. For each choice of first letter, at that place are 5 choices for the second letter (we cannot echo the outset letter of the alphabet; we are rearranging messages and merely have one of each), and for each of those, in that location are four choices for the third, 3 choices for the quaternary, ii choices for the fifth and finally just 1 choice for the last letter of the alphabet. And so there are \(half dozen \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\) permutations of the vi letters.

A piece of annotation is helpful here: \(n!\text{,}\) read "\(north\) factorial", is the product of all positive integers less than or equal to \(n\) (for reasons of convenience, nosotros also define 0! to exist one). So the number of permutation of half dozen letters, as seen in the previous example is \(6! = half dozen\cdot 5 \cdot 4 \cdot 3 \cdot two \cdot one\text{.}\) This generalizes:

Permutations of \(n\) elements

In that location are \(n! = n\cdot (n-1)\cdot (n-ii)\cdot \cdots \cdot two\cdot 1\) permutations of \(n\) (distinct) elements.

Example 1.3.2 Counting Bijective Functions

How many functions \(f:\{one,2,\ldots,8\} \to \{1,two,\ldots, 8\}\) are bijective?

Solution

Call back what it means for a function to be bijective: each element in the codomain must be the image of exactly one element of the domain. Using two-line note, we could write ane of these bijections equally

\begin{equation*} f = \twoline{one \amp 2 \amp iii \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp vii \amp 6 \amp 2 \amp 4} \end{equation*}

What we are really doing is only rearranging the elements of the codomain, so nosotros are creating a permutation of 8 elements. In fact, "permutation" is another term used to describe bijective functions from a finite set to itself.

If you believe this, and then you lot see the reply must exist \(eight! = 8 \cdot seven \cdot\cdots\cdot i = 40320\text{.}\) You tin see this directly as well: for each element of the domain, we must pick a distinct element of the codomain to map to. In that location are viii choices for where to ship 1, then 7 choices for where to send ii, and so on. We multiply using the multiplicative principle.

Sometimes we do non want to permute all of the letters/numbers/elements nosotros are given.

Example 1.iii.3

How many iv letter "words" tin can you make from the letters a through f, with no repeated letters?

Solution

This is just similar the problem of permuting iv messages, only now nosotros accept more than choices for each letter. For the starting time letter, there are 6 choices. For each of those, there are 5 choices for the 2nd letter. So there are 4 choices for the third letter of the alphabet, and three choices for the last letter. The total number of words is \(vi\cdot five\cdot 4 \cdot 3 = 360\text{.}\) This is not \(6!\) because we never multiplied past 2 and ane. We could starting time with \(6!\) and then cancel the 2 and 1, and thus write \(\frac{6!}{2!}\text{.}\)

In general, nosotros can ask how many permutations be of \(thousand\) objects choosing those objects from a larger collection of \(n\) objects. (In the instance above, \(k = 4\text{,}\) and \(n = 6\text{.}\)) We write this number \(P(due north,k)\) and sometimes call it a \(thousand\)-permutation of \(northward\) elements. From the example above, nosotros see that to compute \(P(due north,thou)\) we must utilize the multiplicative principle to \(k\) numbers, starting with \(n\) and counting backwards. For example

\brainstorm{equation*} P(10, 4) = x\cdot 9 \cdot 8 \cdot 7. \end{equation*}

Detect again that \(P(10,4)\) starts out looking like \(x!\text{,}\) but we stop afterwards seven. We can formally account for this "stopping" past dividing away the function of the factorial we do not desire:

\begin{equation*} P(10,four) = \frac{ten\cdot 9 \cdot viii \cdot 7 \cdot half-dozen \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{half-dozen \cdot 5 \cdot iv \cdot 3 \cdot 2 \cdot 1} = \frac{10!}{6!}. \end{equation*}

Conscientious: The factorial in the denominator is not \(four!\) but rather \((10-four)!\text{.}\)

\(yard\)-permutations of \(north\) elements

\(P(due north,k)\) is the number of \(k\)-permutations of \(n\) elements, the number of ways to arrange \(grand\) objects chosen from \(n\) distinct objects.

\begin{equation*} P(northward,yard) = \frac{n!}{(due north-thou)!}. \end{equation*}

Notation that when \(n = k\text{,}\) nosotros have \(P(n,northward) = \frac{n!}{(n-due north)!} = n!\) (since we divers \(0!\) to be 1). This makes sense —we already know \(northward!\) gives the number of permutations of all \(due north\) objects.

Example 1.iii.iv Counting injective functions

How many functions \(f:\{1,2,3\} \to \{1,ii,iii,4,5,6,vii,eight\}\) are injective?

Solution

Notation that it doesn't make sense to ask for the number of bijections hither, equally there are none (because the codomain is larger than the domain, in that location are no surjections). Just for a function to exist injective, nosotros simply can't use an element of the codomain more than in one case.

We need to choice an element from the codomain to be the epitome of 1. There are 8 choices. Then we demand to pick one of the remaining 7 elements to be the image of 2. Finally, i of the remaining 6 elements must exist the paradigm of iii. And then the full number of functions is \(8\cdot 7 \cdot vi = P(8,3)\text{.}\)

What this demonstrates in full general is that the number of injections \(f:A \to B\text{,}\) where \(\card{A} = 1000\) and \(\carte{B} = n\text{,}\) is \(P(n,k)\text{.}\)

Here is another style to discover the number of \(g\)-permutations of \(n\) elements: outset select which \(k\) elements will be in the permutation, and so count how many means there are to adjust them. Once you lot accept selected the \(k\) objects, we know there are \(k!\) ways to conform (permute) them. But how do you select \(k\) objects from the \(n\text{?}\) You lot have \(n\) objects, and you need to choose \(one thousand\) of them. Yous tin do that in \({due north \choose 1000}\) means. Then for each pick of those \(g\) elements, we tin permute them in \(yard!\) ways. Using the multiplicative principle, nosotros go another formula for \(P(n,grand)\text{:}\)

\brainstorm{equation*} P(n,k) = {north \choose k}\cdot thou!. \end{equation*}

Now since nosotros have a airtight formula for \(P(north,k)\) already, we tin can substitute that in:

\brainstorm{equation*} \frac{north!}{(north-g)!} = {n \choose g} \cdot k!. \finish{equation*}

If we divide both sides by \(m!\) we get a closed formula for \({n \choose k}\text{.}\)

Closed formula for \({n \cull k}\)

\begin{equation*} {northward \cull yard} = \frac{n!}{(n-k)!k!} \cease{equation*}

We say \(P(northward,m)\) counts permutations, and \({northward \choose g}\) counts combinations. The formulas for each are very similar, there is only an extra \(k!\) in the denominator of \({n \choose thou}\text{.}\) That actress \(k!\) accounts for the fact that \({northward \choose k}\) does not distinguish between the different orders that the \(k\) objects can announced in. We are only selecting (or choosing) the \(k\) objects, not arranging them. Mayhap "combination" is a misleading characterization. We don't mean it like a combination lock (where the club would definitely matter). Peradventure a meliorate metaphor is a combination of flavors — you just need to determine which flavors to combine, non the lodge in which to combine them.

To further illustrate the connection between combinations and permutations, nosotros close with an instance.

Example 1.3.five

You decide to have a dinner political party. Even though you lot are incredibly popular and have 14 different friends, you simply take plenty chairs to invite vi of them.

1. How many choices do y'all take for which 6 friends to invite?

2. What if you demand to decide not only which friends to invite but also where to seat them forth your long table? How many choices exercise you have and then?

Solution

1. You must simply choose vi friends from a group of 14. This can exist washed in \({14 \choose 6}\) means. We can notice this number either past using Pascal'southward triangle or the airtight formula: \(\frac{fourteen!}{8!\cdot 6!} = 3003\text{.}\)

2. Here you lot must count all the means you can permute half-dozen friends chosen from a group of fourteen. Then the answer is \(P(fourteen, 6)\text{,}\) which tin exist calculated every bit \(\frac{14!}{eight!} = 2192190\text{.}\)

   Notice that we tin can think of this counting problem as a question about counting functions: how many injective functions are there from your set of half-dozen chairs to your set of 14 friends (the functions are injective because you tin't accept a single chair get to two of your friends).

How are these numbers related? Notice that \(P(fourteen,6)\) is much larger than \({14 \choose 6}\text{.}\) This makes sense. \({14 \cull 6}\) picks 6 friends, but \(P(14,6)\) arranges the half-dozen friends also equally picks them. In fact, we tin can say exactly how much larger \(P(14,6)\) is. In both counting issues we cull 6 out of 14 friends. For the outset 1, we finish in that location, at 3003 means. Simply for the 2nd counting problem, each of those 3003 choices of 6 friends can exist arranged in exactly \(6!\) means. And then now nosotros have \(3003\cdot six!\) choices and that is exactly \(2192190\text{.}\)

Alternatively, expect at the get-go problem another way. We desire to select half dozen out of 14 friends, but nosotros do not care about the order they are selected in. To select 6 out of 14 friends, nosotros might try this:

\begin{equation*} fourteen \cdot xiii \cdot 12 \cdot 11 \cdot x \cdot 9. \cease{equation*}

This is a reasonable guess, since we have 14 choices for the first invitee, then xiii for the second, and then on. Merely the guess is wrong (in fact, that product is exactly \(2192190 = P(14,half dozen)\)). Information technology distinguishes between the different orders in which we could invite the guests. To right for this, nosotros could carve up by the number of dissimilar arrangements of the 6 guests (and so that all of these would count equally just 1 effect). There are precisely \(vi!\) ways to arrange six guests, and so the right answer to the beginning question is

\begin{equation*} \frac{xiv \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!}. \finish{equation*}

Annotation that another way to write this is

\begin{equation*} \frac{fourteen!}{8!\cdot 6!}. \end{equation*}

which is what we had originally.

Subsection Exercises

¶

i

A pizza parlor offers 10 toppings.

1. How many three-topping pizzas could they put on their menu? Assume double toppings are not allowed.

2. How many total pizzas are possible, with betwixt null and ten toppings (merely not double toppings) allowed?

3. The pizza parlor will list the 10 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?

Solution

1. \({10 \choose 3} = 120\) pizzas. We must choose (in no detail order) iii out of the x toppings.
2. \(two^{10} = 1024\) pizzas. Say aye or no to each topping.
3. \(P(10,5) = 30240\) ways. Assign each of the 5 spots in the left cavalcade to a unique pizza topping.

two

A combination lock consists of a dial with 40 numbers on information technology. To open the lock, you turn the dial to the right until yous reach a first number, then to the left until you become to second number, then to the correct once more to the third number. The numbers must be distinct. How many dissimilar combinations are possible?

Solution

Despite its name, nosotros are non looking for a combination here. The lodge in which the three numbers appears matters. There are \(P(xl,3) = xl\cdot 39 \cdot 38\) different possibilities for the "combination". This is assuming you cannot echo whatsoever of the numbers (if you could, the reply would be \(40^iii\)).

3

Using the digits two through 8, find the number of unlike 5-digit numbers such that:

1. Digits can be used more than than once.

2. Digits cannot be repeated, only tin can come up in whatsoever order.

3. Digits cannot be repeated and must be written in increasing order.

4. Which of the to a higher place counting questions is a combination and which is a permutation? Explain why this makes sense.

four

How many triangles are in that location with vertices from the points shown below? Notation, we are not allowing degenerate triangles - ones with all three vertices on the same line, but we do allow non-right triangles. Explain why your answer is right.

Hint

You demand exactly ii points on either the \(x\)- or \(y\)-axis, but don't over-count the correct triangles.

v

How many quadrilaterals can you draw using the dots below as vertices (corners)?

Solution

\({7\cull 2}{7\choose two} = 441\) quadrilaterals. We must pick two of the vii dots from the summit row and two of the seven dots on the lesser row. However, it does not brand a difference which of the two (on each row) nosotros selection starting time considering once these 4 dots are selected, there is exactly one quadrilateral that they decide.

vi

How many of the quadrilaterals possible in the previous problem are:

1. Squares?

2. Rectangles?

3. Parallelograms?

4. Trapezoids? ² Here, as in calculus, a trapezoid is defined as a quadrilateral with at least one pair of parallel sides. In particular, parallelograms are trapezoids.

5. Trapezoids that are not parallelograms?

Solution

1. 5 squares. You demand to skip exactly one dot on the summit and on the bottom to make the side lengths equal. One time you pick a dot on the top, the other 3 dots are determined.

2. \({seven \choose two}\) rectangles. Once yous select the two dots on the top, the lesser two are determined.

3. This is catchy since you need to worry about running out of infinite. One way to count: break into cases past the location of the top left corner. You get \({7 \choose 2} + ({vii \choose two}-1) + ({7 \cull 2} - iii) + ({7 \choose 2} - 6) + ({vii \choose two} - 10) + ({7 \choose 2} - 15) = 91\) parallelograms.

4. All of them

5. \({7\choose 2}{7\choose 2} - \left[ {vii \cull 2} + ({7 \cull two}-i) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({vii \choose ii} - ten) + ({7 \choose 2} - xv) \correct]\text{.}\) All of them, except the parallelograms.

vii

An anagram of a word is only a rearrangement of its letters. How many different anagrams of "uncopyrightable" are there? (This happens to be the longest common English word without any repeated letters.)

8

How many anagrams are in that location of the word "assesses" that start with the letter of the alphabet "a"?

Solution

Afterwards the first letter (a), nosotros must rearrange the remaining seven letters. There are only 2 letters (s and e), so this is really just a scrap-cord question (think of s as i and east as 0). Thus there \({7 \cull two} = 21\) anagrams starting with "a".

9

How many anagrams are there of "anagram"?

x

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

1. You need to split up up into foursomes (groups of 4 people): a first foursome, a 2nd foursome, and so on. How many ways can you practise this?

2. Later on all your hard work, you realize that in fact, y'all want each foursome to include ane of the 5 Board members. How many ways can y'all do this?

Solution

1. \({20 \choose iv}{sixteen \choose four}{12 \choose four}{eight \cull iv}{four \choose 4}\) ways. Selection 4 out of twenty people to be in the get-go foursome, so four of the remaining 16 for the second foursome, and so on (utilise the multiplicative principle to combine).
2. \(5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\) ways. Starting time determine the tee fourth dimension of the 5 board members, then select three of the 15 non lath members to golf with the commencement board member, then three of the remaining 12 to golf with the second, and so on.

11

How many different seating arrangements are possible for Male monarch Arthur and his ix knights around their round table?

Solution

\(9!\) (at that place are 10 people seated around the table, but it does not matter where Rex Arthur sits, only who sits to his left, two seats to his left, and and then on).

12

Consider sets \(A\) and \(B\) with \(|A| = x\) and \(|B| = 17\text{.}\)

1. How many functions \(f: A \to B\) are there?

2. How many functions \(f: A \to B\) are injective?

Solution

1. \(17^{x}\) functions. There are 17 choices for the prototype of each chemical element in the domain.
2. \(P(17, 10)\) injective functions. There are 17 choices for image of the first element of the domain, and then but 16 choices for the 2d, and so on.

13

Consider functions \(f: \{1,2,iii,4\} \to \{1,2,three,4,5,6\}\text{.}\)

1. How many functions are there total?

2. How many functions are injective?

3. How many of the injective functions are increasing? To be increasing ways that if \(a \lt b\) then \(f(a) \lt f(b)\text{,}\) or in other words, the outputs get larger equally the inputs get larger.

14

We have seen that the formula for \(P(n,k)\) is \(\dfrac{north!}{(northward-k)!}\text{.}\) Your task here is to explain why this is the right formula.

1. Suppose you have 12 chips, each a unlike color. How many different stacks of 5 chips can you lot make? Explain your answer and why information technology is the aforementioned as using the formula for \(P(12,5)\text{.}\)

2. Using the scenario of the 12 chips again, what does \(12!\) count? What does \(7!\) count? Explain.

3. Explain why it makes sense to divide \(12!\) by \(7!\) when computing \(P(12,5)\) (in terms of the fries).

4. Does your explanation work for numbers other than 12 and five? Explicate the formula \(P(north,yard) = \frac{due north!}{(n-one thousand)!}\) using the variables \(n\) and \(k\text{.}\)

pitmanallecomead.blogspot.com

Source: http://discrete.openmathbooks.org/dmoi2/sec_counting-combperm.html

Share this post