Linear algebra

Last modified:

Combinatorics (tổ hợp)

Factorial: \(n!\)

Combinations (regardless of order):

Taken k objects at a time from n different objects (Tổ Hợp chập k của n):

\[\mathbf{C_{n}^{k}} = \binom{k}{n} = \frac{n!}{k!(n-k)!}\]

Properties:

\(C_{n}^{k} = C_{n}^{n-k}\)
\(C_{n-1}^{k-1} + C_{n-1}^{k} = C_{n}^{k}\)
\(C_{n}^{0} + C_{n}^{1} + C_{n}^{2} + ... + C_{n}^{n} = 2^n\)

Permutations (distinction in order):

• Taken n different objects (Hoán Vị): \(\mathbf{P_{n}} = A_{n}^{n} = n!\)
• Taken k objects at a time from n different objects (Chỉnh Hợp chập k của n):

\[\begin{align*} \mathbf{A_{n}^{k}}&=n(n-1)(n-2)...(n-k+1)\\ &= \frac{n!}{(n-k)!}\\ &=C_{n}^{k}.k! \end{align*}\]

• Taken n objects not all different: \(\frac{n!}{n_{1}!n_{2}!n_{3}!...n_{k}!}\)

• Taken n different objects arranged in a circle: \((n-1)!\)

The Inclusion-Exclusion Principle: For any two sets \(A\) and \(B\),

\[P(A\cup B) = P(A) + P(B) - P(A\cap B)\]

The Complement Principle: If set \(A\) is a subset of a universal set \(U\), then

\[P(A) = P(U) - P(A^C)\]

where the complement of the event \(A\), consisting of all elements in the sample space \(S\) that are not elements of the set \(A\), is denoted by \(A^C\)