+5

Toán học tổ hợp

II. Các dãy số và công thức quan trọng

1. Dãy Fibonaci

Dãy số Fibonaci được xác định bởi công thức sau:

{f0=0.f1=1.fi=fi1+fi2,với i2.\begin{cases}f_0 = 0.\\f_1 = 1.\\ f_i = f_{i - 1} + f_{i - 2},&\text{với }i \ge 2.\end{cases}

Một số phần tử đầu tiên của dãy Fibonaci là: 0,1,1,2,3,5,8,...0, 1, 1, 2, 3, 5, 8,... Ngoài ra, số Fibonaci thứ NN còn có thể tính bằng công thức tổng quát:

fN=15×[(1+52)N(152)N] (1)f_N = \frac{1}{\sqrt{5}}\times [(\frac{1 + \sqrt{5}}{2})^N - (\frac{1 - \sqrt{5}}{2})^N] \ (1)

Dãy Fibonaci là đáp án của một số bài toán dưới đây:

1.1. Bài toán cổ về các cặp thỏ:

  • Phát biểu bài toán:
    • Ban đầu chỉ có một cặp thỏ được sinh ra.
    • Hai tháng sau khi ra đời, mỗi cặp thỏ sẽ sinh ra một cặp thỏ con mới.
    • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo, chúng lại sinh được một cặp con mới.
    • Giả sử các con thỏ không bao giờ chết, hãy đếm số lượng cặp thỏ ở tháng thứ N?N?
  • Ví dụ: Với N=5,N = 5, ta thấy:


  • Giải thích:
    • Giữa tháng thứ nhất: 11 cặp (cặp ban đầu).
    • Giữa tháng thứ hai: 11 cặp (cặp ban đầu vẫn chưa đẻ).
    • Giữa tháng thứ ba: 22 cặp (cặp ban đầu đẻ thêm một cặp con).
    • Giữa tháng thứ tư: 33 cặp (cặp ban đầu tiếp tục đẻ).
    • Giữa tháng thứ năm: 55 cặp (cặp ban đầu tiếp tục đẻ và cặp thứ hai bắt đầu đẻ).

1.2. Bài toán xếp Domino:

  • Phát biểu bài toán: Đếm số cách xếp N1N - 1 thanh Domino có kích thước 2×12 \times 1 để phủ kín một bảng ô vuông kích thước 2×(N1)2 \times (N - 1).
  • Ví dụ:88 cách khác nhau để xếp các thanh Domino kích thước 2×12 \times 1 phủ kín bảng 2×5 (N=6,f6=8)2 \times 5 \ (N = 6, f_6 = 8):

1.3. Cài đặt:

  • Đối với các giá trị N (N107)N \ (N \le 10^7) không quá lớn, ta có thể tính trực tiếp số Fibonaci bằng công thức truy hồi fi=fi1+fi2f_i = f_{i - 1} + f_{i - 2}. Trong trường hợp NN lớn, cần phải sử dụng Phép nhân ma trận để tính toán, bài toán này sẽ được đề cập tới sau.
  • Cài đặt bằng công thức truy hồi:
    long long fibo(int N)
    {
        if (N <= 1)
            return N;
    
        int fi_2 = 0, fi_1 = 1, cur_fi = 0;
        for (int i = 2; i <= N; ++i)
        {
            cur_fi = fi_1 + fi_2;
            fi_2 = fi_1;
            fi_1 = cur_fi;
        }
        
        return fi_ntext;
    }
    

2. Dãy Catalan:

  • Số Catalan được xác định bởi công thức sau:

CatalanN=1N+1×C2NN=(2N)!(N+1)!×N!;với N0Catalan_N = \frac{1}{N + 1}\times C_{2N}^{N} = \frac{(2N)!}{(N + 1)! \times N!}; \text{với } N \ge 0

  • Một số phần tử đầu tiên của dãy Catalan là: 1,1,2,5,14,42,132,...1, 1, 2, 5, 14, 42, 132,...
  • Số Catalan là đáp án của các bài toán sau:

2.1. Bài toán đặt ngoặc:

  • Phát biểu bài toán: Cho trước số nguyên không âm N,N, hãy đếm số cách khác nhau để đặt NN dấu ngoặc mở và NN dấu ngoặc đóng đúng đắn. Cách đặt ngoặc đúng đắn có thể phát biểu đệ quy như sau:
    • ()() là một cách đặt ngoặc đúng.
    • Nếu XX là một cách đặt ngoặc đúng thì (X),()X(X), ()XX()X() cũng là cách đặt ngoặc đúng.
  • Ví dụ: Với N=3,N=3, ta có 55 cách đặt ngoặc đúng sau:

((())),(()()),(())(),()(()),()()()((())), (()()), (())(), ()(()), ()()()

2.2. Đếm cây nhị phân:

  • Phát biểu bài toán: Cho trước số nguyên không âm N, hãy đếm số cây nhị phân khác nhau có đúng (N+1)(N+1) lá?
  • Ví dụ: Với N=3N = 3:

2.3. Chia đa giác:

  • Phát biểu bài toán: Cho một đa giác lồi gồm (N+2)(N+2) đỉnh. Ta chia đa giác thành các tam giác bằng cách vẽ các đường chéo không cắt nhau trong đa giác. Hỏi có bao nhiêu cách chia như vậy:
  • Ví dụ: Với N=4N = 4:

2.4. Cài đặt:

  • Dưới đây cài đặt chương trình tính số Catalan thứ N (N106)N \ (N \le 10^6) và đưa ra kết quả là phần dư sau khi chia cho 109+710^9+7:
    long long modular_exponentiation(long long A, long long B, long long M)
    {
        if (B == 0)
            return 1LL;
    
        long long half = modular_exponentiation(A, B / 2LL, M) % M;
    
        if (B & 1)
            return (((half * half) % M) * (A % M)) % M;
        else
            return (half * half) % M;
    }
    
    long long inverse_modulo(long long A, long long M)
    {
        return modular_exponentiation(A, M - 2, M);
    }
    
    long long catalan_N(long long N, long long M)
    {
        long long x = 1, y = 1;
        for (int i = N + 2; i <= 2 * N; ++i)
            x = (x * i) % M;
        for (int i = 1; i <= N; ++i)
            y = (y * i) % M;
        y = inverse_modulo(y, M);
    
        return (x * y) % M;
    }
    
    int main()
    {
        long long M = 1e9 + 7;
        cout << catalan_N(N, M);
    }
    

3. Số Euler (Eulerian Number):

  • Số Euler A(N,M)A(N, M) là số lượng hoán vị của các số từ 11 tới NN mà có đúng MM số lớn hơn số đứng liền trước nó. Lấy ví dụ, với N=3,M=1,N = 3, M = 1,44 hoán vị từ 11 tới 33 mà có đúng 11 số lớn hơn số liền trước nó, thể hiện trong bảng dưới đây:


  • Số Euler là hệ số của đa thức Euler bậc MM với công thức:

AN(t)=M=0NA(N,M)×tMA_N(t) = \sum_{M = 0}^N A(N, M)\times t^M

  • Ta có thể tính số Euler bằng hệ thức truy hồi sau:

A(N,M)={0,với MN hoặc N=0.1,với M=0.(NM)×A(N1,M1)+(M+1)×A(N1,M),trường hợp khaˊc.A(N, M) = \begin{cases}0, &\text{với } M \ge N \text{ hoặc } N = 0.\\ 1, &\text{với } M = 0. \\(N - M)\times A(N - 1, M - 1) + (M + 1) \times A(N - 1, M), &\text{trường hợp khác.}\end{cases}

  • Cài đặt: Dưới đây cài đặt chương trình tính số Euler bằng đệ quy, ngoài ra bạn đọc có thể suy nghĩ cách cài đặt bằng quy hoạch động:
    long long euler_number(int N, int M)
    {
        if (M == 0)
            return 1;
        
        if (M >= N || N == 0)
            return 0;
            
        return (N - M) * euler_number(N - 1, M - 1) + 
               (M + 1) * euler_number(N - 1, M);
    }
    

4. Tam giác Pascal:

  • Tam giác Pascal là một công thức xác định các tổ hợp chập kk của n,n, bằng tính chất của tổ hợp: Cnk=Cn1k1+Cn1k (0<k<n)C^k_n = C^{k - 1}_{n - 1} + C^k_{n - 1} \ (0 < k < n). Quy ước hàng đầu tiên của tam giác là n=0n = 0 có duy nhất một số 11 - để biểu thị cho C00=1,C^0_0 = 1,. Sử dụng công thức truy hồi, chúng ta dễ dàng tính được tam giác Pascal với vị trí hàng n,n, cột kk là số lượng tổ hợp chập kk của nn (coi các vị trí trống là 0). Ở mỗi hàng, cột đầu tiên và cột cuối cùng luôn mang giá trị 1,1, thể hiện cho tính chất Cn0=Cnn=1C^0_n = C^n_n = 1. Hình vẽ dưới đây minh họa cho tam giác Pascal với các hàng từ 00 tới 77:


  • Ngoài ra, tam giác Pascal còn sử dụng để tính các hệ số của khai triển nhị thức Newton bậc N (a+b)NN \ (a + b)^N thành một đa thức có N+1N+1 số hạng. Nhị thức này đã được chứng minh bởi Issac Newton vào năm 1665,1665, với công thức như sau:

(a+b)N=k=0NCNk×ank×bk(a+b)^N=\sum_{k = 0}^N C^k_N\times a^{n - k} \times b^k

  • Cài đặt: Xây dựng tam giác Pascal gồm NN hàng:
    void pascal_triangle(int N)
    {
        for (int i = 0; i <= N; ++i) // Cột đầu tiên của mọi hàng bằng 1.
            c[i][0] = 1;
    
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= i; ++j)
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    

5. Công thức bao hàm - loại trừ:

  • Công thức bao hàm - loại trừ là một công thức sử dụng để tính lực lượng (số lượng phần tử) của hợp của nhiều tập hợp. Công thức được phát biểu như sau: "Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của các bộ bốn tập hợp, và cứ thế cho đến khi ta xét đến giao của tất cả các tập hợp."
  • Đối với các tập hợp, công thức có thể được viết ở dạng như sau: Giả sử có NN tập hợp A1,A2,A3,...,ANA_1, A_2, A_3,..., A_N. Lực lượng của hợp của NN tập hợp là:

i=1NAi=i=1nAiijAiAj+A1A2A3+A1A2A4++|\bigcup_{i=1}^N A_i| = \sum_{i=1}^n |A_i| - \sum_{i \ne j} |A_i \cap A_j| + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + \cdots +

AN2AN1AN(1)nA1A2AN|A_{N-2} \cap A_{N-1} \cap A_N| - \cdots - (-1)^n|A_1 \cap A_2 \cap … \cap A_N|

  • Ta có thể minh họa công thức bằng một sơ đồ Venn trong trường hợp N=3N = 3 như sau:


Như sơ đồ, ta thấy lực lượng của ABCA \cap B \cap C bằng tổng lực lượng của A,B,CA, B, C trừ đi lực lượng của các giao AB,BC,CAA \cap B, B \cap C, C \cap A rồi cộng thêm lực lượng của ABCA \cap B \cap C:

ABC=A+B+CABBCCA+ABC| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|

Bằng phương pháp tương tự ta có thể minh họa được công thức với NN tập hợp.

  • Ví dụ: Đếm số lượng số từ 11 tới NN và không chia hết cho số nào trong tập {2,3,5}\{2, 3, 5\}:
    int count_numbers(int N)
    {
        return N - N / 2 - N / 3 - N / 5 + N / (2 * 3) +
               N / (3 * 5) + N / (2 * 5) - N / (2 * 3 * 5);     
    }
    
    Ta có thể biến đổi bài toán thành đếm phần bù: Đếm số lượng phần tử chia hết cho ít nhất một số trong tập {2,3,5}\{2, 3, 5\} rồi lấy NN trừ đi số lượng đó. Đặt AA là tập hợp các phần tử chia hết cho 2, B2,\ B là tập hợp các phần tử chia hết cho 3, C3, \ C là tập hợp các phần tử chia hết cho 55 từ 1 tới NN. Cần tính ABC|A \cup B \cup C|. Dựa vào công thức bao hàm, loại trừ, ta có:

ABC=A+B+CABBCCA+ABC| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|

=N2+N3+N5N2.3N2.5N3.5+N2.3.5=\left \lfloor{\frac{N}{2}} \right \rfloor+\left \lfloor{\frac{N}{3}} \right \rfloor+\left \lfloor{\frac{N}{5}} \right \rfloor-\left \lfloor{\frac{N}{2.3}} \right \rfloor-\left \lfloor{\frac{N}{2.5}} \right \rfloor-\left \lfloor{\frac{N}{3.5}} \right \rfloor+\left \lfloor{\frac{N}{2.3.5}} \right \rfloor

III. Tài liệu tham khảo:


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.