1.2 Basic Mathematic

1.2.1 Combinatorics

Before we read more about probability, we need to know some basic mathematical notation in combinatorics first.

(1) With replacement

List

Suppose we have a list of length \(n\), denote by \((x_1,\cdots,x_n)\). If there are \(n_i\) choices for \(x_i, i=1, \cdots, r\), then there are \[ n_1 \times n_2 \times \cdots \times n_r \] choices for \((x_1,\cdots,x_n)\).

Example:

A seat number in a train has the form \(\square\bigcirc\bigcirc\), where \(\square\) are capital letters and \(\bigcirc\) are numbers \(0\sim9\). Therefore, there are total \(26 \times 10 \times 10 = 2600\) seat numbers.

(2) Without replacement

Permutations

Suppose now that we have \(n\) objects, then there are \[ n! := n(n − 1)(n − 2) \cdots 3 \cdot 2 \cdot 1 \] different permutations of the \(n\) objects.

Example: TBD

For generalization, factorial for non-negative integer \(n\) is gamma function \(\Gamma(n)=\int_0^\infty t^{n-1}e^{-t} dt\).

Combinations

The number of different groups of \(r\) items that could be formed from a set of \(n\) items is \[ {{N}\choose{r}} = \frac{n!}{(n-r)!r!} \] which represents the number of possible combinations of \(n\) objects taken \(r\) at a time.

Example: TBD

Note tat in the definition \(n \geq k \geq 1\), for other range we have: \[ {{N}\choose{r}} = \begin{cases} 1, & r=0 \\ 0, & (0\leq n<r) \lor (r<0\leq n) \\ (-1)^{r} {{|n|+r-1}\choose{r}}, & (n<0) \land (r>0) \\ (-1)^{n+r} {{|r|-1}\choose{|n|-1}}, & (n<0) \land (r<0) \end{cases} \]

In R programming, you can use factortial(x) and choose(n,k) to calculate the permutations and the combinations.

factorial(5) == 5*4*3*2*1
## [1] TRUE
choose(6,2) == 6*5*4*3*2*1 / ( (4*3*2*1)*(2*1) )
## [1] TRUE
multinomial coefficients

A set of \(n\) distinct items is to be divided into \(r\) distinct groups of respective sizes \(n_1, n_2, \cdots, n_r\), where \(\sum_{i=1}^r n_i = n\). How many different divisions are possible?

Note that there are \({{n}\choose{n_1}}\) possible choices for the first group; for each choice of the first group, there are \({{n-n_1}\choose{n_2}}\) possible choices for the second group; for each choice of the first two groups, there are \({{n-n_1-n_2}\choose{n_3}}\) possible choices for the third group; and so on. Hence, there are \[ {{n}\choose{n_1}} {{n-n_1}\choose{n_2}} \cdots {{n-n_1-n_2-n_{r-1}}\choose{n_r}} = \frac{n!}{n_1! \cdots n_r!} \] possible divisions.

If \(\sum_{i=1}^r n_i = n\), we define multinomial coefficients by \[ {{n}\choose{n_1,n_2,\cdots,n_r}} = \frac{n!}{n_1! \cdots n_r!} \]

Example:

TBD

Cyclic permutation

Example:

TBD

Why we introduce the permutations and combinations? This is because in classical probability, we need to calculate the number of events in the sample space, which will introduce in the below.

1.2.2 Set Theory

The following introduced some notations in the set theory.

Suppose two sets \(A,B \subseteq \Omega\), define

  1. \(\varnothing=\{\}\) (empty set)
  2. \(A^c = \{ \omega | \omega \in \Omega \land \omega \notin A\} = \Omega \setminus A\) (complement of the set \(A\))
  3. \(A \cup B = \{ \omega | \omega \in A \vee \omega \in B\}\) (union of the set \(A,B\))
  4. \(A \cap B = \{ \omega | \omega \in A \land \omega \in B\}\) (intersection of the set \(A,B\))
  5. \(A \setminus B = A - B = \{ \omega | \omega \in A \land \omega \notin B\} = A \cap B^c\) (difference of the set \(A,B\))
  6. \(A \Delta B = (A-B) \cup (B-A) = (A \cup B) - (A \cap B)\) (symmetric difference of the set \(A,B\))
  7. If \(A \cap B = \varnothing\), then define \(A+B = A \cup B\) (additively of the set \(A,B\))


If \(A,B \subseteq \Omega\), and \(A \subseteq B, B \subseteq A\), then \(A=B\).


Proposition:

Suppose \(A,B,C \subseteq \Omega\), then

  1. \(\left(A^c \right)^c = A\)
  2. \(A \cap A^c = \varnothing, \quad A \cup A^c = \Omega\)
  3. \(A \cap \Omega = A, \quad A \cup \varnothing = A\) ( \(\Omega\) and \(\varnothing\) are the identity element of \(\cap\) and \(\cup\) respectively)
  4. \(A \cap A = A, \quad A \cup A = A\) (idempotency law)
  5. \(A \cap B = B \cap A, \quad A \cup B = B \cup A\) (communicative law)
  6. \(A \cap (B \cap C) = (A \cap B) \cap C, \quad A \cup (B \cup C) = (A \cup B) \cup C\) (associated law)
  7. \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C), \quad A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) (distributed law)
  8. If \(A \subseteq B\), then \(A \cap B = A, \quad A \cup B = B\)
  9. \((A \cap B)^c = A^c \cup B^c, \quad (A \cup B)^c = A^c \cap B^c\) (De-Morgan’s law)


Let \(\{A_i\}_{i=1}^\infty\) be a sequence of sets, then \(\bigcup_{i=1}^\infty = A_1 + \sum_{k=2}^\infty A_1^cA_2^c \cdots A_{k-1}^cA_k\).

Here we only discuss the most basic concept in the set theory. For more advanced topics, we will introduced in Chapter 16.

Venn Diagrams

A Venn diagram is a visual tool that displays the relationships between sets. It uses circles or other shapes to show the extent to which different sets overlap. Each circle usually represents a set, and the overlap between circles represents the elements that are common to those sets.