forked from abhusnurmath/592Notes
-
Notifications
You must be signed in to change notification settings - Fork 2
/
05_Permutations.tex
190 lines (117 loc) · 8.33 KB
/
05_Permutations.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
\documentclass[12pt]{article}
\usepackage{amsfonts,amssymb}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{listings}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}
\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%
%\input ../adgeomcs/lamacb.tex
%\input ../mac.tex
%\input ../mathmac.tex
%
\input xy
\xyoption{all}
\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
%cis51109hw1
%
\begin{document}
\begin{center}
\fbox{{\Large\bf Permutations and Combinations}}\\
\vspace{1cm}
\end{center}
\medskip\noindent
{\bf Notes.}
Main concepts
\begin{itemize}
\item Order matters - permutation
\item Choosing - combinations
\item More applications
\end{itemize}
\vspace{0.5cm}\noindent
\section*{Permutations}
Permutations occur when counting sequences without repetitions.
If Ash, Bo, and Carmen have to be lined up in a straight line the number of ways in which this can be done can be calculated using the product rule.
The first position can be filled any of the 3. The second position can be filled by any of the remaining 2. Finally there is only choice for the final position. Therefore this can be done in $3 \cdot 2 \cdot 1 = 6$
In general, $n$ items can be arranged in an $n$ sequence in $n! = n \times (n-1) \times (n-2) \times 1$ ways.
That $n$ with an exclamation point is the notation for what is called n factorial.
What if instead of using all the elements in a set, we just want to pick $r$ of them and arrange them in a straight line?
The product principle can still be applied
\begin{itemize}
\item pick the first - $n$ choices
\item pick the second - $n-1$ choices
\item pick the third - $n-2$ choices
\item pick the $r^{th}$ - $n-r+1$ choices
\end{itemize}
Putting that all together you get what is called the number of r-permutations over a set with n elements which is often denoted as $P(n,r)$. An r-permutation is a sequence of r items with no repetitions, all taken from the same set.
$P(n,r) = n \cdot (n-1) \cdots (n-r+1) = \frac{n!}{(n-r)!}$
\section*{Examples - Permutations}
How many functions are there from $\{1,2,3\}$ to $\{a,b\}$?
The key here is recognizing that each function can be identified as an ordered sequence of 3 with each place being occupied by an $a$ or a $b$. Why? Something (a,a,b) would just mean that $1$ is being mapped to $a$, $2$ is being mapped to $a$ and so on.
So the total is $2 \times 2 \times 2 = 8$.
It is important to observe that in this case, since repetition is allowed in the sequence, you actually do not use the r-permutation formula.
\medskip
\textbf{Example} There are 8 people who make it to the 100 m final at the Olympics. In how many ways can the gold, silver and bronze be handed out?
This is the same as the number of 3-permutations in a set of 8 since we have to assume that any of the 8 people can win a medal. Also, the obvious constraint here is that a person who manages to win the gold medal cannot also at the same time manage to win silver or bronze.
So $8 \cdot 7 \cdot 6$ ways.
\medskip
\textbf{Example} A wedding party consists of 3 groomsmen, 3 bridesmaids and of course the bride and groom. The photographer wants to take pictures by arranging people on a bench. The bridesmaids have to be together, the groomsmen have to be together and the newly married couple would be together as well. How many different photographs are possible.
There are basically 3 distinct groups here. Consider the groomsmen as one unit (tie them up!), bridesmaids as one unit and the couple as one unit. These 3 units can be arranged in 3! ways. Now within the groups, you can arrange the bridesmaids in 3! ways. The groomsmen in 3! ways and finally the couple can be arranged in 2 ways.
Therefore, $3!3!3!2! = 432$ pictures.
\medskip
\textbf{Example}
In how many ways can the letters of the word `LEADING' be arranged so that the vowels are always together.
In a manner similar to the example above, we tie the vowels together. That means we have the characters L, D, N, G and then the block of A,E,I. So 5 different things to be arranged first.
That can be done in 5! ways.
But that is not all. We can `zoom' in to the block of vowels and then rearrange those. 3 of those. They can be arranged in 3! ways.
So overall, you have 5!3! ways or arranging these letters as per the constraints.
\section*{Combinations - Choice without order mattering}
Assume someone tells you that Christopher Nolan is a great director. You want to watch some of his movies but you really do not have the time to watch them all. You just want to watch 3 of them before you make your decision whether he is good or not. The question is in how many ways can you make your choice.
Here are his movies - {Following, Memento, Insomnia, Batman Begins, The Prestige, The Dark Knight, Inception, The Dark Knight Rises, Interstellar}. 9 movies in total.
Now let's first look at this as a sequencing/permutation question and say we have 3 blanks to fill
\underline{{\hspace{2cm}}} \hspace{0.5cm } \underline{{\hspace{2cm}}} \hspace{0.5cm} \underline{{\hspace{2cm}}}
\vspace{1cm}
The first blank can be filled in 9 ways, the second in 8 ways, the third in 7 ways (you're not going to repeat a movie). So your initial idea might be to say $9 \cdot 8 \cdot 7$.
But the order does not matter! You are just making a choice of 3 movies to watch. It does not matter if you watch Memento, Insomnia, Dark Knight in that order or Insomnia, Dark Knight, Memento in that order. If someone was to ask you which 3 movies you watched, in both cases, you would just say `I watched Insomnia, Memento and Dark Knight'.
So this means we are over counting in our above answer. How much are we over counting by??
For each choice of 3 movies, there are 3! ways in which you can order them.
For the choice mentioned above for instance, you could arrange them as
(Memento, Insomnia, Dark Knight) or (Memento, Dark Knight, Insomnia) or (Dark Knight, Insomnia, Memento) or (Dark Knight, Memento, Insomnia) or (Insomia, Dark Knight, Memento) or
(Insomnia, Memento, Dark Knight).
That is 6 ways.
So for each choice, we have 6 ways to do the arrangements. That means that
\begin{align*}
\text{Number of choices} \times 6 &= 9 \cdot 8 \cdot 7 \\
\text{Number of choices} &= \frac{9 \cdot 8 \cdot 7 }{6}
\end{align*}
This is basically what is called a combination problem or a problem that involves counting the number of choices.
There is a formula and terminology associated with this. We write ${n \choose r}$ and say `n choose r' and this denotes the number of ways in which you can choose a set of r items from a set of n items.
\begin{align*}
{n \choose r} = \frac{n!}{r!(n-r)!}
\end{align*}
Now that you have seen this notation and formula, you can answer the previous question even more directly by saying
The number of choices is the same as picking a set of 3 from a set of 9. That is $\binom{9}{3}$.
\section*{The k to 1 rule}
Let $f: X \rightarrow Y$ be a function with the property that for every $y \in Y$, there are exactly $k$ different $x \in X$ such that $f(x) = y$
Then to count the number of elements in $X$, you can simply say $|Y| = \frac{|X|}{k}$.
\medskip
\textbf{Example} - How many binary strings of length 16 have exactly 4 1s.
Think of this question in the following manner. Once you know which of the 16 spots contain the 1s, you are done!
In how many ways can 4 spots be picked for the 1s. Out of the 16 possible spots, you have to pick 4.
That is $\binom{16}{4}$.
Here is another way of looking at it. Let us define a mapping from the set of 16 bit strings to a subset of the set $\{1,2,\ldots 16\}$ of size 4 in the following manner. Map the string to the locations where a 1 can be found.
$0110100010000000$ gets mapped to $\{2,3,5,9\}$.
$0000 0110 0101 0000$ gets mapped $\{6,7,9,11\}$.
It is clear that given a string you can uniquely map it to a 4 element set.
It is also clear that given a 4 element subset, you can form a 16 bit string. Just put the 1s in the locations provided by the 4 element subset.
So this is a bijection between 16 bit strings and 4 element subsets. Therefore the number of 16 bit strings with 4 1s is the same as the number of 4 element subsets of the set $\{1,2,\ldots 16\}$.
How many 4 element subsets are there? Again, that is $\binom{16}{4}$.
\end{document}