Tweet
Login
Mathematics Crystal
You may switch between
tex
and
pdf
by changing the end of the URL.
Home
About Us
Materials
Site Map
Questions and Answers
Skills
Topic Notes
HSC
Integration
Others
Tangent
UBC
UNSW
Calculus Advanced
Challenges
Complex Numbers
Conics
Differentiation
Integration
Linear Algebra
Mathematical Induction
Motion
Others
Polynomial Functions
Probability
Sequences and Series
Trigonometry
/
Topics /
Probability /
Counting.tex
--Quick Links--
The Number Empire
Wolfram Mathematica online integrator
FooPlot
Calc Matthen
Walter Zorn
Quick Math
Lists of integrals
List of integrals of trigonometric functions
PDF
\documentclass[10pt]{article} \usepackage{amssymb,amsmath} \usepackage[hmargin=1cm,vmargin=1cm]{geometry} \begin{document} {\large Counting} % % Permutations % \begin{align*} \text{Ordered }&\text{Selections \it with \rm Repetition:}\quad \text{If $n$ distinct elements are to be arranged in order and repetition is allowed, there}\\ &\text{are $n$ possibilities to select an element for the first position, and also $n$ possibilities to select for the second}\\ &\text{position, and so on. Therefore, there are $n^n$ possible arrangements.}\\ &\therefore\quad\boxed{n^n=\text{Number of ordered arrangements of $n$ elements \it with \rm repetition.}}\\ \\ &\text{If $r$ elements are to be arranged in order out of $n$ elements repetition allowed, there are $r$ positions to fill.}\\ &\text{Therefore, there are $n^r$ possible arrangements. (Note: $r\geq 0$ ; \: $r$ can be larger than $n$ .)}\\ &\therefore\quad\boxed{n^r=\text{Number of ordered arrangements of $r$ elements from a set of $n$ \it with \rm repetition.}}\\ \\ \text{\bf Permutations:}\quad &\text{A \it permutation \rm is an ordered arrangement of elements selected from a certain set \it without \rm repetition.}\\ \\ &\text{If there are $n$ distinct elements in the set, there are $n$ possibilities to select an element for the first position.}\\ &\text{After that, as repetition is not allowed, there are only $n-1$ remaining elements to be selected for the}\\ &\text{second position. Likewise, there are $n-2$ elements for the third position, and so on. Therefore, there are}\\ &\text{$n(n-1)(n-2)\ldots 3\cdot 2\cdot 1$ possible permutations in total. This number is called ``$n$ factorial'' --- $n!$ .}\\ \\ \text{Definition:}\quad&\boxed{n!=n(n-1)(n-2)\ldots 3\cdot 2\cdot 1=\text{Number of permutations selected from a set of $n$ elements.}}\\ &\text{e.g. There are $5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$ permutations for 5 distinct elements.}\\ \\ &\text{If $r$ elements are selected out of a set of $n$ $(r\leq n)$, there are only $r$ positions to fill. Therefore, there are}\\ &\text{$n(n-1)\ldots(n-r+1)$ permutations, which equals to\quad$n(n-1)\ldots(n-r+1)\cdot\tfrac{(n-r)(n-r-1)\ldots 2\cdot 1}{(n-r)(n-r-1)\ldots 2\cdot 1}=\tfrac{n!}{(n-r)!}$.}\\ \\ &\text{Alternatively, if we line up all $n$ elements, we can put the first $r$ elements in one group and the last $n-r$}\\ &\text{elements in another. There are still $n!$ permutations in total, but for each of the permutation of the first}\\ &\text{group or $r$, there are $(n-r)!$ permutations for the second group. These $(n-r)!$ permutations are in fact}\\ &\text{counted as one if only the first $r$ elements is of interest. That means the ``total number of permutations'' ($n!$)}\\ &\text{is $(n-r)!$ times the ``number of permutations of $r$ elements out of $n$'' $(^nP_r)$. So \: $(n-r)!\cdot(^nP_r)=n!$ .}\\ \\ \text{Definition:}\quad&\boxed{^nP_r=\frac{n!}{(n-r)!}=\text{Number of permutations of $r$ elements selected from a set of $n$ elements \it without \rm repetition.}}\\ &\text{e.g. There are $^5P_3=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60$ permutations of 3 elements selected from a set of 5 elements.}\\ \\ \text{Note:}\quad &\because\quad n!=\:^nP_n=\tfrac{n!}{(n-n)!}=\tfrac{n!}{0!}\:,\quad\therefore\quad 0!=\tfrac{n!}{n!}\:.\quad\boxed{0!=1}\\ \end{align*} % % Combinations % \begin{align*} \text{\bf Combinations:}\quad &\text{A \it combination \rm is an unordered subset of elements selected from a certain set.}\\ \\ &\text{With reference to the analysis of permutations (ordered arrangements), since there are $^nP_r$ ways to}\\ &\text{arrange $r$ elements from a set of $n$, if their order is \it not \rm of interest, for each selection of $r$ elements, the}\\ &\text{$r!$ permutations of them are in fact the same selection and therefore counted as one. So the ``number}\\ &\text{of permutations'' ($^nP_r$) is $r!$ times the ``number of combinations'' ($^nC_r$). So \: $r!\cdot(^nC_r)=\:^nP_r=\tfrac{n!}{(n-r)!}$ .}\\ \\ \text{Definition:}\quad&\boxed{^nC_r=\binom{n}{r}=\frac{n!}{r!(n-r)!}=\text{Number of combinations of $r$ elements selected from a set of $n$ elements.}}\\ &\text{e.g. There are $^5C_3=\frac{5!}{3!(5-3)!}=\frac{5!}{3!2!}=10$ combinations of 3 elements selected from a set of 5 elements.}\\ \\ Note:\quad&\because\quad^nC_r=\frac{n!}{r!(n-r)!}=\frac{n!}{[n-(n-r)]!(n-r)!}=\:^nC_{n-r}\:,\quad\therefore\quad\boxed{^nC_r=\:^nC_{n-r}}\:.\\ &\text{i.e. There are as many ways to ``include'' $r$ elements from a set of $n$ as to ``exclude'' $n-r$ elements from it.}\\ \\ \\ \text{\bf Groups:}\quad &\text{When some elements need to be together in the arrangement, each group is taken as one element, and}\\ &\text{the total number of permutations is $\boxed{n!\prod_{r=1}^n g_r!}$ , where $n$ is the number of groups (individual elements}\\ &\text{are taken as groups of one), and $g_r$ is the number of elements in group $r$ (which might be 1).}\\ \\ &\text{e.g. Ways to arrange letters \it abcdefg \rm with \it ab \rm and \it def \rm together: We have four groups --- ``\it ab\rm'', ``\it c\rm'', ``\it def''}\\ &\text{and ``\it g\rm''. So $g_1=2,\:g_2=1,\:g_3=3,\:g_4=1$ and $n=4$ . There are $4!\times(2!\times 1!\times 3!\times 1!)=288$ ways.}\\ \\ \\ \text{\bf Separation:}\quad &\text{When there are $r$ elements that need to be separated in the arrangement of $n$ ($r\leq n+1$), first place the}\\ &\text{$n-r$ elements that do not need to be separated, then place the remaining $r$ elements into the $n-r+1$}\\ &\text{``slots'' (between each neighbouring elements already placed, and the two ends). The total number of}\\ &\text{permutations is $\boxed{(n-r)!\:\:^{(n-r+1)}P_r}$ .}\\ \\ &\text{e.g. Ways to arrange letters \it abcdefg \rm with vowels (``\it ae\rm'') separated: $n=7,\:r=2$. Place the 5 elements}\\ &\text{``\it bcdfg\rm'' first \big($(n-r)!=5!$ ways\big), then place \it a \rm and \it e \rm into the 6 ``slots''. There are $5!\times\:^6P_2=3600$ ways.}\\ \end{align*} \end{document}