Tác giả bài viết:
Rất <TLExSQRT>OJ và MarisaOJ
Những con số, những bài toán liên quan đến việc kết hợp các trạng thái với nhau hay đếm số lượng trạng thái,… những bài toán này nghe qua tưởng chừng là những yêu cầu rất đơn giản nhưng nó lại đòi hỏi đến kiến thức của tổ hợp chẳng hạn - một trong những chuyên đề mà các bạn sẽ được gặp lần đầu ở cấp THPT và sau này ở Đại học (thường tồn tại ở môn “Toán rời rạc” hoặc “Lý thuyết số”).
Để đảm bảo tính nhất quán cho bài viết, ký hiệu tổ hợp sẽ là:
$$ \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $$
Độ phức tạp thời gian và không gian sẽ được viết tắt dưới dạng $<O(f(n)), O(g(n))>$.
Ta có:
$$ \binom{n}{k} = \binom{n}{n - k} = \frac{n!}{k! (n - k)!} = \prod_{i = 1}^{k}{\frac{n - i + 1}{i}} $$
Như vậy, ta chỉ cần xét trường hợp $k \leq \frac{n}{2}$ là đủ.
Từ công thức tính tổ hợp, ta có thể sử dụng cách lưu trữ giai thừa để có thể tính.
Khảo sát độ phức tạp: $<O(n), O(1)>$