• 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?$
• Ví dụ: Với $N=5,$ ta thấy:

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

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

• Đối với các giá trị N (N≤107)N (N le 10^7)N (N≤107) 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=fi−1+fi−2f_i = f_{i – 1} + f_{i – 2}fi​=fi−1​+fi−2​. Trong trường hợp $N$ 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:

  longlongfibo(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;}

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

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

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

• Phát biểu bài toán: Cho trước số nguyên không âm $N,$ hãy đếm số cách khác nhau để đặt $N$ dấu ngoặc mở và $N$ 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 $X$ là một cách đặt ngoặc đúng thì $(X),()X$ và $X()$ cũng là cách đặt ngoặc đúng.
• Ví dụ: Với $N=3,$ ta có $5$ cách đặt ngoặc đúng sau:

$$((())),(()()),(())(),()(()),()()()$$

• 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)$ lá?
• Ví dụ: Với $N=3$:

• Phát biểu bài toán: Cho một đa giác lồi gồm $(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=4$:

• Dưới đây cài đặt chương trình tính số Catalan thứ N (N≤106)N (N le 10^6)N (N≤106) và đưa ra kết quả là phần dư sau khi chia cho 109+710^9+7109+7:
  

  longlongmodular_exponentiation(longlong A,longlong B,longlong M){if(B ==0)return1LL;longlong half =modular_exponentiation(A, B /2LL, M)% M;if(B &1)return(((half * half)% M)*(A % M))% M;elsereturn(half * half)% M;}longlonginverse_modulo(longlong A,longlong M){returnmodular_exponentiation(A, M -2, M);}longlongcatalan_N(longlong N,longlong M){longlong 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;}intmain(){longlong M =1e9+7;
      cout <<catalan_N(N, M);}

• Số Euler $A(N,M)$ là số lượng hoán vị của các số từ $1$ tới $N$ mà có đúng $M$ số lớn hơn số đứng liền trước nó. Lấy ví dụ, với $N=3,M=1,$ có $4$ hoán vị từ $1$ tới $3$ mà có đúng $1$ 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 $M$ 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
AN​(t)=M=0∑N​A(N,M)×tM

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

A(N,M)={0,với M≥N hoặc N=0.1,với M=0.(N−M)×A(N−1,M−1)+(M+1)×A(N−1,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}
A(N,M)=⎩⎪⎪⎨⎪⎪⎧​0,1,(N−M)×A(N−1,M−1)+(M+1)×A(N−1,M),​với M≥N hoặc N=0.với M=0.trường hợp khaˊc.​

• 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:
  

  longlongeuler_number(int N,int M){if(M ==0)return1;if(M >= N || N ==0)return0;return(N - M)*euler_number(N -1, M -1)+(M +1)*euler_number(N -1, M);}

• Tam giác Pascal là một công thức xác định các tổ hợp chập $k$ của $n,$ bằng tính chất của tổ hợp: Cnk=Cn−1k−1+Cn−1k (0<k<n)C^k_n = C^{k – 1}_{n – 1} + C^k_{n – 1} (0 < k < n)Cnk​=Cn−1k−1​+Cn−1k​ (0<k<n). Quy ước hàng đầu tiên của tam giác là $n=0$ có duy nhất một số $1$ – để biểu thị cho C00=1,C^0_0 = 1,C00​=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,$ cột $k$ là số lượng tổ hợp chập $k$ của $n$ (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,$ thể hiện cho tính chất Cn0=Cnn=1C^0_n = C^n_n = 1Cn0​=Cnn​=1. Hình vẽ dưới đây minh họa cho tam giác Pascal với các hàng từ $0$ tới $7$:

• 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)^NN (a+b)N thành một đa thức có $N+1$ số hạng. Nhị thức này đã được chứng minh bởi Issac Newton vào năm $1665,$ với công thức như sau:

(a+b)N=∑k=0NCNk×an−k×bk(a+b)^N=sum_{k = 0}^N C^k_Ntimes a^{n – k} times b^k
(a+b)N=k=0∑N​CNk​×an−k×bk

• Cài đặt: Xây dựng tam giác Pascal gồm $N$ hàng:
  

  voidpascal_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];}

• 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ó $N$ tập hợp A1,A2,A3,…,ANA_1, A_2, A_3,…, A_NA1​,A2​,A3​,...,AN​. Lực lượng của hợp của $N$ tập hợp là:

∣⋃i=1NAi∣=∑i=1n∣Ai∣−∑i≠j∣Ai∩Aj∣+∣A1∩A2∩A3∣+∣A1∩A2∩A4∣+⋯+|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 +
∣i=1⋃N​Ai​∣=i=1∑n​∣Ai​∣−i​=j∑​∣Ai​∩Aj​∣+∣A1​∩A2​∩A3​∣+∣A1​∩A2​∩A4​∣+⋯+

∣AN−2∩AN−1∩AN∣−⋯−(−1)n∣A1∩A2∩…∩AN∣|A_{N-2} cap A_{N-1} cap A_N| – cdots – (-1)^n|A_1 cap A_2 cap … cap A_N|
∣AN−2​∩AN−1​∩AN​∣−⋯−(−1)n∣A1​∩A2​∩…∩AN​∣

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

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

$$|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 $N$ tập hợp.

• Ví dụ: Đếm số lượng số từ $1$ tới $N$ và không chia hết cho số nào trong tập $\{2,3,5\}$:
  

  intcount_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\}$ rồi lấy $N$ trừ đi số lượng đó. Đặt $A$ là tập hợp các phần tử chia hết cho $2,B$ là tập hợp các phần tử chia hết cho $3,C$ là tập hợp các phần tử chia hết cho $5$ từ 1 tới $N$. Cần tính $|A\cup B\cup C|$. Dựa vào công thức bao hàm, loại trừ, ta có:

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$$

=⌊N2⌋+⌊N3⌋+⌊N5⌋−⌊N2.3⌋−⌊N2.5⌋−⌊N3.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
=⌊2N​⌋+⌊3N​⌋+⌊5N​⌋−⌊2.3N​⌋−⌊2.5N​⌋−⌊3.5N​⌋+⌊2.3.5N​⌋